双方向連結リストとは？
双方向連結リストは、各ノードがデータに加えて、前のノードを指すprev、次のノードを指すnextの2つのポインタを持つデータ構造です。
単方向連結リストがnext一つで一方向にしか進めないのに対し、双方向連結リストは前後両方向に自由に走査できます。音楽プレイヤーの前の曲/次の曲、ブラウザの戻る/進むはすべてこの構造の応用です。
単方向連結リストとの違いは？
| 項目 | 単方向 | 双方向 |
|---|---|---|
| ポインタ | nextのみ | prev + next |
| 走査方向 | 前のみ | 前後両方 |
| ノード削除 | 前のノードを別途探す必要 | ノード参照があればO(1) |
| メモリ | 少ない | prev分だけ多い |
核心的な違いは2つです。
- •逆方向走査: tailから
prevをたどって逆順に探索できます。単方向では不可能です。 - •O(1)削除: 削除するノードの参照があれば、そのノードのprev/nextで両隣を直接つなぎ、探索なしで削除できます。
核心アプローチ
双方向連結リストを扱う時に絶対に忘れてはいけない原則が一つあります。連結を変える時は常に両方のポインタをペアで更新する。
- •前/後ろに追加: 新ノードのprev/nextを端のノードに接続し、端のノードのポインタも新ノードを指すようにします。
- •中間挿入: 前ノードのnext、後ろノードのprev、新ノードのprev/nextまで合計4つのポインタを更新します。
- •削除:
node.prev.next = node.next、node.next.prev = node.prevで両隣を互いにつなぎ、ノードを迂回します。
片側だけ変えると反対方向のリンクが切れて走査が壊れるため、「両側をペアで」が最も重要な感覚です。
アルゴノートで直接確認しましょう
prev/next双方向の矢印が追加・削除のたびにどう更新されるか、そしてtailから始まる逆方向探索がどう動作するかを、アルゴノートで1ステップずつ視覚的に確認できます。