Связный список

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

История

Концепция связного списка была разработана в 1955—1956 годах Алленом Ньюэллом, Клиффом Шоу и Гербертом Саймоном в рамках исследований по обработке символьной информации и созданию эвристических программ. Они использовали связные списки для представления сложных структур данных в языке программирования IPL (Information Processing Language). В 1960 году эта структура была реализована в языке Lisp, где списки стали основной формой представления данных и кода. Впоследствии связные списки были реализованы практически во всех языках программирования общего назначения, как в виде встроенных библиотек, так и в виде пользовательских структур.

Классификация

Связные списки классифицируются по направлению связей и по способу организации.

По направлению связей

• Односвязный (однонаправленный) список. Каждый узел содержит ссылку только на следующий узел. Обход возможен только в одном направлении — от головы (первого элемента) к хвосту (последнему). У последнего узла ссылка на следующий отсутствует (равна null или nil).
• Двусвязный (двунаправленный) список. Каждый узел содержит две ссылки: на следующий и на предыдущий узел. Это позволяет обходить список в обоих направлениях и упрощает операции удаления узла, так как для этого не требуется хранить указатель на предыдущий элемент.
• Многосвязный список. Узлы имеют несколько ссылок, образующих различные последовательности. Используется, например, для представления разреженных матриц или графов.

По способу организации

• Линейный список. Последний узел ссылается на null. Это классическая последовательность с началом и концом.
• Циклический (кольцевой) список. Последний узел ссылается на первый (или на голову), образуя кольцо. В циклическом списке нет явного начала и конца; обход может продолжаться бесконечно. Для ограничения обычно хранят указатель на какой-либо узел (например, на последний добавленный). Циклические списки удобны для организации очередей с циклическим обслуживанием.
• Список с заголовком (sentinel). В начало списка добавляется фиктивный узел (страж), который не содержит полезных данных, но упрощает алгоритмы вставки и удаления, избавляя от необходимости проверять пустой список отдельно.

Устройство и основные операции

Узел списка

Узел (node) — это базовый элемент. В простейшем односвязном списке узел содержит поле данных (может быть любого типа — число, строка, объект) и поле указателя next. В двусвязном списке добавляется поле prev. В языках со сборкой мусора (Java, C#, Python) узлы создаются как объекты; в языках без сборки мусора (C, C++) память под узлы выделяется динамически и должна освобождаться явно.

Основные операции

• Поиск элемента. Имеет линейную сложность O(n), так как для доступа к i-му элементу необходимо пройти по ссылкам от головы до i-го узла. Это главный недостаток связных списков по сравнению с массивами, где доступ по индексу — O(1).
• Вставка элемента. Вставка в начало (после головы) выполняется за O(1): создаётся новый узел, его ссылка next указывает на текущую голову, а указатель на голову обновляется на новый узел. Вставка в середину или конец требует сначала найти позицию (O(n)), но сама операция вставки после найденного узла — O(1). В двусвязном списке вставка перед узлом также O(1) после его нахождения.
• Удаление элемента. Удаление из начала — O(1): голова переставляется на следующий узел. Удаление из середины требует найти предыдущий узел (O(n)), после чего перестановка ссылок занимает O(1). В двусвязном списке удаление по ссылке на сам узел — O(1), так как предыдущий узел доступен через prev.
• Обход списка. Последовательный проход по всем узлам — O(n). Используется для вывода, поиска, суммирования и т.д.

Применение

Связные списки применяются в тех случаях, где важна динамическая вставка и удаление элементов, а доступ по индексу не является критичным.

• Реализация стеков и очередей. Стек (LIFO) удобно реализовать на односвязном списке с вставкой и удалением в начале. Очередь (FIFO) — на двусвязном списке или на односвязном с указателями на голову и хвост.
• Хеш-таблицы. В методе цепочек (separate chaining) каждый элемент массива хеша является головой связного списка коллизий.
• Управление памятью. Во многих операционных системах свободные блоки памяти организованы в виде связных списков (например, в алгоритмах динамического выделения памяти).
• Представление графов. Списки смежности для хранения рёбер графа часто реализуются как массивы связных списков.
• Реализация ассоциативных массивов. В некоторых языках (например, в Ruby) хеш-таблицы могут использовать связные списки для разрешения коллизий.
• Отмена/повтор действий (undo/redo). Двусвязный список позволяет хранить историю состояний и перемещаться по ней вперёд и назад.
• Музыкальные плейлисты. Циклические списки удобны для зацикленного воспроизведения треков.

Преимущества и недостатки

Преимущества

• Динамический размер: память выделяется по мере необходимости, нет необходимости заранее задавать ёмкость.
• Быстрая вставка и удаление в начале и (для двусвязных) в конце списка — O(1).
• Отсутствие фрагментации памяти при последовательном выделении (в отличие от массивов, которые могут требовать перераспределения с копированием).

Недостатки

• Линейный доступ по индексу — O(n). Невозможен прямой доступ к произвольному элементу.
• Дополнительные затраты памяти на хранение указателей (обычно 4 или 8 байт на узел в зависимости от архитектуры).
• Плохая локальность ссылок: узлы могут быть разбросаны по памяти, что снижает эффективность кэширования процессора.
• Сложность реализации по сравнению с массивами (особенно для двусвязных и циклических списков).
• В языках без сборки мусора требуется аккуратное управление памятью для предотвращения утечек.

Реализация в языках программирования

• C/C++. Связные списки реализуются вручную с помощью структур и указателей. В стандартной библиотеке C++ есть std::forward_list (односвязный) и std::list (двусвязный).
• Java. В стандартной библиотеке Java есть java.util.LinkedList — двусвязный список, реализующий интерфейсы List и Deque.
• Python. Встроенного типа «связный список» нет, но его легко реализовать с помощью классов. В стандартной библиотеке collections.deque реализован как двусвязный список.
• C#. System.Collections.Generic.LinkedList<T> — двусвязный список.
• JavaScript. В языке нет встроенного связного списка, но его можно реализовать с помощью объектов и ссылок.
• Rust. В стандартной библиотеке есть std::collections::LinkedList.

Интересные факты

• Связные списки лежат в основе функциональных языков программирования. В Lisp и Scheme практически все данные представлены в виде списков.
• Алгоритм «разворота» односвязного списка (обращение порядка следования узлов) — классическая задача на собеседованиях по программированию.
• Существуют «пропускающие списки» (skip lists) — вероятностная структура данных, основанная на многоуровневых связных списках, которая обеспечивает логарифмическое время поиска.
• В некоторых реализациях (например, в Linux-ядре) используется макрос container_of для встраивания узлов списка непосредственно в структуры данных, что позволяет избежать дополнительных выделений памяти под узлы.

Источники

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (CLRS), глава 10 «Основные структуры данных».
• Дональд Кнут. «Искусство программирования», том 1 «Основные алгоритмы», раздел 2.2 «Линейные списки».
• Документация по стандартной библиотеке языков C++ (cppreference.com), Java (Oracle), Python (docs.python.org).
• Статья «Linked list» в английской Википедии.