地方エンジニアの学習日記

興味ある技術の雑なメモだったりを書いてくブログ。たまに日記とガジェット紹介。

単方向リストと双方向リスト

双方向と片方向
双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置(そのノードの前に新たなノードを挿入する)が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に1つ前のノードのアドレスも知る必要がある。アルゴリズムによっては双方向のアクセスが必須な場合もある。一方、双方向リストでは尾部の共有はできないので、永続データ構造としては使えない。

削除したいノードのアドレスを別のデータ構造で管理している場合はノードの削除とノードにに紐づく前後のノードのポインタ情報を書き換えればノードの削除移動が双方向リストだと可能

単方向リストだと削除したノードのアドレスがわかっても前のノードのアドレスを知るための方法がないためO(N)の時間がかかってしまう。