Связный список как структура данных
💻 Информатика · 9 класс
Что такое связный список
Связный список — это структура данных, в которой элементы хранятся не подряд, а связаны ссылками: каждый элемент содержит значение и указатель на следующий. Чтобы пройти список, начинают с первого элемента и переходят по ссылкам до конца.
Списки удобны там, где часто вставляют и удаляют элементы в середине. В массиве такая операция потребовала бы сдвига множества значений, а в списке достаточно переставить пару ссылок.
Чем отличается от массива
В массиве элементы лежат в памяти подряд, и доступ по индексу мгновенный, зато вставка в середину требует сдвига всех последующих элементов. В списке прямого доступа по номеру нет — к элементу добираются последовательным проходом, зато вставка и удаление выполняются изменением ссылок и не затрагивают остальные элементы.
| Операция | Массив | Связный список |
|---|---|---|
| доступ по номеру | быстро | медленно (проход) |
| вставка в середину | медленно (сдвиг) | быстро (смена ссылок) |
| удаление | медленно | быстро |
| память | только значения | значения и ссылки |
Как устроен элемент
Каждый узел списка хранит данные и ссылку на следующий узел. У последнего узла ссылка пустая — это признак конца списка. Отдельно хранят ссылку на первый узел, иначе до списка нельзя будет добраться.
узел:
значение
следующий | ссылка на другой узел или пусто
первый -> [5|*] -> [2|*] -> [9|пусто]
Проход по списку
Чтобы вывести все элементы, идут от первого узла по ссылкам, пока ссылка не станет пустой:
тек := первый
нц пока тек <> пусто
вывод тек.значение
тек := тек.следующий
кц
Виды списков
Бывает односвязный список, где из узла можно перейти только вперёд, и двусвязный, где каждый узел хранит ещё и ссылку назад. Двусвязный список позволяет двигаться в обе стороны, что удобно для истории действий с переходами «вперёд» и «назад».
Правило: в связном списке нет прямого доступа по номеру. Чтобы добраться до пятого элемента, нужно пройти от первого через все предыдущие узлы по ссылкам.
Где применяют
На основе списков строят очереди, стеки, музыкальные плейлисты, истории действий в редакторах. Они лежат в основе многих более сложных структур данных и используются там, где размер набора заранее неизвестен.
Частые ошибки: теряют ссылку на остаток списка при вставке; забывают про пустую ссылку в конце и зацикливаются; обращаются к элементу по номеру, как в массиве.
Кратко о главном
- Связный список — элементы, соединённые ссылками.
- Каждый узел хранит значение и ссылку на следующий.
- Вставка и удаление быстры, прямого доступа по номеру нет.
- На списках строят очереди, стеки и истории действий.