😊
コンピュータサイエンスの基礎・上級②：双方向リスト
本記事はコンピュータサインス学習サービスRecursionの学習記録です。
双方向リスト(doubly linked list)
双方向リストは、連結リストの一種で、双方向の走査を可能にする。
各ノードは、次のノードへのポインタと前のノードへのポインタの2つを保持している。
これによりリストを順方向にも逆方向にもたどることができる。
双方向リストのインデックス
片方向リストと同様に、要素にアクセスするには線形探索を使用する。
計算量はO(n)になる。
双方向リストの反転
双方向リストでは、prevポインタを使ってリストを逆方向にたどることでリストを反転することができる。
双方向リストの挿入
双方向リストにデータを挿入するには、既存のノードの前後に新しいノードを追加する必要がある。
リストの先頭や末尾へのノード挿入はO(1)で実行できるが、リストの途中に挿入する場合はO(n)の計算量を要する。
双方向リストの削除
双方向リストの利点として、前のポインタを持っていることからノードの削除をO(1)で実行できる点がある。
片方向リストよりも効率的な削除が可能となり、操作のスピードが上昇する。
例えば、「A」「B」「C」というノードが順番に並んでいるときに「B」を削除する場合、「A」と「C」を直接つなげるだけで削除が完了する。
メモ
前回に続き、配列・片方向リストと時間計算量を比較してみた。
| 操作 | 配列 | 片方向リスト | 双方向リスト |
|---|---|---|---|
| インデックス | O(1) | O(n) | O(n) |
| 挿入（先頭） | O(n) | O(1) | O(1) |
| 挿入（末尾） | O(1) | O(n) | O(1) |
| 挿入（中間） | O(n) | O(n) | O(n) |
| 削除（先頭） | O(n) | O(1) | O(1) |
| 削除（末尾） | O(1) | O(n) | O(1) |
| 削除（中間） | O(n) | O(n) | O(1) |
- 配列はインデックスアクセスが高速だが、挿入・削除には時間がかかる。都度要素をシフトするからだと思う。
- 片方向リストは先頭での挿入・削除が早いが、末尾では時間がかかる。
- 双方向リストはインデックスアクセス以外は早い。
比較すると双方向リストの良さが目立つ。何かデメリットがないか調べてみた。
- 片方向リストに比べるとメモリ消費量が多い
ポインタの数が倍になるから。 - 片方向リストに比べると実装が複雑
単純にポインタが多いのでコードが複雑になりやすい。特にエッジケース(空のリスト、先頭や末尾の操作など)でバグが発生しやすくなる。 - 配列に比べるとキャッシュ効率が悪い
配列はメモリ上で連続的に格納されるため、CPUキャッシュによる高速化が期待できる。大量のデータを順次主檻する場合、配列の方が高速に動作することが多い。
こんな具合で、どんなアプローチにも一長一短があることが確認できた。
時間計算量を考えるときに先頭・末尾・中間という観点があることを知れたのがよかった。設計やレビューの際の引き出しが増えた気がする。
Discussion