How exactly does a XOR Linked list work?

Question

The following link explains it.
The implementation is said to work by storing the XOR of the previous and next address(say nxp), instead of storing both(previous and next address) separately.However, further along the implementation is said to work by xor-ing the previous address and nxp, in order to get the next address.

But isnt this practically using the same space as having previous and next pointers?

Answer 1

In a doubly linked list, you store two pointers per node: prev and next. In an XOR linked list, you store one 'pointer' per node, which is the XOR of prev and next (or if one of them is absent, just the other (the same as XORing with 0)). The reason why you can still traverse an XOR linked list in both directions relies on the properties of XOR and the redundancy of information inherent in a double linked list.

---

Imagine you have three nodes in your XOR linked list.

A is the head, and has an unobfuscated pointer to B (B XOR 0, next only)

B is the middle element, and has the XOR of pointers to A and to C.

C is the tail, and an unobfuscated pointer to B (0 XOR B, prev only)

When I am iterating over this list, I start at A. I note A's position in memory as I travel to B. When I wish to travel to C, I XOR B's pointer with A, granting me the pointer to C. I then note B's position in memory and travel to C.

This works because XOR has the property of undoing itself if applied twice: C XOR A XOR A == C. Another way to think about it is, the doubly linked list stores no extra information a singly linked list does not (since it's just storing all the previous pointers as copies of next pointers somewhere else in memory), so by exploiting this redundancy we can have doubly linked list properties with only as many links as are needed. However, This only works if we start our XOR linked list traversal from the start or end — as if we just jump into a random node in the middle, we do not have the information necessary to start traversing.

---

While an XOR linked list has the advantage of smaller memory usage, it has disadvantages — it will confuse the compiler, debugging and static analysis tools as your XOR of two pointers will not be correctly recognized by a pointer by anything except your code. It also slows down pointer access to have to do the XOR operation to recover the true pointer first. It also can't be used in managed code — XOR obfuscated pointers won't be recognized by the garbage collector.

Answer 2

Let us consider the following XOR list

A->B->C->D

suppose you created nodes in this format below

Key|Link|

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

CASE #1:[Forward Traversal] Now Suppose you are in B (current_node=>B) want visit C , so you need Address of C . How you will get ?

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

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

CASE #2: [Backward traversal] Now Suppose you are in C (current_node=> C) want visit B , so you need Address of B . How you will get ?

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

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

Traversing: To traverse whole list ,You will need 3 pointers prevPtr , currPtr , nextPtr to store relative current, previous and next node's address starting with head. Then in each iteration these pointers need be move to one position ahead.

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; }