algorithm - ハッシュテーブルの削除

Question

私はアルゴリズムの紹介という本を読んでいて、これに出くわしました：

リストが二重にリンクされている場合、O(1) 時間で要素を削除できます。(CHAINED-HASH-DELETE はキー k ではなく要素 x を入力として受け取ることに注意してください。そのため、最初に x を検索する必要はありません。ハッシュ テーブルが削除をサポートしている場合、そのリンク リストは二重にリンクされている必要があります。アイテムをすばやく削除できます.リストが単独でリンクされている場合、要素 x を削除するには、まずリスト T[h(x.key)] で x を見つけて、x の次の属性を更新できるようにする必要があります。単独でリンクされたリストでは、削除と検索の両方が同じ漸近的な実行時間になります。)

リストが二重にリンクされている場合、O(1) 時間で要素を削除するにはどうすればよいでしょうか? 最初に要素を見つける必要があり、それから O(1) で削除できます。しかし、それを見つけるには O(リストの長さ) の時間が必要です。二重リンクリストで削除する方が速いかもしれませんが（リストの両端から同時に検索できるためですが、それは常に改善されているだけです）、O（1）でどのように実行できるかわかりません時間。

前もって感謝します。

Answer 1

答えは本文にあります。

CHAINED-HASH-DELETE は、キー k ではなく要素 x を入力として受け取るため、最初に x を検索する必要がないことに注意してください。

すでにアイテムを持っているので、チェーンから削除して削除するだけです。

アイテム X を削除するには、リスト内の前のノードと次のノードを取得し、X を削除する前にそれらをリンクして、リストが途切れないようにする必要があります。双方向にリンクされたリストでは、前と次へのリンクが既にあるため、これは一定です。単一のリンクされたリストでは、次へのリンクしかないため、リストをスキャンして前のノードを見つける必要があります。

Answer 2

ここでの混乱は、CLRS の暗黙の前提によるものだと思います。この本では、オブジェクトは多くの場合、必要なプロパティを実行時に追加できるプロパティ バッグとして扱われます。JavaScript によく似ていますが、Java/C# の世界とは異なります。したがって、x を連結リストに入れたい場合、最初に Node オブジェクトを作成してから、Previous、Next、および Value のプロパティを追加する必要は必ずしもありません。代わりに、これらのプロパティを x 自体に追加するだけです。静的に型付けされた言語で育った私たちの多くは、この設計にショックを受けるでしょうが、疑似コードを使用したアルゴリズム設計では、不要な混乱が取り除かれます。著者はこれを明確にする必要があると思います。いずれにせよ、Previous、Next プロパティをオブジェクトに動的に追加する機能がなければ、はい、二重にリンクされたリストであっても O(1) にはなりません。