ハッシュ表のチェインほうで双方向リストのほうが優れている点はありますでしょうか?
有名な教科書のMIT教科書アルゴリズムイントロダクション第3版のP213の図11.3の解説文。
ハッシュ表をチェイン法で実装してる解説で疑問点があったので質問します。
「連結リストは一方向、あるいは双方向であり、図は削除が高速にできる双方向連結リストである」という記述があります。
一方向でも双方向でも実装ができるのはわかるのですが、「双方向のほうが削除が高速にできる」という記述の根拠がわかりません。
双方向だとprevがあるから逆にたどれるというのはわかりますが、削除の際にリストをたどる方向は最初の要素から一方向に外に向かってというイメージなので逆方向にたどれるメリットを感じません。削除が高速にできるというのもわかりません。
ちなみに英語版でも同様の解説でした。
双方向のほうが削除が高速にできるという記述の根拠を教えてください。もしこの記述や私の解釈がおかしければチェイン法における単方向、双方向リストのそれぞれのメリット・デメリットを教えてほしいです。