循環連結リスト
循環単方向リストは最後の next を null ではなく最初のノードへ向けます。このレッスンは head と tail を保存し、空でない時に tail.next == head を維持します。
next をたどると始点へ戻り、空参照には達しません。したがって一周して curr == head になったら止めます。この条件を忘れると、存在しない値の検索が無限に続きます。
循環リストの仕組み
円形に並ぶ走者が、次の一人へバトンを渡す形です。コースに終端はなく、出発した人へ戻ったことを自分で判定します。
両端を保存するため、insert_head と insert_tail は O(1)。先頭挿入は新ノードを旧先頭へ向け、head と tail.next を更新します。末尾挿入は新ノードを先頭へ、旧末尾を新ノードへ向け、tail を進めます。毎回 tail.next = head を回復し、画面の折り返し矢印が変化を示します。末尾へ走査しないのは tail の効果で、通常の単方向リストにも追加できます。
search は先頭から比較し、一致すれば途中で添字を返します。不一致なら末尾から先頭へ戻り、進んだ後の curr == head で未発見を返します。成功と失敗では停止理由が違います。
delete は同じ一周の境界で対象と前のノードを探し、前から対象を飛ばします。発見 O(n)、参照変更 O(1)。先頭削除は折り返し先を変え、末尾削除は tail を前へ戻し、唯一のノードなら空にします。
容量 4–10、既定 7 のスライダーは表示制限で、コードの max が対応します。リスト自体の固定容量ではありません。
操作をステップで追う
空の環から始めます。
- 先頭に 5：
5.next = 5の自己ループ。headとtailはともに 5。5 ↺。 - 先頭に 8：
8.next = 5、旧末尾の5.next = 8、headを 8 へ。8 → 5 → 8 に戻る。 - 末尾に 3：
tailはすでに 5。3.next = 8、5.next = 3、tailを 3 へ。8 → 5 → 3 → 8 に戻る。 - 末尾に 7：
7.next = 8、3.next = 7、tailを 7 へ。8 → 5 → 3 → 7 → 8 に戻る。 - 3 を検索：添字 0 で
8 ≠ 3、1 で5 ≠ 3、2 で3 = 3。2 を返し、途中で停止。 - 9 を検索：
8 ≠ 9、5 ≠ 9、3 ≠ 9、7 ≠ 9。末尾を越えたカーソルが折り返し矢印で先頭へ戻る。curr == headで未発見として停止。null は一度も使わない。
画面の通常の next はノード列に、尾から頭への線は下にあります。失敗検索のカーソルはその弧を移動し、一周を目で追えます。
時間・空間計算量
| 操作 | 費用 | 理由 |
|---|---|---|
| 添字アクセス | O(n) | 先頭から next をたどる |
| 先頭挿入 | O(1) | 旧先頭へつなぎ、折り返しを更新 |
| 末尾挿入 | O(1) | tail を保持 |
| 値による削除 | O(n) | 最大一周の探索と定数回の変更 |
| 検索 | O(n) | 一致か一周まで |
| 空間 | O(n) | 各ノードに値と参照一つ |
ノードごとの保存量は単方向リストと同じで、リスト全体に尾への参照を加えます。輪番スケジューリングやリンク型の循環バッファーに適し、環と停止条件の維持が必要です。循環バッファーは配列でも実装でき、リストに限りません。
境界ケース
- 一ノードの環：
node.next = node、head == tail。画面は自己ループを示す。 - 先頭削除：複数ノードなら
head = node.next、次にtail.next = head。 - 末尾削除：複数ノードなら
tail = prev、次にtail.next = head。 - 唯一のノードの削除：
headとtailをともに空にする。旧ノードへの環を残さない。 - 値がない：ちょうど一周し、先頭へ戻って
-1/False。null を待たない。 - 空の検索：
if not self.headで走査前に返す。
よくある間違い
- 空参照を待つ。 非空の環で
while curr:やwhile curr.next:は終わりません。処理して進み、headに戻ったかを確認します。既定の検索 9 で試せます。 - 折り返しの更新を忘れる。 挿入や端の削除後に
tail.next = headを回復します。旧末尾の接続を忘れると切断や新ノードを飛ばす環になります。 - 末尾削除後に
tailを残す。 次の挿入が、環から外したノードにつながります。 - 一ノードを特別扱いしない。
head == tailの削除では両方を空にし、空への最初の挿入では自己ループを作ります。常に二ノード以上あるという仮定は使えません。