双方向リストとは、各データ要素（ノード）が「次の要素」と「前の要素」の両方へのポインタ（参照）を持つデータ構造で、リストを先頭から末尾へ、または末尾から先頭へ双方向にたどれるのが特徴です。単方向リストが「次」しか参照できないのに対し、双方向リストは前後の移動や要素の挿入・削除が柔軟で効率的であり、ブラウザの履歴管理や音楽プレイヤーの再生リストなど、双方向のデータアクセスが求められる場面で活用されます。
画像参照：https://basics.k-labo.work/2017/09/28/%E3%83%AA%E3%82%B9%E3%83%88/
主な特徴
- 両方向の走査:
nextポインタとprevポインタを持つため、どちらの方向にも移動可能。 - 効率的な挿入・削除: 特定のノードの前後に新しい要素を追加したり、あるノードを削除したりする操作を、一定時間（O(1)）で実行できる。
- メモリ使用量: 単方向リストに比べ、各ノードが追加の
prevポインタを持つため、メモリ使用量はやや増える。 - 応用例:
- Webブラウザの「進む」「戻る」機能。
- 音楽・動画プレイヤーの再生リスト（前へ/次へ）。
- 両端キューの実装。
O(n)（オーダーN）
アルゴリズムの計算量がデータ量(n)に比例して増える「線形時間」の計算量オーダーです。
▶︎詳しく計算量の考え方を知りたい方はこちら両端キュー
先頭と末尾の両方から要素の追加・削除ができるデータ構造です。
単方向リストとの比較
- 単方向リスト: 次の要素へのポインタのみ。一方向（先頭→末尾）にしかたどれない。メモリ効率が良いが、逆方向への移動はできない。
- 双方向リスト: 前後両方へのポインタ。双方向の移動や操作が柔軟。メモリ使用量は単方向より多い。
コメント