Efficient Doubly Linked Lists

Every node in a Doubly Linked List consists of two pointers - one pointing towards the next node and another pointing towards the previous node.

 ...  A       B         C         D         E  ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

We can reduce the memory of this list by using an XOR Linked List, represented as follows:

 ...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

As you can see in the figure above, every node stores the XOR of the address of its previous node and the address of its next node, i.e.

link(B) =  address(A) ⊕ address(C)

To traverse the list, we need to XOR the current link with the address of the previous node (explained below)

 i.e.  addr(D) = link(C) ⊕ addr(B)
    where
          link(C) = addr(B)⊕addr(D)
     so  
          addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
      
          addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
    since 
           X⊕X = 0                 
           => addr(D) = 0 ⊕ addr(D)
    since
           X⊕0 = x
           => addr(D) = addr(D)
    The XOR operation cancels addr(B) appearing twice in the equation and all we are left with is the addr(D).

Note:

This method might create some problems in deletion of nodes or in certain other operations, and the code might become slightly difficult to understand, initially.

The method is elegant, nonetheless.

( Source: Wikipedia! :) )