データ構造 - 循環リンクリスト

循環リンクリストはリンクリスト構造の一種の変種であり、その核心的な特徴は、リンクリストの最後のノードが 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 ポインタを維持)| 削除も同様

循環リンクリストは主に2つのタイプに分けられます:

  • 単方向循環リンクリスト:各ノードは1つの 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はループ本体が少なくとも1回実行されることを保証し、その後終了条件をチェックします。


古典的な応用:ヨセフスの問題

ヨセフスの問題 (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人目を数えるたびにその人を輪から脱落させ、その後次の人から再び数を数え始め、最後の1人だけが残るまでこれを繰り返します。

この問題は、循環リンクリストの「先頭と末尾がつながり、循環アクセスする」という構造的特性に自然と合致します。

実例

#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;  /* 1人だけの場合は自己環 */

    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 は常に先頭を指す */
        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) {  /* 残り1ノードのみ(自己環)になったら終了 */
        /* カウント: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;
}

その他の応用シーン

シーン説明
OSのタイムスライス・ラウンドロビンスケジューリングCPU が各プロセスにタイムスライスを順番に割り当て、1つのプロセスがタイムスライスを使い切ると次のプロセスに移り、循環を形成します
多人数ゲームで順番にカードを出すボードゲームやカードゲームでは、プレイヤーが時計回り(または反時計回り)に順番に操作します
循環バッファ音声/動画データストリームの循環バッファで、書き込みが満杯になると先頭に戻って古いデータを上書きします
その他の拡張