Структура данных — Циклический связный список

Циклический связанный список — это разновидность структуры связанного списка. Его ключевая особенность в том, что последний узел списка больше не указывает на NULL, а вместо этого указывает обратно на первый узел, так что весь связанный список логически образует кольцевую структуру.

Структурные особенности циклического связанного списка

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

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

10
→
20
→
30
↺ tail.next = head (возврат к началу)
Каждый узел имеет только указатель next, а хвостовой узел указывает на головной узел, образуя замкнутый цикл
Двусвязный циклический список

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

10
⇄
20
⇄
30
↺ head.prev = tail, tail.next = head
Каждый узел имеет prev + next, а головной и хвостовой узлы взаимосвязаны, образуя двойное кольцо

Обычный связный список: next в конце = NULL, условие завершения обхода — cur == NULL

Циклический связный список: next в конце = head, условие завершения обхода — cur == head (возврат к начальной точке)

Общие операции:Вставка головного узла O(n) — сначала нужно найти хвостовой узел | обход использует цикл do...while

Вставка хвостового узла O(1) (поддерживать указатель tail) | удаление аналогично

Циклические связные списки в основном делятся на два типа:

  • Односвязный циклический список: каждый узел хранит только один указатель next, а next последнего узла указывает обратно на головной узел
  • Двусвязный циклический список: на основе двусвязного списка next последнего узла указывает на головной узел, а prev головного узла указывает на последний узел

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

Условие определения конца обхода — не "достигнут ли NULL", а "произошёл ли возврат к начальному узлу".

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

Пример

#include <stdio.h>
#include <stdlib.h>

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

/* Создать новый узел */
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = newNode;  /* Для одного узла next указывает на себя, образуя петлю */
    return newNode;
}

Узел в голове
Сложность по времени: O(n) — сначала нужно найти хвостовой узел, чтобы обновить его указатель next */
struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = createNode(value);

    if (head == NULL) {
        return newNode;  /* Пустой связный список, новый узел образует петлю */
    }

    /* Найти хвостовой узел (то есть узел, next которого указывает на head) */
    struct Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }

    newNode->next = head;   /* next нового узла указывает на исходный головной узел */
    tail->next = newNode;   /* next хвостового узла указывает на новый узел (новый головной узел) */
    return newNode;          /* Новый узел становится новым головным узлом */
}

/* Обход циклического связного списка (один цикл)
Начать с головного узла, остановиться при возврате к головному узлу снова */
void traverse(struct Node* head) {
    if (head == NULL) return;

    struct Node* cur = head;
    printf("Циклический связный список: ");
    do {
        printf("%d -> ", cur->data);
        cur = cur->next;
    } while (cur != head);  /* Остановиться при возврате к начальной точке */
    printf("(назад к началу)\n");
}

int main() {
    struct Node* head = NULL;
    head = insertAtHead(head, 30);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 10);

    traverse(head);
    /* Вывод: Циклический связный список: 10 -> 20 -> 30 -> (назад к началу) */
    return 0;
}

Ключ к обходу циклического связного списка заключается в использованииdo...whileоператора вместоwhile. Потому что при использованииwhile (cur != head), начальное состояние cur равно head, и цикл вообще не выполнится. Иdo...whileгарантирует, что тело цикла выполнится хотя бы один раз, а затем проверяет условие завершения.

Классическое применение: задача об Иосифе Флавии

Задача об Иосифе Флавии (n=7, m=3)
Начальное состояние: 7 человек образуют круг, начиная с1начинается отсчёт, каждый 3-й человек выбывает
1Старт
2
3Раунд 1
4
5
6
7
↻ Направление подсчёта 1, 2, 3, ...

Порядок выбывания и окончательный результат (n=7, m=3)

3
Раунд 1
→
6
Раунд 2
→
2
Раунд 3
→
7
Раунд 4
→
5
Раунд 5
→
1
Раунд 6
→
4
Выживший

Задача об Иосифе Флавии (Josephus Problem)— это классическая математическая задача:

Предположим, n человек стоят по кругу. Счёт начинается с 1-го человека, и каждый m-й человек выбывает из круга. Затем счёт возобновляется со следующего человека, и это продолжается, пока не останется только последний человек.

Эта задача естественно соответствует структурным особенностям циклического связного списка: «соединён конец с началом, доступ осуществляется циклически».

Пример

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;           /* Номер человека */
    struct Node* next;
};

/* Решение задачи об Иосифе Флавии
Параметры: n — общее количество людей, m — каждый m-й по счёту человек выходит из круга
Используйте циклический связный список для моделирования всего процесса */
void josephus(int n, int m) {
    if (n <= 0) return;

    /* Шаг 1: Создать циклический связный список, содержащий n человек (пронумерованных 1~n) */
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = head;  /* Когда остаётся только один человек, он замыкается сам на себя */

    struct Node* tail = head;
    for (int i = 2; i <= n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = head;   /* У нового узла next всегда указывает на head */
        tail->next = newNode;   /* next предыдущего узла указывает на новый узел */
        tail = newNode;          /* Продвинуть tail */
    }

    /* Шаг 2: смоделировать процесс выбывания */
    struct Node* cur = head;
    struct Node* prev = tail;  /* prev указывает на предшественника cur, изначально — на хвостовой узел */

    printf("Кольцо Иосифа (n=%d, m=%d) порядок выбывания: ", n, m);

    while (cur->next != cur) {  /* Завершить, когда останется только один узел (цикл на себя) */
        /* Подсчёт: отсчитать m-1 раз, одновременно продвигая prev и cur */
        for (int count = 1; count < m; count++) {
            prev = cur;
            cur = cur->next;
        }
        /* Когда счётчик достигает m, cur выбывает */
        printf("%d ", cur->data);
        prev->next = cur->next; /* Пропустить cur */
        free(cur);               /* Освободить выбывший узел */
        cur = prev->next;        /* Перезапустить подсчёт со следующего человека */
    }

    printf("=> Последний выживший: %d\n", cur->data);  /* Вывести последнего человека */
    free(cur);
}

int main() {
    josephus(7, 3);
    /* Вывод: кольцо Иосифа (n=7, m=3), порядок выбывания: 3 6 2 7 5 1 => Последний выживший: 4 */
    return 0;
}

Другие сценарии применения

СценарийОписание
Карусельное планирование квантов времени в операционной системеЦП поочерёдно выделяет кванты времени каждому процессу. Когда процесс исчерпывает свой квант времени, наступает очередь следующего процесса, образуя цикл.
Многопользовательские игры, где игроки по очереди играют в картыВ настольных и карточных играх игроки действуют по очереди по часовой стрелке (или против часовой стрелки).
Кольцевой буферКольцевой буфер для потоков аудио/видео данных; когда он заполнен, он возвращается к началу и перезаписывает старые данные.
Другие расширения