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

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

Если я знаю первый узел списка, голову, я могу проследить за всеми указателями и пройти весь список. Остальную часть списка часто называют хвостом. Это подсписок всего, кроме головы. Приведенный выше пример представляет собой простейшую форму связного списка, часто называемого односвязным списком. Как вы, наверное, догадались, мы можем перемещаться по списку вперед, но у нас нет указателей для перемещения назад. Кроме того, что происходит, когда мы дойдем до конца списка? Каждый узел имеет указатель на следующий, но на последнем узле следующего нет. Обычно этому значению присваивается значение null, чтобы обозначить конец списка. Это приводит к печально известному условию обхода «while (node.next! = Null)».

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

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

История

Связанный список был изобретен в 1955–1956 гг. Гербертом Саймоном, Аланом Ньюэллом и Клиффом Шоу из корпорации RAND. Его первоначальная цель заключалась в создании базовой структуры данных на языке IPL для искусственного интеллекта. На протяжении многих лет он все чаще используется в основных языках программирования, таких как LISP.

Представление

Погляди

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

Вставка и удаление

Явным преимуществом метода связанных списков является то, что нам не нужно перемещать элементы для вставки или удаления узлов. Нам просто нужно переставить указатели, константу или операцию O (1). Поскольку мы можем часто знать головной или последний узел списка, мы можем напрямую вставить туда новые узлы за время O (1). С другой стороны, если мы должны вставить в середину списка, мы должны потратить время, необходимое для обхода, а затем вставки элемента, случай средней сложности O (n / 2) + O (1).

Ускорение поиска

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

Недостатки

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

Альтернативы

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

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