【そうほうこうれんけつりすと】
双方向連結リスト とは？
最終更新:
💡 前にも後ろにも進める、双方向の連結チェーン
各ノードが前後両方のノードへのポインタを持つ連結リスト。前方にも後方にもたどれるため、挿入・削除が柔軟に行えるデータ構造。
📌 このページのポイント
- 各ノードが前と次のノードへの2つのリンクを持つ
- 前方にも後方にもノードをたどれる
- 対象ノードや挿入位置が既知なら、リンクの付け替えはO(1)
- 位置を探す走査はO(n)になり得て、前後のリンク管理も必要
ひよこ 双方向連結リストって、単方向のリストと何が違うの？
ひよこ 削除するときも便利なの？
ペンギン先生 対象ノードがすでにわかっていれば、その前後のノードのリンクを付け替える処理はO(1)でできるよ。ただし、先に目的の位置を探すなら、走査にO(n)かかる場合がある。単方向でも前のノードがわかっていれば、先頭から探し直す必要はないんだ。
ひよこ デメリットはあるのかな？
ペンギン先生 前後2つのリンクを保持する分のメモリが必要で、挿入・削除では両方を正しく更新する必要があるよ。リンクの操作が速いことと、目的のデータを探すのが速いことは別なんだ。
ひよこ 実際にはどこで使われてるの？
まとめ：ざっくりこれだけ覚えればOK！
「双方向連結リスト」って出てきたら「前にも後ろにも進めるリスト」と思えばだいたいOK！
📖 おまけ：英語の意味
「Doubly Linked List」 ＝ 双方向連結リスト
💬 Doubly（二重に）Linked（つながった）Listだから、双方向に繋がったリストという意味だよ