Для начинающих

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

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

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

Один узел содержит две вещи: данные и следующий (указатель). Указатель узла содержит ссылку на следующий узел. Это компонент, который помещает ссылку в связанные списки … Указатели являются центральным элементом списков и важной концепцией, которую необходимо усвоить. Как пишет Стэнфордский профессор Ник Парланте:

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

Так! Обратите внимание на указатели…

Список на диаграмме выше имеет длину четыре, потому что есть четыре узла. Заголовок содержит ссылку (указатель) на первый узел. Это точка входа в список. Последний узел списка содержит ссылку, равную нулю, что указывает на конец списка. Если заголовок не ссылается на первый узел, его указатель принимает значение NULL, а значение связанного списка равно NULL.

Давайте взглянем на код! Создадим связанный список на JavaScript:

Для начала у нас есть конструктор узла в строке 1 и конструктор связанного списка в строке 6. Функция в строке 10 добавляет узел в связанный список. Аргумент, передаваемый функции, становится добавленным узлом, инициализированным в строке 11 конструктора узла. В строке 13, если заголовок связанного списка равен нулю, узел назначается заголовку списка. В противном случае в строке 20 функция находит последний узел связанного списка, а в строке 23 назначает новый узел в конец списка.

А теперь давайте создадим связанный список!

В строке 27 мы создаем связанный список из конструктора связанного списка и называем его «список». В строке 28 мы добавляем узел в список, передавая «2» в качестве аргумента. Первый результат, видимый в терминале, - это список с единственным узлом, содержащим «2»:

LinkedList {head: Node {data: 2, next: null}}

Обратите внимание, что узел содержит данные «2», а также ссылку на следующий узел, который имеет значение NULL. Следующий в списке пуст, потому что второй узел не существует (пока). В строке 30 мы добавляем еще один узел в список, передавая «10» в качестве аргумента. Второй результат - это список с обоими наборами введенных данных, «2» и «10»:

LinkedList {head: Node {data: 2, next: Node {data: 10, next: null}}}

Три типа связанных списков

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

Управление списком

Операции можно выполнять в связанном списке. Найдите несколько описанных ниже.

Вставка:
Элемент добавляется в список путем нахождения двух узлов, между которыми он будет помещен. Чтобы поместить его в список, указатель на ранее существовавший левый узел в списке должен быть «переставлен» так, чтобы указатель слева теперь ссылался на новый узел, а новый узел теперь ссылался на узел в Правильно. Если узел помещается в конец списка, узел, который ранее указывал на null, теперь должен указывать на новый узел, а новый узел теперь должен указывать на null, как мы видели в примере кода выше.

Удаление.
Сначала можно удалить элемент из списка, найдя удаляемый элемент. Точно так же при вставке указатели надо переставить. Узел слева больше не будет связан с удаленным узлом. Вместо этого его нужно будет связать с узлом, на который ссылался удаленный узел.

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

На диаграмме ниже указатели 1, 2 и 3 «перенаправляют» каждый узел на тот, который находится за ним. Указатель 4 перенаправляет то, что становится последним узлом списка, на null. Указатель 5 перенаправляет заголовок на то, что становится первым узлом списка.

Можно выполнить несколько дополнительных действий, таких как отображение списка или поиск определенного элемента в списке, среди прочего…

Списки и массивы

Списки часто сравнивают с их конкурирующей линейной структурой данных: массивами. И списки, и массивы линейны и хранят данные. Но какая разница?

  1. В отличие от массивов, элементы списка не хранятся в определенных индексах списка. Элементы списка доступны только через указатели из узла, который был перед ним. К элементам нельзя получить доступ случайным образом: к ним можно получить доступ только с первого узла и далее. Это недостаток, потому что операции становятся медленнее по мере продвижения линии и удаления от передней части. По этой причине массивы более эффективны.
  2. Списки - это динамические структуры. Это позволяет им гибко выбирать количество элементов, которые они могут содержать. Размер списка увеличивается и уменьшается в зависимости от того, добавлен узел или удален. Память хранится в каждом отдельном узле во время выполнения. С другой стороны, массивы - это статические структуры. Массив хранит все свои данные в одном блоке памяти, ограничивая объем данных, которые он может принять. Размер массива должен быть указан во время компиляции и поэтому остается фиксированным в зависимости от того, вставлены или удалены элементы. Ограничения памяти массива являются одним из его самых больших недостатков, поскольку память либо тратится на дополнительное превентивное пространство (выделяемое при создании массива), либо при его отсутствии, когда массив заполняется.
  3. Вставка и удаление элементов из связанного списка влияет только на узлы слева и справа от вставки или удаления. Это оказывает значительно меньшее влияние на остальные узлы в списке, чем на элементы в массиве. Вставка и удаление элементов в массив и из массива является дорогостоящим, потому что пространство ограничено, и нарушает работу, потому что все другие элементы после вставленного или удаленного элемента должны быть сдвинуты (изменяя их индексы). Давайте посмотрим на быстрый пример того, как элементы могут быть нарушены в массиве:

В строке 1 определен массив длиной 5. В строке 6 выполняется поиск элемента с индексом 2 и результатом является 3, как это печатается в терминале.

В строке 9 один элемент объединяется (удаляется) из массива с индексом 1. В этот момент длина массива уменьшается на 1 (при проверке в строке 12), а когда индекс 2 проверяется снова (в строке 15). , значение также изменилось - теперь оно содержит элемент 4. Элемент 3 теперь имеет индекс 1, тогда как раньше он занимал индекс 2.

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

В сумме

В этой статье мы рассмотрели только общий обзор связанных списков, но этого достаточно, чтобы начать знакомиться с концепцией. Связанные списки довольно прямолинейны… (потому что они линейны)… как описано здесь. При этом не бойтесь углубляться в ресурсы, перечисленные ниже. И наслаждайтесь процессом обучения!

использованная литература

Особая благодарность Джейкобу Карлоне за предоставленные примеры кода и Майклу Матичу, Кэрин Кафтал и Феличе Панагроссо за их правки.