Что такое кольцевая структура данных?

# Кольцевая структура данных (Circular Data Structure)

Кольцевая структура данных — это структура, в которой последний элемент связан с первым, образуя замкнутый цикл. Это распространённый паттерн в информатике, используемый для оптимизации памяти и повышения производительности.

Основные типы кольцевых структур

1. Кольцевой связный список (Circular Linked List)

public class CircularLinkedList<T> {
    private Node<T> head;
    private int size;
    
    private class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    // Добавление элемента
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        
        if (head == null) {
            head = newNode;
            newNode.next = head;  // ← Замыкаем цикл!
        } else {
            Node<T> current = head;
            while (current.next != head) {  // ← Условие цикла
                current = current.next;
            }
            current.next = newNode;
            newNode.next = head;  // ← Замыкаем цикл
        }
        size++;
    }
    
    // Обход всех элементов
    public void display() {
        if (head == null) return;
        
        Node<T> current = head;
        do {
            System.out.println(current.data);
            current = current.next;
        } while (current != head);  // ← Останавливаемся, когда вернулись к началу
    }
}

2. Кольцевой буфер (Circular Buffer / Ring Buffer)

Мост часто используемая реализация. Это массив фиксированного размера, где индекс указателя циклически переполняется:

public class CircularBuffer<T> {
    private T[] buffer;
    private int head;      // Указатель на начало
    private int tail;      // Указатель на конец
    private int size;      // Текущее количество элементов
    private int capacity;  // Максимальный размер
    
    @SuppressWarnings("unchecked")
    public CircularBuffer(int capacity) {
        this.buffer = new Object[capacity];
        this.capacity = capacity;
        this.head = 0;
        this.tail = -1;
        this.size = 0;
    }
    
    // Добавление элемента в очередь
    public void enqueue(T element) throws Exception {
        if (size == capacity) {
            throw new Exception("Буфер переполнен");
        }
        
        tail = (tail + 1) % capacity;  // ← Циклический переход
        buffer[tail] = element;
        size++;
    }
    
    // Извлечение элемента из очереди
    public T dequeue() throws Exception {
        if (size == 0) {
            throw new Exception("Буфер пуст");
        }
        
        T element = buffer[head];
        head = (head + 1) % capacity;  // ← Циклический переход
        size--;
        return element;
    }
    
    public int getSize() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

3. Пример использования Circular Buffer

public class CircularBufferExample {
    public static void main(String[] args) throws Exception {
        CircularBuffer<Integer> buffer = new CircularBuffer<>(5);
        
        // Добавляем элементы
        buffer.enqueue(10);
        buffer.enqueue(20);
        buffer.enqueue(30);
        
        System.out.println("Размер: " + buffer.getSize());  // 3
        
        // Извлекаем элементы
        System.out.println(buffer.dequeue());  // 10
        System.out.println(buffer.dequeue());  // 20
        
        // Добавляем ещё
        buffer.enqueue(40);
        buffer.enqueue(50);
        buffer.enqueue(60);
        buffer.enqueue(70);
        buffer.enqueue(80);
        
        // Буфер полный
        System.out.println("Переполнен: " + buffer.isFull());  // true
    }
}

Практическое сравнение с массивом

Линейный массив в очереди:

[10] [20] [30] [ ] [ ]
 ↑ head          ↑ tail

// После удаления головы:
[__] [20] [30] [ ] [ ]  ← Память потеряна!
     ↑ head          

Кольцевой буфер:

Первое состояние:
[10] [20] [30] [ ] [ ]
 ↑ head         ↑ tail

После удаления 10 и добавления 40:
[40] [20] [30] [ ] [ ]
     ↑ head     ↑ tail → циклически перемещается

Преимущества кольцевых структур

1. Эффективность памяти — нет необходимости перевыделять память при удалении элементов
2. Производительность — операции add/remove выполняются за O(1)
3. Предсказуемость — фиксированный размер буфера известен заранее
4. Простота реализации — благодаря циклическому переполнению индекса

Где используются кольцевые структуры

1. java.util.ArrayDeque — внутренне использует кольцевой буфер
2. Логирование — журналы событий с фиксированным размером (ringbuffer в SLF4J)
3. Сетевые пакеты — буферы для передачи данных
4. Музыкальные плееры — очередь воспроизведения
5. Игры — системы частиц, анимации
6. Databases — WAL (Write-Ahead Logs)
7. Обработка сигналов — DSP приложения

Java-примеры в стандартной библиотеке

// ArrayDeque - двусторонняя очередь на основе кольцевого буфера
Deque<Integer> deque = new ArrayDeque<>(10);
deque.addLast(1);
deque.addLast(2);
deque.removeFirst();  // ← Эффективно работает за счёт кольцевой структуры

// RingBuffer в Disruptor (для высокопроизводительных систем)

Резюме

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