ある本で「削除が高速にできる双方向連結リスト」とあったのですが何故か？

Question

双方向リストは一方向より早いのでしょうか？
それは何故でしょうか？

Answer 1

双方向という事は前後へのリンク情報も保持しているという事なので削除対象が特定されている時点で削除物の前にあるデータと削除物の後にあるデータを連結して削除対象物をリストから除外するという整理操作がその場ですぐに解決できますが、例えば片方向（後方）の場合だと、削除対象が特定されていても削除物の前にあるデータは検索しないと特定できないので双方向の時に比べると検索コストが余計にかかってしまう理屈になります。

[例]
A→B→C から B を削除したい場合に
1.「Aの次がBである」を「Aの次はCである」に変更
2.「Cの前がBである」を「Cの前はAである」に変更(双方向の場合)
をしなくてはなりませんが、
・双方向ならBがAとCへのリンク情報を持っているのでBだけですぐにAとCを特定できる
・片方向ならBはCへのリンク情報しかもっていないのでAの特定には検索が必要
という違いがあります。

Answer 2

prev -> here -> next で現在hereをポイントしてて、hereを削除となると
削除要素のひとつ前:prevをポイントせにゃならんので速くはなさそう。

が、ゴマカシが許されるなら nextのナカミをhereにコピーしたのちnextを削除することで hereが削除されたようにみせかけることができます。
ただし、
1.コピーのコストが大きいと速くない(ポインタ張替えの方が速いなら、双方向の方が速いことになる)
2.末尾要素が削除できない

Comments

[退会済みユーザー]

おお！
その削除の方法は気付かなかったのでベストアンサーにしようかと思ったのですがプログラムの他のところにhere,nextをポイントして使ってる部分があったらバグになっちゃうのかと思ったのですがどうでしょうか。

[episteme]

ですね、どっかヨソでnextをポイントしてる誰かさんに迷惑をかけることになります。
とはいえ、双方向でも here をポイントしてる誰かさんに迷惑をかけるわけだし。

[yumetodo]

いや、消す要素が全体に比べて少ないものの膨大な場合は削除処理を非同期化できるというメリットが・・・

[yumetodo]

あーいや、なんでもない、間違って読んでいた

Answer 3

一方向は逆方向にたどれないし、削除と言ってもリンクの付替えだけで済むから。

Answer 4

解決済みですが。

皆様おっしゃられる通り、以下のようなリストを考えます。
head->p1->・・・->p11->p12->p13->・・・
ここでp12を削除する場合を考えると、p11のポインタを書き換える必要があります。しかし、フォーカス（巡回用ポインタ）がp12を指示しているならば、先頭から辿らないとp11のポインタを変更できないので手間がかかります。

ただし、これはフォーカスの運用次第です。

フォーカスを二つ使うとか、先読運用（例えばp11を指しているときにp12に対する処理を行う。）とか、解決する方法がないわけではありません。

蛇足

非常に変則な形ですが、フォーカスだけ双方向ポインタをもち、これを中心にリストの向きを変更していくといったリストの使い方もあります。

head<-p1<-・・・<-p11<-[focus]->p12->p13->・・・

これはメモリ容量が小さいときに使われていた小手先の技術なので推奨はしません。読み取りだけでもデータ改変が必要なので、現在はむしろ悪手です。

Answer 5

単方向リストで、「ポインタが指している要素を削除する」という関数を実装することを考えてみると分かるかと。根本から、その要素までず～～～と辿らないといけない。

Answer 6

多分に推測になりますが、双方向連結リストで「削除が高速にできる」の比較対象は一方向リストではなく、配列などリストでないデータ構造なのではないかと思います。

配列であれば途中の削除は「残りを全部ずらす」しかないのでリスト構造のほうが有利ですが、一方向リストに対しては優位になりません。

Comments

[maisumakun]

ただ、ポインタで指したような「この要素」を削除したいとなった場合は、双方向リストであればそこから両方向のポインタをたどって削除すればいいのに対して、一方向リストの場合は「前」がわからないので、リストを改めてたどる必要が出てきます。