Comment fonctionne exactement un XOR liste Liée de travail?

Dans une liste doublement chaînée, de stocker les deux pointeurs par nœud: prev et next. Dans un XOR liste liée, vous stockez un 'pointeur' par nœud, ce qui est le XOR de prev et next (ou si l'un d'eux est absent, juste de l'autre (le même que XORing 0)). La raison pour laquelle vous pouvez encore parcourir un XOR liste liée dans les deux directions s'appuie sur les propriétés de XOR et la redondance de l'information inhérente à une double liste chaînée.

---

Imaginez que vous avez trois nœuds dans votre XOR liste liée.

Un est le chef, et a un unobfuscated pointeur vers B (B XOR 0, après seulement)

B est le milieu de l'élément, et a le XOR de pointeurs A et C.

C est la queue, et une unobfuscated pointeur vers B (0 XOR B, prev seulement)

Quand je suis à parcourir cette liste, je commence à A. je note Une position en mémoire, car je voyage à B. Quand je veux voyager à C, je XOR B le pointeur de la avec Un, m'accordant le pointeur de la C. ensuite, je note B de la position dans la mémoire et les voyages de C.

Cela fonctionne parce que le XOR est la propriété de la réparation elle-même si elle est appliquée deux fois: C UN XOR XOR A == C. une Autre façon de le penser il est, la liste doublement liée stocke aucune information supplémentaire une seule liste liée n'est pas (puisqu'il s'agit seulement de stocker toutes les pointeurs que des copies de pointeurs suivants ailleurs en mémoire), par l'exploitation de cette redondance, nous pouvons disposer de liste doublement chaînée propriétés avec seulement que de nombreux liens sont nécessaires pour. Cependant, Cela ne fonctionne que si nous commençons notre XOR liste liée de la traversée à partir du début ou de la fin — comme si nous n'sauter dans un nœud aléatoire dans le milieu, nous n'avons pas les informations nécessaires pour commencer la traversée.

---

Tout un XOR liste liée a l'avantage de réduire l'utilisation de la mémoire, il a aussi des inconvénients — il confondre le compilateur, le débogage et les outils d'analyse statique comme votre XOR de deux pointeurs ne sera pas correctement reconnu par un pointeur par rien, sauf votre code. Il ralentit aussi le pointeur de l'accès à l'devez faire l'opération XOR pour récupérer le vrai pointeur de la première. Il a également ne peut pas être utilisé dans du code managé — XOR obscurci les pointeurs ne sont pas reconnus par le garbage collector.

XOR a un très spécial de la propriété à ce sujet, à savoir, compte tenu de a XOR b = c, seulement deux (deux) de la variable sont tenus de calculer le troisième, avec certaines restrictions. Voir la XOR algorithme de swap pour expliquer pourquoi cela fonctionne.

Dans ce cas, le précédent (ou suivant) pointeur doit toujours être porté, mais seulement par le biais de la traversée de calculs et non pas comme un autre membre.

Considérons la suite XOR liste

A->B->C->D

supposons que vous nœuds créés dans ce format ci-dessous

Clé|Lien|

A|0^addr(B)| ->  B|addr(A)^addr(C)|  ->  C|addr(B)^addr(D)| -> D|addr(C)^0|

CAS n ° 1:[Avant la Traversée] Maintenant, Supposons que vous êtes dans B (current_node=>B) voulez visiter C , si vous avez besoin de l'Adresse de C . La façon dont vous obtenez ?

Addressof(Next_node) = addressof(Prev_node) ^ Current_node(Lien)

addr(A)^ ( addr(A)^ addr(C) )
=>(addr(A) ^ addr(A)) ^ addr(C) 
=> 0 ^ addr(C)
=>addr(C)

CAS n ° 2: [en Arrière de la traversée] Maintenant, Supposons que vous êtes dans C (current_node=> C) veulent visiter, B , de sorte que vous besoin de l'Adresse de B . La façon dont vous obtenez ?

Addressof(Prev_node) = addressof(Next_node) ^ Current_node(Lien)

addr(D) ^ ((addr(B) ^ addr(D)) 
=> (addr(D)^ addr(D)) ^ addr(B)
=> 0^addr(B)
=> addr(B)

Déplacement:
De parcourir toute la liste ,Vous aurez besoin de 3 pointeurs prevPtr , currPtr , nextPtr pour stocker actuelle relative, précédent et suivant du nœud de l'adresse de départ de la tête.
Puis, à chaque itération ces pointeurs besoin de se déplacer vers une position de l'avant.

struct Node *currPtr = head;
struct Node *prevPtr = NULL;
struct Node *nextPtr;

printf ("Following are the nodes of Linked List: \n");

while (currPtr != NULL)
{
    //print current node
    printf ("%d ", currPtr->key);

    //Save the address of next node
    nextPtr = XOR (prevPtr, currPtr->link);

    //move prevPtr and currPtr one position for next iteration

    prevPtr = currPtr;
    currPtr = nextPtr;
}