Der folgende Link wird erklärt
Es wird gesagt, dass die Implementierung funktioniert, indem das XOR der vorherigen und der nächsten Adresse (z. B. nxp) gespeichert wird, anstatt beide (vorherige und nächste Adresse) getrennt zu speichern. Es wird jedoch gesagt, dass die Implementierung mit
Aber nutzt das nicht praktisch den gleichen Platz als vorherigen und nächsten Zeiger?
In einer doppelt verknüpften Liste speichern Sie zwei Zeiger pro Knoten: prev und next. In einer XOR-verknüpften Liste speichern Sie einen "Zeiger" pro Knoten, der das XOR von prev und next ist (oder wenn einer von ihnen abwesend ist, nur der andere (das gleiche wie XORing mit 0)). Der Grund, warum Sie immer noch eine XOR-verknüpfte Liste in beide Richtungen durchlaufen können, beruht auf den Eigenschaften von XOR und der Redundanz von Informationen, die einer doppelt verknüpften Liste innewohnen.
Stellen Sie sich vor, Sie haben drei Knoten in Ihrer XOR-Liste.
A ist der Kopf und hat einen unverschleierten Zeiger auf B (B XOR 0, nur neben)
B ist das mittlere Element und hat das XOR von Zeigern zu A und zu C.
C ist der Schwanz und ein unauffälliger Zeiger auf B (0 XOR B, nur prev)
Wenn ich über diese Liste iteriere, fange ich bei A an. Ich notiere die Position von A im Speicher, während ich nach B fahre. Wenn ich zu C reisen will, führe ich den Zeiger mit A aus und gestatte mir den Zeiger auf C. Ich notiere dann die Position von B im Speicher und fahre zu C.
Das funktioniert, weil XOR die Eigenschaft hat, sich selbst rückgängig zu machen, wenn es zweimal angewendet wird: C XOR A XOR A == C. Eine andere Möglichkeit ist, dass die doppelt verknüpfte Liste keine zusätzlichen Informationen speichert es speichert nur alle vorherigen Zeiger als Kopien der nächsten Zeiger irgendwo anders im Speicher), also können wir durch Ausnutzen dieser Redundanz Listeneigenschaften doppelt mit nur so vielen Links verknüpfen, wie benötigt werden. Allerdings Das funktioniert nur, wenn wir unsere XOR-Linked-List-Traversierung von Anfang oder Ende starten - als ob wir einfach in einen zufälligen Knoten in der Mitte springen würden, wir hätten nicht die Informationen, um die Traversierung zu starten.
Während eine XOR-verknüpfte Liste den Vorteil einer geringeren Speichernutzung bietet, hat sie Nachteile - sie verwirrt die Compiler-, Debugging- und statischen Analyse-Tools, da Ihr XOR von zwei Zeigern von keinem Zeiger außer von Ihrem Code korrekt erkannt wird . Es verlangsamt auch den Zeigerzugriff, um die XOR-Operation durchführen zu müssen, um den wahren Zeiger zuerst wiederherzustellen. Es kann auch nicht in verwaltetem Code verwendet werden - XOR-verschleierte Zeiger werden vom Garbage Collector nicht erkannt.
Aber benutzt das nicht praktisch den gleichen Platz wie früher und nächste Zeiger?
Nein - es verwendet ungefähr die Hälfte des Platzes, da die Größe des Ergebnisses der XOR-Verknüpfung von "prev" und "next" gleich der Größe der größeren der beiden ist.
XOR hat eine ganz spezielle Eigenschaft, nämlich% a XOR b = c , nur zwei (beliebige zwei) der Variablen sind erforderlich, um die dritte, mit einigen Einschränkungen zu berechnen. Sehen Sie sich den XOR-Austauschalgorithmus an, warum dies funktioniert.
In diesem Fall muss der vorherige (oder nächste) Zeiger immer noch mitgeführt werden , aber nur durch Traversalberechnungen und nicht als separates Element.
Die doppelt verkettete Liste benötigt 2 * N Zeiger, die für N Knoten gespeichert sind, plus mindestens einen zusätzlichen Zeiger (Kopf oder Kopf und Schwanz).
Eine XOR-verknüpfte Liste benötigt N Zeiger, die für N Knoten gespeichert sind, plus mindestens zwei zusätzliche Zeiger (Kopf und zuletzt besuchter Knoten oder vielleicht Kopf und Schwanz und zuletzt besuchter Knoten). Während des Traversierens speichern Sie einen Knoten (den zuletzt besuchten Knoten). Wenn Sie jedoch zum nächsten Knoten wechseln, schreiben Sie diesen mit der Adresse des vorherigen Knoten neu.
Tags und Links algorithm