Что такое связный список

Связный список — это структура данных из узлов, где каждый узел хранит данные и ссылку на следующий (а в двусвязном — также на предыдущий) узел. Различают односвязные, двусвязные и кольцевые связные списки. Индексация и поиск в них выполняются за O(n), а вставка и удаление при известном месте — за O(1).

Определение:

Связный список — это структура данных, в которой элементы хранятся в узлах, а узлы соединены между собой с помощью ссылок.

• Данные хранятся в узлах, каждый узел указывает на другой узел.
• Узел содержит один элемент данных и одну ссылку (в односвязном списке — на следующий узел).
• Связный список соединяет узлы друг с другом последовательной цепочкой ссылок.

Что вам нужно знать:

• Связный список разработан для оптимизации вставки и удаления; он медленно работает при индексировании и поиске по позиции.
• Двусвязный список содержит узлы, которые ссылаются и на следующий, и на предыдущий узел.
• Кольцевой связный список — это связный список, хвост которого (последний узел) ссылается на голову (первый узел).
• Очереди тоже могут быть реализованы с помощью связного списка или массива.
• Очереди — это FIFO-структуры данных (first in, first out).
• Очередь представляет собой двусвязный список, в котором элементы удаляются из головы, а добавляются в хвост.

Эффективность (Big O) операций в связном списке:

• Индексирование по позиции: O(n), так как для доступа к элементу нужно пройти список от головы до нужного узла.
• Поиск элемента по значению: O(n), так как требуется последовательно обходить узлы.
• Вставка при известной позиции (после уже найденного узла): O(1), но поиск позиции занимает O(n).
• Вставка в начало — O(1); вставка в конец — O(1) при наличии ссылки на хвост, иначе O(n).
• Удаление известного узла — O(1); удаление по значению с предварительным поиском — O(n).