Что такое связные списки простыми словами?

Пример структуры узла на языке C++:

Каждый узел может быть формально описан как структура данных в виде абстрактного псевдокода.

Логическая структура списка формируется исключительно за счет цепочки указателей, а не физического расположения элементов.

Каждый узел содержит ссылку на произвольный адрес памяти, что формирует последовательную логическую цепочку, независимо от физического расположения узлов в памяти.

Представим, что мы хотим добавить элемент в начало связного списка. Операция включает три последовательных действия: создание нового узла, переназначение указателя next и обновление указателя head.

На первом этапе создаем новый элемент (например, со значением = 2), который размещается по некоторому адресу памяти (например, 0xCC в рамках примера).

На данном этапе новый элемент существует, но его поле указателя ещё не ссылается на какие-либо элементы связного списка.

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

Иными словами, поле next нового элемента начинает указывать на прежний первый элемент связного списка. Таким образом новый узел включается в существующую цепочку и становится ее предшествующим звеном.

После установления связи выполняется обновление указателя head.

Указатель головы переназначается и ссылается на новый созданный элемент.

В результате новый узел становится первым элементом связного списка, а прежняя голова становится вторым элементом структуры.

Операция никак не зависит от элементов связного списка, поэтому сложность как по времени, так и по памяти, — константная O(1).

Рассмотрим операцию вставки нового элемента в конец списка. Операция включает три последовательных шага: создание нового узла, переназначение указателя next у предыдущего хвоста и обновление указателя tail.

Создается новый узел (например, со значением = 7) и адресом памяти (например, 0x08).

На момент создания его указатель не ссылается на элементы списка. Так как элемент является последним в структуре, его указатель next принимает значение nil.

Далее выполняется операция связывания структуры: текущий последний элемент связного списка изменяет свой указатель таким образом, чтобы он ссылался на вновь созданный узел.

Таким образом, прежний хвост списка перестает указывать на nil и включается в цепочку связного списка, соединяясь с новым элементом.

После этого выполняется обновление указателя tail. Указатель хвоста переназначается на вновь добавленный узел, который становится последним элементом структуры данных.

Поскольку количество выполняемых операций не зависит от размера связного списка, временная и пространственная сложность данной операции является константной O(1).

Рассмотрим операцию вставки между двумя существующими узлами.

Для вставки элемента в середину связного списка сначала выполняется создание нового узла. Присваиваем элементу значение (например, 8) и размещаем по некоторому адресу памяти (например, 0xB8).

На момент создания он не содержит корректных ссылок на элементы связного списка.

Представим, что у нас есть указатели на два элемента в связном списке. Для этого предполагается наличие двух указателей (или итераторов), которые указывают на два соседних элемента связного списка, между которыми должна быть выполнена вставка нового узла.

1. На первом этапе выполняется перенаправление указателя нового узла: указатель нового элемента теперь ссылается на правый элемент из пары.

2. На втором этапе выполняется разрыв существующей связи между двумя исходными узлами и перенаправление указателя левого узла. Указатель левого элемента теперь ссылается на вновь созданный узел.

Поскольку количество операций фиксировано и не зависит от размера связного списка, временная и пространственная сложность данной операции является константной O(1).

Рассмотрим операцию удаления первого элемента связного списка.

В исходной структуре указатель head ссылается на первый узел списка. Для удаления данного узла достаточно выполнить переназначение указателя головы на следующий элемент.

После выполнения данной операции второй элемент списка становится новым первым элементом, а прежний первый элемент исключается из цепочки связей.

После исключения элемента из структуры данных он становится недостижимым через указатели списка.

Дальнейшая обработка зависит от модели управления памятью:

• при ручном управлении памятью вам нужно будет очистить выделенную память;
• при автоматическом управлении памятью сборщик мусора сам очистит этот участок памяти.

Операция удаления из начала включает единственное изменение указателя head, следовательно, как по времени, так и по памяти — константная O(1).

Удаление последнего элемента представляет собой более сложную задачу, так как односвязный список не содержит обратных ссылок.

Для того чтобы удалить последний элемент, нужно передвинуть tail на предыдущий узел.

Но в классическом односвязном списке каждый элемент содержит ссылку только на следующий элемент, а не на предыдущий. Это означает отсутствие прямого доступа к предыдущему элементу, что затрудняет удаление последнего элемента.

Через какие стратегии можно определить предыдущий элемент от хвоста:

После определения предпоследнего элемента меняем положение tail на предыдущий от хвоста элемент.

Тем самым последний элемент исключается из цепочки, а новый хвост корректно завершается.

Удаленный узел становится недоступным через структуру данных. В дальнейшем память от удаленного узла освободится вами вручную либо при автоматической очистке сборщиком мусора.

Если у вас изначально есть указатель на предыдущий элемент, то сложность удаления из конца будет константной О(1) как по времени, так и по памяти, т. к. все, что нужно будет сделать — это передвинуть tail и у предыдущего элемента обновить следующий элемент.

Рассмотрим удаление произвольного элемента, доступ к которому уже известен.

Представим, что у нас снова есть указатель, и вы понимаете, какой элемент вы хотите удалить.

Для удаления все, что нужно сделать, — это обновить указатель, чтобы элемент со значением «3» начал указывать на элемент со значением «5».

Сперва смотрим, куда указывает элемент со значением «3» — на элемент со значением «8»

Затем смотрим, куда указывает элемент со значением «8» — на элемент со значением «5»

В итоге получаем нужный адрес (в нашем примере это 0x04) и меняем на него указатель.

После переназначения указателей удаляемый элемент перестает участвовать в структуре связного списка.

В будущем при ручном управлении памятью потребуется ручное освобождение, а при при использовании сборщика мусора объект становится кандидатом на удаление автоматически.

Если у вас изначально есть указатель на предыдущий элемент, то сложность удаления из конца будет константной О(1) как по времени, так и по памяти, т. к. все, что нужно будет сделать — это обновить указатель.

После рассмотрения операций вставки и удаления может показаться, что связный список — универсальная структура данных. Действительно, большинство операций модификации выполняются за константное время.

Причина заключается в особенностях хранения данных и способе доступа к элементам.

Рассмотрим, каким образом осуществляется доступ к произвольному элементу массива. Предположим, имеется массив data, и необходимо получить второй элемент. При этом индексация начинается с нуля.

Для вычисления адреса нужного элемента в массиве используется простая формула:

Если массив состоит из целых чисел (int), то размер элемента равен размеру типа int.

После вычисления адреса выполняется операция разыменования указателя, в результате которой получается значение необходимого элемента.

Подобный механизм возможен благодаря устройству оперативной памяти (RAM — Random Access Memory). Оперативная память предоставляет возможность обратиться к любому байту за одинаковое время, поэтому доступ к элементу массива выполняется за константное время — O(1).

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

Для получения элемента с номером N потребуется выполнить N последовательных переходов между узлами.

По этой причине операция обращения к произвольному элементу имеет:

• линейную сложность по времени — O(n);
• константную сложность по памяти — O(1).

Еще важно отметить, что при обходе массива элементы располагаются последовательно друг за другом. Благодаря этому процессор может заранее загружать соседние данные в кэш. Такое поведение называется хорошей кэш-локальностью. В результате при последовательном обходе массива большинство обращений выполняется не к оперативной памяти, а к быстрому кэшу процессора.

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

В результате процессор не может эффективно предугадывать следующие обращения. Данные значительно хуже кэшируются и чаще происходят промахи кэша. Такое свойство называется плохой кэш-локальностью.

Поэтому, несмотря на одинаковую сложность O(n), итерация по связному списку на практике обычно выполняется заметно медленнее, чем итерация по массиву.

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

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

В результате каждый элемент будет хранить:

• значение;
• указатель на следующий элемент (next);
• указатель на предыдущий элемент (prev).

Первый элемент не имеет предыдущего узла, поэтому его указатель prev содержит значение nil. Аналогично последний элемент содержит значение nil в поле next. Такая структура называется двусвязным списком (Doubly Linked List).

Наличие дополнительного указателя позволяет эффективно выполнять операции, которые затруднены в односвязном списке.

Появляется возможность:

• перемещаться по списку как вперед, так и назад;
• быстро получать предыдущий элемент;
• упрощать некоторые операции удаления и вставки.

За счет хранения обратных ссылок многие алгоритмы становятся удобнее в реализации, но дополнительная функциональность достигается за счет увеличения объема памяти. Каждый узел теперь хранит не один указатель, а два, поэтому на хранение структуры требуется больше памяти по сравнению с односвязным списком.

Пример структуры узла двусвязного списка на языке C++:

Подводя итог, выделим несколько ключевых характеристик связного списка.

К преимуществам относятся:

К недостаткам относятся:

Связные списки наиболее эффективны в задачах, где нужно часто модифицировать структуру данных.

Например, они хорошо подходят для реализации списка задач в системе управления проектами. Если задачи регулярно меняют приоритет, перемещаются между различными статусами или часто переставляются относительно друг друга, использование связного списка позволяет выполнять такие изменения без перемещения всех элементов структуры.

Еще одним примером является реализация очередей. Например, очередь запросов в колл-центре обрабатывается по принципу FIFO: первым обслуживается тот запрос, который поступил раньше остальных. После обработки первый элемент удаляется из начала очереди. Поскольку удаление первого элемента в связном списке выполняется за O(1), такая структура данных хорошо подходит для реализации подобных очередей.

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

Поэтому выбор между массивом и связным списком всегда определяется характером решаемой задачи: если требуется быстрый доступ к элементам — предпочтителен массив, если же структура данных постоянно изменяется — более эффективным решением становится связный список.

Если хотите подробнее разобраться в работе связных списков, то смотрите наше видео с наглядными примерами из курса по структурам данных.