В информатике, свя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Мы с вами рассмотрим реализацию односвязного (однонаправленного) списка.
*-Нравится статья? Кликни по рекламе! 🙂


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

В одной из статей Sython’а (Cвойство замыкания, на примере list) мы уже создавали похожую структуру, методами функционального программирования. Пришло время задействовать ООП!)

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

Рисунок 1. Пример связного списка

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

Основные правила реализации связных списков
Список состоит из элементов, называемых узлами (node). Первый узел списка называется «головным» (head), а последний — «хвостовым» (tail). На рисунке 2 изображен двойной связный список.

Рисунок 2. Двойной связный список

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