Циклический двусвязный список

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

Основные свойства

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

Ключевые характеристики:

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

История

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

Устройство и реализация

Структура узла

В типичной реализации на языке C узел описывается как:

``c struct Node { int data; // данные struct Node prev; // указатель на предыдущий узел struct Node next; // указатель на следующий узел }; ``

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

1. Вставка в начало: создаётся новый узел, его next указывает на текущий первый узел, prev — на последний. Затем корректируются ссылки соседних узлов. Если список пуст, новый узел замыкается сам на себя.
2. Вставка в конец: аналогично, но новый узел становится последним.
3. Удаление узла: изменяются ссылки соседних узлов, чтобы они указывали друг на друга, минуя удаляемый. Память освобождается.
4. Обход: начинается с любого узла и продолжается до возврата в исходную точку. Для предотвращения бесконечного цикла используется условие остановки (например, счётчик или сравнение с начальным узлом).

Пример реализации на Python

```python class Node: def __init__(self, data): self.data = data self.prev = None self.next = None

class CircularDoublyLinkedList: def __init__(self): self.head = None

def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: new_node.next = new_node new_node.prev = new_node self.head = new_node else: last = self.head.prev new_node.next = self.head new_node.prev = last self.head.prev = new_node last.next = new_node self.head = new_node ```

Применение

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

• Планировщики задач (Round Robin): в операционных системах циклический список позволяет равномерно распределять процессорное время между процессами, обходя их по кругу.
• Игровые циклы: в компьютерных играх для управления очередностью ходов или обновления состояний объектов.
• Кэширование (алгоритм «Часы»): в алгоритме замены страниц (Clock algorithm) используется циклический список для отслеживания недавно использованных страниц памяти.
• Реализация очередей с кольцевым буфером: в системах реального времени и встроенных устройствах (например, в драйверах устройств).
• Графические редакторы: для хранения истории действий (undo/redo) с возможностью циклического возврата.

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

Достоинства и недостатки

Достоинства

• Возможность обхода в обоих направлениях без необходимости хранить отдельные указатели на начало и конец.
• Вставка и удаление в начале и конце выполняются за константное время.
• Отсутствие необходимости в реаллокации памяти (в отличие от массивов).
• Удобство для реализации циклических алгоритмов (например, Round Robin).

Недостатки

• Более сложная реализация по сравнению с односвязным списком.
• Повышенный расход памяти (два указателя вместо одного).
• Риск зацикливания при обходе, если не предусмотрено условие остановки.
• Медленный произвольный доступ (O(n) по сравнению с O(1) у массивов).

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

• В языке C++ циклический двусвязный список реализован в стандартной библиотеке как std::list (двусвязный список), но не является циклическим по умолчанию — циклическая версия может быть эмулирована с помощью итераторов.
• В некоторых реализациях (например, в ядре Linux) для управления списками используется макрос list_head, который позволяет создавать циклические двусвязные списки без хранения данных в самом узле — данные хранятся в структуре-контейнере.
• Алгоритм «Часы» (Clock) для замены страниц в виртуальной памяти был разработан в 1968 году и до сих пор используется в некоторых операционных системах.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006. — 720 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002. — 688 с.
• Документация по ядру Linux: «Linked Lists in the Linux Kernel» (внутренняя документация, 2020).