【そうほうこうれんけつりすと】
双方向連結リスト とは？
公開:
💡 前にも後ろにも進める、双方向の連結チェーン
📌 このページのポイント
- 各ノードが「前のノード」と「次のノード」の2つのポインタを持つ
- 前方にも後方にもたどれるので、単方向リストより柔軟
- 任意の位置での挿入・削除がO(1)で行える
- ブラウザの「戻る・進む」やテキストエディタのアンドゥ機能に使われる
ひよこ 前にも後ろにも行けると何がうれしいの？
ペンギン先生 例えばあるノードを削除したいとき、単方向リストだと前のノードを探すのに先頭からたどり直す必要がある。でも双方向なら前のノードにすぐアクセスできるから、削除がO(1)でできるんだ。
ひよこ デメリットはあるのかな？
ペンギン先生 ポインタが2つになるからメモリ消費が増えるし、挿入・削除のときに前後両方のポインタを正しく付け替える必要があるから、実装がちょっと面倒になるんだ。
ひよこ 実際にはどこで使われてるの？
まとめ：ざっくりこれだけ覚えればOK！
「双方向連結リスト」って出てきたら「前にも後ろにも進めるリスト」と思えればだいたいOK！
📖 おまけ：英語の意味
「Doubly Linked List」 ＝ 双方向連結リスト
💬 Doubly（二重に）Linked（つながった）Listだから、双方向に繋がったリストという意味だよ