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

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

История

Концепция связных списков восходит к ранним работам в области информатики. Первое формальное описание связных списков приписывается Аллену Ньюэллу, Клиффу Шоу и Герберту Саймону, которые в 1955–1956 годах разработали язык обработки списков IPL (Information Processing Language). В IPL использовались односвязные списки. Двусвязные списки, как более гибкая модификация, появились вскоре после этого, когда возникла потребность в эффективных операциях удаления и вставки элементов в середине списка, а также в обратном обходе. Они стали фундаментальной частью многих языков программирования и операционных систем, например, для управления памятью и очередями. В 1960-х годах двусвязные списки были реализованы в таких языках, как Lisp и Simula, а позже стали стандартной частью библиотек шаблонов C++ (std::list) и Java (java.util.LinkedList).

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

Основным элементом двусвязного списка является узел (node). Каждый узел содержит три поля:

1. Данные (Data) — полезная информация, которая может быть любого типа (число, строка, объект).
2. Указатель на следующий узел (Next) — ссылка на следующий элемент в последовательности. Для последнего узла списка этот указатель обычно равен null (или None в Python, nil в Lisp).
3. Указатель на предыдущий узел (Prev) — ссылка на предыдущий элемент. Для первого узла списка этот указатель равен null.

Сам список обычно хранит ссылки на первый узел (голову, head) и на последний узел (хвост, tail). Это позволяет выполнять операции на обоих концах списка за константное время O(1).

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

• Вставка в начало (push_front): Создаётся новый узел. Его Next указывает на текущую голову. Prev текущей головы обновляется, чтобы указывать на новый узел. Голова списка переназначается на новый узел. Время выполнения: O(1).
• Вставка в конец (push_back): Аналогично вставке в начало, но с использованием хвоста. Время выполнения: O(1).
• Вставка в середину (insert_after/insert_before): Требует нахождения узла, после (или перед) которого производится вставка. Если позиция известна (например, по итератору), операция выполняется за O(1). Если позиция задана индексом, требуется обход списка до нужного элемента, что занимает O(n).
• Удаление из начала (pop_front): Голова переназначается на следующий узел. Prev новой головы устанавливается в null. Старая голова удаляется. Время выполнения: O(1).
• Удаление из конца (pop_back): Аналогично удалению из начала, но с использованием хвоста. Время выполнения: O(1).
• Удаление из середины (erase): Если известен указатель на удаляемый узел, его Prev и Next соседей связываются друг с другом, минуя удаляемый элемент. Время выполнения: O(1).
• Поиск элемента (find): Требует последовательного обхода от головы или хвоста. Время выполнения: O(n).

Классификация и разновидности

Хотя двусвязный список сам по себе является конкретной структурой, существуют его модификации:

• Циклический двусвязный список: В этой разновидности указатель Next последнего узла указывает на первый узел, а указатель Prev первого узла — на последний. Это устраняет необходимость в отдельных указателях head и tail, но требует осторожности при обходе, чтобы не зациклиться. Циклические списки удобны для реализации циклических очередей (кольцевых буферов) и в задачах, где требуется бесконечный обход.
• Двусвязный список с фиктивным узлом (sentinel): В список добавляется один или два фиктивных узла (дозорных), которые не содержат полезных данных. Они размещаются в начале и/или в конце списка. Это упрощает алгоритмы вставки и удаления, так как отпадает необходимость в проверке на null для граничных случаев (первый и последний элементы).

Применение

Двусвязные списки находят применение в различных областях программирования и компьютерных наук:

• Реализация стеков и очередей: Благодаря возможности быстрой вставки и удаления на обоих концах, двусвязный список является идеальной базой для реализации двусторонних очередей (deque).
• Управление памятью в операционных системах: Алгоритмы выделения и освобождения памяти (например, в куче) часто используют двусвязные списки для отслеживания свободных и занятых блоков памяти. Это позволяет эффективно объединять соседние свободные блоки.
• Реализация отмены действий (Undo/Redo): В текстовых редакторах, графических редакторах и IDE история изменений часто хранится в виде двусвязного списка. Текущее состояние — это узел, «отмена» перемещает указатель на предыдущий узел, а «повтор» — на следующий.
• Кэширование (алгоритм LRU): Алгоритм вытеснения давно неиспользуемых данных (Least Recently Used) может быть эффективно реализован с помощью двусвязного списка и хеш-таблицы. Список хранит порядок использования элементов: самый недавно использованный — в начале, самый давний — в конце.
• Браузерная навигация: Кнопки «Назад» и «Вперёд» в веб-браузере работают по принципу двусвязного списка. Каждая посещённая страница — это узел, а переходы по истории — перемещение между узлами.
• Компьютерная алгебра: Представление многочленов и разреженных матриц. Каждый ненулевой элемент хранится в узле, а нулевые пропускаются, что экономит память.

Сравнение с другими структурами данных

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

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

• Динамический размер: Память выделяется по мере необходимости, в отличие от статических массивов.
• Эффективные вставка и удаление: Операции вставки и удаления в середине списка выполняются за O(1) при наличии указателя на нужный узел (без необходимости сдвигать остальные элементы, как в массиве).
• Двунаправленный обход: Возможность перемещаться как вперёд, так и назад.
• Эффективные операции на обоих концах: Вставка и удаление в начале и конце списка выполняются за O(1) (при наличии указателей на head и tail).

Недостатки:

• Большой расход памяти: Каждый элемент хранит два дополнительных указателя, что увеличивает потребление памяти по сравнению с массивами или односвязными списками.
• Медленный произвольный доступ: Для доступа к элементу по индексу требуется последовательный обход, что занимает O(n) времени.
• Фрагментация памяти: Узлы могут быть разбросаны по оперативной памяти, что снижает производительность кэша процессора.
• Сложность реализации: Алгоритмы работы с двусвязным списком (особенно вставка и удаление) более сложны и подвержены ошибкам (например, потеря ссылок, разрыв списка), чем для односвязного списка.

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

Многие современные языки программирования предоставляют встроенные реализации двусвязных списков:

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

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

• В некоторых реализациях для экономии памяти используется XOR-связный список, где вместо двух указателей хранится один — результат операции XOR над адресами предыдущего и следующего узлов. Однако это усложняет обход и делает код менее безопасным.
• Двусвязные списки часто используются в ядре Linux для управления различными системными структурами, такими как списки процессов, модулей и файловых систем. В ядре Linux реализован циклический двусвязный список в виде макроса list_head, который встраивается в любую структуру данных, делая её частью списка.

Источники

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
2. Седжвик Р. Фундаментальные алгоритмы на C++. Часть 1-4. Анализ. Структуры данных. Сортировка. Поиск. — М.: ДиаСофт, 2002. — 688 с.
3. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006. — 720 с.
4. Документация по стандартной библиотеке C++: std::list. cppreference.com.
5. Документация Java Platform SE 8: java.util.LinkedList. Oracle.