Sunday, 13 October 2013

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)
          link(C) = addr(B)⊕addr(D)
          addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
          addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
           X⊕X = 0                 
           => addr(D) = 0 ⊕ addr(D)
           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).


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! :) )