algorithm - XOR リンク リストはどのように機能しますか?

Question

次のリンクで説明しています。
実装は、両方 (前と次のアドレス) を別々に保存するのではなく、前と次のアドレス (nxp など) の XOR を保存することによって機能すると言われています。次のアドレスを取得するためのnxp 。

しかし、これは実際 には前と次のポインターを持つのと同じスペースを使用していませんか?

Answer 1

双方向リンク リストでは、ノードごとに 2 つのポインター (前と次) を格納します。XOR リンク リストでは、ノードごとに 1 つの「ポインター」を格納します。これは、前と次の XOR です (または、一方が存在しない場合は、もう一方だけです (0 での XOR と同じ))。XOR 連結リストを双方向にトラバースできる理由は、XOR の特性と、二重連結リストに固有の情報の冗長性に依存しています。

---

XOR リンク リストに 3 つのノードがあるとします。

A がヘッドであり、難読化されていない B へのポインターを持っている (B XOR 0、次のみ)

B は中央の要素であり、A と C へのポインターの XOR を持ちます。

C はテールであり、難読化されていない B へのポインター (0 XOR B、前のみ)

このリストを反復処理するときは、A から開始します。B に移動するときに、メモリ内の A の位置を記録します。C に移動する場合は、B のポインターと A の XOR をとって、C へのポインターを取得します。メモリ内の B の位置と C への移動。

これが機能するのは、XOR が 2 回適用されると、それ自体を元に戻す特性があるためです: C XOR A XOR A == C. 別の考え方として、二重連結リストには、単方向連結リストにはない余分な情報は保存されません (単に保存しているだけなので)。以前のすべてのポインターは、メモリ内の別の場所にある次のポインターのコピーとして)、この冗長性を活用することで、必要な数のリンクのみを持つ二重リンク リスト プロパティを作成できます。ただし、これは XOR 連結リストのトラバーサルを最初または最後から開始した場合にのみ機能します — 途中でランダムなノードにジャンプしただけでは、トラバースを開始するために必要な情報がありません。

---

XOR リンク リストにはメモリ使用量が少ないという利点がありますが、欠点もあります。2 つのポインターの XOR が、コード以外のポインターによって正しく認識されないため、コンパイラ、デバッグ、および静的分析ツールが混乱します。また、最初に真のポインターを回復するために XOR 操作を実行する必要があるため、ポインター アクセスが遅くなります。また、マネージ コードでは使用できません。XOR 難読化されたポインターは、ガベージ コレクターによって認識されません。

Answer 2

しかし、これは実際には前と次のポインターを持つのと同じスペースを使用していませんか?

いいえ - 「前」と「次」を XOR した結果のサイズが 2 つのうち大きい方のサイズに等しいため、約半分のスペースを使用します。

Answer 3

XOR には非常に特殊な特性があります。つまり、 が与えられa XOR b = cた場合、3 番目の変数を計算するために必要な変数は 2 つ (任意の 2 つ) だけであり、いくつかの制限があります。これが機能する理由については、 XOR スワップ アルゴリズムを参照してください。

この場合、前の (または次の) ポインターは引き続き運ぶ必要がありますが、トラバーサル計算を介してのみであり、別のメンバーとしてではありません。

Answer 4

二重連結リストには、N ノード用に格納された 2*N ポインターと、少なくとも 1 つの追加ポインター (ヘッド、またはおそらくヘッドとテール) が必要です。

XOR リンク リストには、N 個のノード用に格納された N 個のポインターと、少なくとも 2 つの追加のポインター (ヘッドと最後にアクセスしたノード、またはおそらくヘッドとテールと最後にアクセスしたノード) が必要です。トラバースしている間、1 つのノード (最後に訪れたノード) を保存しますが、次のノードに移動すると、現在前のノードのアドレスでそれを書き換えます。