Связанные списки представляют собой линейно сгруппированные наборы данных. Они состоят из узлов, содержащих данные и указатели. Мы сосредоточимся на односвязных списках, узлы которых содержат данные и указатель на следующий узел. Однако имейте в виду, что существуют также двусвязные и циклические списки. В этой истории мы будем говорить о структуре данных связанного списка на языке Арианы Гранде «спасибо, дальше». Если вы не смотрели произведение искусства, являющееся музыкальным видео к песне, сделайте паузу и сделайте это, прежде чем мы начнем.

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

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

В этой статье мы будем использовать следующий список:

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

Думал, что останусь с Шоном
Но он не подошел
Написал несколько песен о Рики
Теперь слушаю и смеюсь
Даже чуть не женился
А за Пита я так благодарен
Хотел бы сказать «спасибо» Малкольму
Потому что он был ангелом

Последний узел - сама Ариана:

К тому же, я познакомился с кем-то еще
У нас есть лучшие обсуждения
Я знаю, они говорят, что я двигаюсь слишком быстро < br /> Но этот будет последним
"Потому что ее зовут Ари
А я" мне так хорошо с этим (так хорошо с этим)

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

Самый простой способ создать односвязный список - создать и связать узлы один за другим:

Пример аналогичного кода на Python.

Если мы отобразим содержимое узла Sean, мы увидим, что он содержит имя в виде данных, а также ссылку на следующий узел - Ricky. С помощью атрибута next мы можем перебирать все узлы по порядку.

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

Связанные списки имеют определенные преимущества перед массивами (их основная альтернатива в мире линейных структур данных). Массивы обычно хранятся в одном блоке памяти, что позволяет использовать быструю формулу для индексации start_of_array_in_memory + space_allocated_for_each_array_item * index_of_item_we_want. Это очень эффективно, когда вам нужно получить объект по определенному индексу. Однако, когда элементы удаляются или добавляются, эффективность алгоритма снижается, потому что все данные должны быть перемещены в другой блок памяти. Нет гарантии, что в памяти будет место для нового объекта перед началом или в конце массива. Чтобы вставить объект в середину массива или удалить его оттуда, работает та же логика - вам нужно переместить большие объемы данных, чтобы получить свободное место или заполнить пробел.

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

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

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

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

Вот как выглядело бы удаление Ricky из нашего связанного списка, если бы Ариана перестала быть ему чертовски благодарна:

Два других полезных метода - search и iterate:

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