Кольцевой список¶

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

¶История

Концепция кольцевого списка возникла в ранних работах по программированию и алгоритмам, связанных с управлением памятью и планированием задач. Одним из первых практических применений стал кольцевой буфер (circular buffer), разработанный в 1950-х годах для организации очередей в операционных системах и системах реального времени. В частности, в вычислительных машинах, таких как IBM 704, кольцевые буферы использовались для синхронизации ввода-вывода данных. В 1960-х годах, с развитием языков программирования (например, Lisp и Algol), кольцевые списки стали применяться в алгоритмах обработки списков и в реализации циклических очередей. В советской вычислительной технике кольцевые списки использовались в операционных системах для ЭВМ серии «Минск» и «Урал» для организации многозадачности.

¶Виды кольцевых списков

Кольцевые списки классифицируются по типу связей между элементами.

¶Односвязный кольцевой список

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

¶Двусвязный кольцевой список

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

¶Кольцевой буфер (кольцевая очередь)

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

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

Кольцевой список хранится в памяти как последовательность узлов, каждый из которых содержит данные и ссылки. Основные операции включают:

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

Кольцевой список не имеет явного «начала» или «конца»; обычно для идентификации используется указатель на какой-либо элемент, называемый «головой» (head) или «текущим» (current). Это отличает его от линейного списка, где конец обозначается нулевым указателем.

¶Применение

Кольцевые списки находят применение в различных областях вычислительной техники и программирования.

¶Планирование задач (Round Robin)

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

¶Кольцевые буферы в системах реального времени

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

¶Реализация очередей и стеков

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

¶Игровые движки и анимация

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

¶Управление памятью

В некоторых реализациях сборщиков мусора и аллокаторов памяти кольцевые списки используются для отслеживания свободных блоков или для организации циклических ссылок.

¶Примеры реализации

¶Пример на языке C (односвязный кольцевой список)

```c

¶include <stdio.h>

¶include <stdlib.h>

struct Node { int data; struct Node* next; };

void insertEnd(struct Node** head, int value) { struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = value; if (head == NULL) { head = newNode; newNode->next = head; } else { struct Node temp = head; while (temp->next != head) { temp = temp->next; } temp->next = newNode; newNode->next = *head; } }

void display(struct Node head) { if (head == NULL) return; struct Node temp = head; do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); printf("\n"); } ```

¶Пример на языке Python (кольцевой буфер)

```python class CircularBuffer: def __init__(self, size): self.buffer = [None] * size self.head = 0 self.tail = 0 self.size = size self.count = 0

def enqueue(self, item): self.buffer[self.tail] = item self.tail = (self.tail + 1) % self.size if self.count < self.size: self.count += 1 else: self.head = (self.head + 1) % self.size

def dequeue(self): if self.count == 0: return None item = self.buffer[self.head] self.head = (self.head + 1) % self.size self.count -= 1 return item ```

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

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

• Циклический обход: возможность начать обход с любого элемента и вернуться к нему без проверки на конец списка.
• Эффективность для циклических алгоритмов: идеально подходит для алгоритмов, где требуется повторяющийся доступ к элементам (например, Round Robin).
• Экономия памяти: кольцевой буфер на массиве не требует динамического выделения памяти для каждого элемента, что снижает накладные расходы.
• Простота реализации: для базовых операций (вставка в конец, удаление из начала) требуется минимальное количество операций.

¶Недостатки

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

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

• В языке программирования Lisp кольцевые списки использовались для реализации циклических структур данных, таких как «бесконечные» списки.
• В советской ЭВМ «Минск-32» кольцевой буфер применялся для организации очереди задач в операционной системе «ДИСПАК».
• Кольцевые списки лежат в основе алгоритма «проблема обедающих философов» (Dining Philosophers Problem), где они используются для моделирования циклического доступа к ресурсам.
• В современных процессорах кольцевые буферы встроены в аппаратные FIFO-очереди для передачи данных между ядрами или устройствами (например, в архитектуре ARM).

¶Источники

• Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2006.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
• Таненбаум Э., Бос Х. Современные операционные системы. — СПб.: Питер, 2015.
• Седжвик Р. Фундаментальные алгоритмы на C. Часть 1. Анализ. Структуры данных. Сортировка. Поиск. — М.: ДиаСофт, 2003.
• ГОСТ 19.701-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».