データ構造 - 循環リンクリスト
循環リンクリストはリンクリスト構造の一種の変種であり、その核心的な特徴は、リンクリストの最後のノードが NULL を指さずに先頭ノードを再び指すことで、リンクリスト全体が論理的に環状構造を形成することです。
循環リンクリストの構造的特徴
単方向循環リンクリスト
双方向循環リンクリスト
普通のリンクリスト:末尾の next = NULL、走査の終了条件は cur == NULL
循環リンクリスト:末尾の next = head、走査の終了条件は cur == head(起点に戻る)
一般的な操作:先頭ノードの挿入 O(n) — まず末尾ノードを見つける必要がある | 走査には do...while ループを使用
末尾ノードの挿入 O(1)(tail ポインタを維持)| 削除も同様
循環リンクリストは主に2つのタイプに分けられます:
- 単方向循環リンクリスト:各ノードは1つの next ポインタのみを保持し、最後のノードの next が再び先頭ノードを指します
- 双方向循環リンクリスト:双方向リンクリストに基づき、最後のノードの next が先頭ノードを指し、先頭ノードの prev が最後のノードを指します
循環リンクリスト構造の最大の特徴は、先頭と末尾がつながった連続走査を自然にサポートすることです。
走査終了の判定条件は「NULL に到達したかどうか」ではなく、「開始ノードに戻ったかどうか」です。
基本操作
実例
#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)
ヨセフスの問題(Josephus Problem)は古典的な数学の問題です:
n人が輪になって囲み、1人目から数を数え始め、m人目を数えるたびにその人を輪から脱落させ、その後次の人から再び数を数え始め、最後の1人だけが残るまでこれを繰り返します。
この問題は、循環リンクリストの「先頭と末尾がつながり、循環アクセスする」という構造的特性に自然と合致します。
実例
#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つのプロセスがタイムスライスを使い切ると次のプロセスに移り、循環を形成します |
| 多人数ゲームで順番にカードを出す | ボードゲームやカードゲームでは、プレイヤーが時計回り(または反時計回り)に順番に操作します |
| 循環バッファ | 音声/動画データストリームの循環バッファで、書き込みが満杯になると先頭に戻って古いデータを上書きします |