双方向連結リスト

双方向リストのノードは next と prev を持ち、リストは head と tail を保存します。逆向きにたどれ、対象ノードをすでに持っていれば、前を探さず O(1) で外せます。

代価はメモリと参照の管理です。途中への挿入は新ノードの二参照と隣接ノードの各一参照、計四回を書きます。片側を忘れると、順方向と逆方向で異なる列を見てしまいます。

双方向リストの仕組み

ノードは両端に連結器のある車両のようなものです。対象を見つけた後は、前後の車両をつなげば取り外せます。

pred と succ の間への挿入は newNode.prev = pred、newNode.next = succ、pred.next = newNode、succ.prev = newNode と書きます。画面は新ノードが両側を指す段階と、両側が新ノードを指す段階に分けます。

内部ノードの削除では node.prev と node.next が隣接点を与えます。node.prev.next = node.next と node.next.prev = node.prev で O(1) の取り外しです。ただし値による発見は O(n)。単方向リストで対象だけを持つ場合と違い、前のノードの情報が保存されています。

search は head から next、search_back は tail から prev をたどります。比較は同じで方向が逆です。

容量スライダーの 4–10、既定 7 は画面とコードの max に対応します。双方向リスト自体の固定容量ではありません。

操作をステップで追う

空から始めます。

1. 先頭に 5：5.prev、5.next は null。head と tail が 5 を指す。
2. 先頭に 8：8.next = 5、8.prev = null、次に 5.prev = 8、head を 8 へ。8 ⇄ 5。
3. 末尾に 3：tail で 5 に直接到達。3.prev = 5、3.next = null、次に 5.next = 3、tail を 3 へ。8 ⇄ 5 ⇄ 3。
4. 添字 1 に 7：curr は添字 0 の前のノード 8 へ。7.prev = 8、7.next = 5、次に 8.next = 7、5.prev = 7。8 ⇄ 7 ⇄ 5 ⇄ 3。
5. 前向きに 7 を検索：添字 0 で 8 ≠ 7、1 で 7 = 7。1 を返す。
6. 後ろ向きに 5 を検索：末尾の添字 3 で 3 ≠ 5、prev をたどり添字 2 で 5 = 5。2 を返す。
7. 7 を削除：curr は前のノードではなく対象 7 に到達。その prev は 8、next は 5。8.next = 5、5.prev = 8 と書いて外す。8 ⇄ 5 ⇄ 3。

画面の上側が next、下側が prev です。新ノードはポインタの書き込みが完了するまで列の上で待ちます。削除時はカーソルが対象を指し、両方の迂回矢印がそこを飛び越えます。

時間・空間計算量

head だけの単方向リストに比べ、逆向き参照と tail を追加しています。逆向き参照は逆走と既知ノードの削除を支えます。末尾挿入 O(1) は tail の効果で、単方向リストにも尾への参照だけを追加できます。

境界ケース

• 空への挿入：唯一のノードが head と tail。両隣は空。
• 先頭の削除：node.prev は空なので head = node.next。新先頭があれば head.prev = null。
• 末尾の削除：tail = node.prev。新末尾があれば tail.next = null。
• 唯一のノードの削除：両隣が空で、head と tail をともに空にする。
• 値がない：どちら向きでも端まで進み、削除は False、検索は -1。例外はない。
• 末尾を超える挿入添字：表示コードには完全な範囲検査がなく、空参照に達する。可視化は停止して説明する。k = 0 は insert_head、k = size は insert_tail。

よくある間違い

• 一方向だけ更新する。 pred.next = newNode だけでは、逆走時に新ノードを飛ばします。succ.prev = newNode も必要です。
• 端の参照を忘れる。 頭尾を削除したら head、tail を更新し、一ノードなら両方を扱います。
• 保持済みノードの前を再探索する。 prev に保存してあるので、再走査は構造の利点を捨てます。
• 常に双方向を選ぶ。 一端での出し入れと前向き走査だけなら追加参照が不要な場合があります。操作に応じて単方向リストや配列を選びます。