Циклический список¶

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

¶История

Концепция циклических структур данных возникла в середине XX века с развитием вычислительной техники. Одним из ранних применений стало использование кольцевых буферов в аппаратных устройствах, таких как магнитные барабаны и диски, где данные считывались и записывались последовательно, а адресация велась по модулю. В 1950-х годах кольцевые буферы применялись в системах реального времени для синхронизации потоков данных. В 1960-х годах, с появлением языков программирования высокого уровня, циклические списки стали реализовываться программно, например, в языке Lisp для представления циклических структур. В 1970-х годах они получили распространение в операционных системах для организации очередей процессов (циклическое планирование — round-robin). В 1980-х и 1990-х годах циклические списки стали стандартным элементом библиотек структур данных (например, в STL C++ и Java Collections Framework).

¶Типы циклических списков

Циклические списки классифицируются по способу связей между элементами и по направлению обхода.

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

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

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

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

¶Кольцевой буфер (циклический массив)

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

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

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

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

¶Применение

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

¶Планирование процессов (Round-Robin)

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

¶Кольцевые буферы

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

¶Игры и анимация

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

¶Алгоритмы на графах

Циклические списки применяются в алгоритмах поиска в глубину и ширину для представления списков смежности, особенно когда граф содержит циклы.

¶Очереди с приоритетом

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

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

¶На языке C (односвязный циклический список)

```c

¶include <stdio.h>

¶include <stdlib.h>

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

// Вставка в начало void insertAtBeginning(struct Node** head, int data) { struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = data; if (head == NULL) { newNode->next = newNode; head = newNode; } else { struct Node temp = head; while (temp->next != head) { temp = temp->next; } temp->next = newNode; newNode->next = head; *head = newNode; } }

// Обход списка void traverse(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.size = size self.head = 0 self.tail = 0 self.is_full = False

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

def dequeue(self): if not self.is_full and self.head == self.tail: return None item = self.buffer[self.head] self.head = (self.head + 1) % self.size self.is_full = False return item ```

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

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

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

¶Недостатки

• В односвязной реализации операции вставки и удаления в начале могут требовать полного обхода.
• Сложность обнаружения полного заполнения буфера (необходимо различать пустой и полный буфер).
• Ограничение размера в кольцевом буфере на основе массива.
• Риск бесконечного цикла при неправильной реализации обхода.

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

• В языке программирования Lisp циклические списки могут быть созданы с помощью функции rplaca или rplacd, изменяющей указатели, что позволяет строить кольцевые структуры.
• Кольцевые буферы используются в аппаратных FIFO-буферах (first in, first out) в микроконтроллерах и процессорах для синхронизации потоков данных.
• В алгоритме Джозефуса (задача о выживании) циклический список используется для моделирования круга людей, из которого последовательно удаляются элементы.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (глава 10.2 — списки).
• Седжвик Р. «Фундаментальные алгоритмы на C++» (глава 3 — списки и кольцевые буферы).
• Документация языка C и Python (стандартные библиотеки).
• Статья «Circular buffer» в Wikipedia (англ.).
• Статья «Linked list» в Wikipedia (англ.).