Связные списки

Зачем нужны связные списки

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

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

Что входит в раздел

• Основы связных списков. Разберём устройство узла, роль ссылки next и отличие последовательного доступа от индексного.
• Односвязный список. Научимся работать с цепочкой, в которой каждый узел знает только о следующем элементе.
• Двусвязный список. Добавим ссылку назад и увидим, какие операции становятся удобнее ценой дополнительной памяти.
• Быстрый и медленный указатели. Познакомимся с техникой, где две ссылки движутся по одной цепочке с разной скоростью.
• Разворот связного списка. Научимся менять направление ссылок без создания второго списка из тех же элементов.
• Поиск цикла. Разберём ситуацию, когда цепочка вместо окончания возвращается к уже посещённому узлу.
• Слияние связных списков. Применим последовательный обход для объединения двух упорядоченных цепочек.

Связи важнее индексов

Node first = new Node(10);
Node second = new Node(20);

first.next = second;

Эти две строки уже образуют маленький связный список. Дальше мы будем работать не с индексами, а с узлами и ссылками между ними — именно это лежит в основе всего раздела.