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

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

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

Давайте начнем!

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

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

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

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

Когда связанный список менее эффективен?
Напротив, отсутствие индексов в связанном списке снижает эффективность случайного поиска. Обход односвязного списка должен начинаться с головы и переходить по ссылке к следующему узлу, пока не будет достигнут желаемый узел. Это немного более эффективно для двусвязного списка из-за повышенной гибкости для изменения направления (возможность смотреть на следующий и предыдущий). Если пространство является приоритетом, список ссылок может быть не лучшим выбором. Они требуют дополнительного выделения в памяти для хранения указателей / ссылок на предыдущий и следующий.

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

Основные выводы

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