双方向リストとは、各データ要素（ノード）が「次の要素」と「前の要素」の両方へのポインタ（参照）を持つデータ構造で、リストを先頭から末尾へ、または末尾から先頭へ双方向にたどれるのが特徴です。単方向リストが「次」しか参照できないのに対し、双方向リストは前後の移動や要素の挿入・削除が柔軟で効率的であり、ブラウザの履歴管理や音楽プレイヤーの再生リストなど、双方向のデータアクセスが求められる場面で活用されます。
画像参照：https://itsiken.com/22A_L3/22A_L3_05.html
双方向リストの主な特徴
- 両方向の走査:
nextポインタとprevポインタを持つため、どちらの方向にも移動可能。 - 効率的な挿入・削除: 特定のノードの前後に新しい要素を追加したり、あるノードを削除したりする操作を、一定時間（O(1)）で実行できる。
- メモリ使用量: 単方向リストに比べ、各ノードが追加の
prevポインタを持つため、メモリ使用量はやや増える。 - 応用例:
- Webブラウザの「進む」「戻る」機能。
- 音楽・動画プレイヤーの再生リスト（前へ/次へ）。
- 両端キュー（Deque）の実装。
単方向リストとの比較
- 単方向リスト: 次の要素へのポインタのみ。一方向（先頭→末尾）にしかたどれない。メモリ効率が良いが、逆方向への移動はできない。
- 双方向リスト: 前後両方へのポインタ。双方向の移動や操作が柔軟。メモリ使用量は単方向より多い。
コメント