連結リスト
連結リストは独立したノードに値を保存し、各ノードの next が次を指します。先頭への挿入は指し先の変更だけなので O(1)。添字アクセス、検索、任意位置への挿入のための探索は head からたどり、最悪 O(n) です。
各ノードは現在の値と次の場所を持つ手掛かりです。五番目へ飛べず、最初の四つを通ります。ただし挿入位置を見つけた後は、二つの参照をつなぐだけです。
連結リストの仕組み
このレッスンは単方向リストです。Node は value と next を持ち、LinkedList は入口の head だけを保存します。tail がないため、insert_tail は毎回末尾まで歩きます。
insert_head(v) は新ノードの next を旧先頭へ向け、head を新ノードへ変えます。書き込み二回で走査はありません。insert_at(k, v) は添字 k − 1 まで進み、newNode.next = curr.next、curr.next = newNode の順に書きます。順序が重要なので、画面でも別の段階として示します。
delete(v) は先頭を先に検査します。前のノードがないので O(1) の特別処理です。それ以外は curr を進めながら curr.next.value を調べます。発見時には前のノードにいるため、curr.next = curr.next.next で対象を飛ばせます。search(v) は各値を比べ、添字か -1 を返します。
容量スライダーは 4–10、既定 7 で、画面の制約です。コードの max もそれに対応します。リスト構造自体に固定容量はなく、利用可能なメモリに応じて成長できます。
操作をステップで追う
空から入力パネルで実行します。
- 先頭に 5：新ノードの
nextを∅に向け、headを新ノードへ。5 → ∅。 - 先頭に 8：
8.nextを旧先頭 5 へ向け、headを 8 へ。8 → 5 → ∅。 - 末尾に 3：
currは添字 0 の 8、添字 1 の 5 と進む。5.next = ∅で止まり、3.next = ∅、続いて5.nextを 3 へ。8 → 5 → 3 → ∅。 - 添字 1 に 7：前のノードは添字 0。
7.next = 8.nextで 5 を指し、その後8.next = 7。8 → 7 → 5 → 3 → ∅。 - 5 を検索：添字 0 で
8 ≠ 5、1 で7 ≠ 5、2 で5 = 5。2 を返す。 - 5 を削除：先頭は
8 ≠ 5。currが添字 0 なら次の 7、1 なら次の 5 を調べる。発見後、7.nextを 3 へ向けて 5 を飛ばす。8 → 7 → 3 → ∅。
画面の curr が比較位置を示します。新ノードは挿入位置の上で待ち、二つの参照をつないでから列へ入ります。削除ではノードが離れ、矢印がその位置を飛び越えます。動きは書き込み順序に対応します。
時間・空間計算量
| 操作 | 費用 | 理由 |
|---|---|---|
| 添字アクセス | O(n) | head からたどる |
| 先頭へ挿入 | O(1) | 参照の書き込み二回 |
| 末尾へ挿入 | O(n) | この実装は tail を持たない |
| 添字 k へ挿入 | O(k) | 前のノードを探し、O(1) でつなぐ |
| 値で削除 | O(n) | 対象の前を探す |
| 検索 | O(n) | ノードごとに比較 |
| 空間 | O(n) | 値ごとにノードと次への参照 |
tail を維持すれば末尾挿入を O(1) にできます。このコードは走査を見せるため省いています。前のノードが既知なら、つなぎ替え自体は O(1) です。
境界ケース
- 空への挿入：先頭・末尾のどちらも
headを∅から唯一のノードへ変える。 - 空の削除・検索：
deleteはif not self.headでFalseを返し、searchはwhile currのループに一度も入らず-1を返す。例外はない。 - 先頭の削除：
head = head.next。走査は不要。 - 存在しない値の削除：
curr.nextが∅に達してFalseを返す。 - 末尾を超える添字：表示する
insert_at(k, v)には完全な範囲検査がなく、空参照まで歩いて失敗する。可視化は停止して説明する。k = 0はinsert_headに委ねる。
よくある間違い
- 接続の順序を逆にする。
newNode.next = curr.nextが先、curr.next = newNodeが後です。逆にすると後半への参照を失い、新ノードが自分を指す場合もあります。 - 対象だけを探す。 単方向リストの削除は前のノードの
nextを変えるため、curr.nextを調べます。 - 走査条件を一つずらす。
while curr.nextは最後のノードで止まり、末尾挿入に使えます。検索はwhile currで最後も検査します。交換すると見落としや∅の参照が起こります。 - 位置の探索とキャッシュ費用を無視する。 ノードはメモリに散らばる場合があり、参照をたどる処理はキャッシュに不利です。位置が既知で挿入が多い場合に利点があり、添字アクセスが多ければ連続配列が適しています。