algorithm - you - How exactly does a XOR Linked list work?




xor linked list youtube (4)

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

No - it uses about half the space, as the size of the result of XOR-ing the "prev" and "next" is equal to the size of the larger of the two.

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?


Double linked list needs 2*N pointers stored for N nodes, plus at least one additional pointer(head, or perhaps head and tail).

XOR linked list needs N pointers stored for N nodes, plus at least two additional pointers (head and last visited node, or perhaps head and tail and last visited node). While traversing, you store one node (the last visited node), but when you go to the next node, you rewrite that with the now-previous node's address.


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

XOR has a very special property about it, namely, given a XOR b = c, only two (any two) of the variable are required to compute the the third, with some restrictions. See the XOR swap algorithm for why this works.

In this case the previous (or next) pointer must still be carried, but only through traversal calculations and not as a seperate member.





algorithm