質問: ハッシュ表のチェインほうで双方向リストのほうが優れている点はありますでしょうか? 有名な教科書のMIT教科書アルゴリズムイントロダクション第3版のP213の図11.3の解説文。 ハッシュ表をチェイン法で実装してる解説で疑問点があったので質問します。 「連結リストは一方向、あるいは双方向であり、図は削除が高速にできる双方向連結リストである」という記述があります。 一方向でも双方向でも実装ができるのはわかるのですが、「双方向のほうが削除が高速にできる」という記述の根拠がわかりません。 双方向だとprevがあるから逆にたどれるというのはわかりますが、削除の際にリストをたどる方向は最初の要素から一方向に外に向かってというイメージなので逆方向にたどれるメリットを感じません。削除が高速にできるというのもわかりません。 ちなみに英語版でも同様の解説でした。 **双方向のほうが削除が高速にできるという記述の根拠を教えてください。もしこの記述や私の解釈がおかしければチェイン法における単方向、双方向リストのそれぞれのメリット・デメリットを教えてほしいです。**
回答: 双方向リストの削除という場合キーや位置を指定しての削除と、ノードそのものを指定しての削除とで考え方が違います。 キーや位置を指定して削除する場合、そのノードを見つけるために順にたどっていく必要があるので、単方向リストで prev を発見するのと変わりません。*おそらくAkiyama Naoさんが想定してるのはこちら。* 一方ノードそのものを指定する場合、双方向リストではそのノード自身や prev, next をリストを辿って見つける必要がないので単方向リストより高速です。 別の言い方をすれば、 Delete(Hash, Key) であれば単方向でも双方向でも大差ありませんが、 Delete(Hash, Node) であれば双方向のほうが早くなります。 型名等を省略した疑似コードではそこの部分がわかりづらくなってるので、注意深く見てみてください。 C#の双方向リストに関するドキュメントですが、比較しやすく記載されていたので参考に貼っておきます。 ノードを指定して削除する場合の計算量はO(1)、値を指定して削除する場合O(n)となっています。