Doubly-Linked Lists

Doubly Linked Lists

I was reading this article the other day and thought I should share its contents. It's quite interesting. It has the notion of using one pointer to construct a doubly linked list of nodes. It copies the notion of the XOR-swap described in a previous article.

   x ^= y ^= x ^= y;

However, we don't need to swap, but only hold the XOR value of x and y, namely the value of

   x ^ y

Therefore, we can have one pointer hold the XOR of the prev and next nodes. And to extract the previous, you XOR the combination with the next node, and vice versa to extract the next node. This quite simple, but effecient. Also, when assigning a new value for this one pointer that holds the XOR-combination, you need to remove one of the two and replace it with a new value. The code below follows:

   #ifdef __BIT_32_REGISTER__
      #define XOR(a,b) ( (typeof((a))) ((unsigned)(a) ^ (unsigned)(b)) )
   #else  /*__BIT_64_REGISTER__*/
      #define XOR(a,b) ( (typeof((a))) \
       ((unsigned long long)(a) ^ (unsigned long long)(b)))
   #endif

   initial XOR setup:
   node->onePointer = XOR(prev,next);

   // since we know that onePointer always holds 
   // prev ^ next of the current node, we can just XOR
   // out the prev or next value:
   // 1.) let's replace the previous node with a new prev
   node->onePointer = XOR(node->onePointer,XOR(oldPrev,newPrev));

   // 2.) let's repalce the next node with a new next node
   node->onePointer = XOR(node->onePointer,XOR(oldNext,newNext));

Therefore, now we know what the single pointer should hold. And since it holds the XOR combination, we can XOR it with the prev (that's supposed to have been set with the next to come up with this XOR combination value, meaning onePointer ^ prev will remove prev, and will evaluate the value to just "next" within the XOR combination value) to remove it, and vice versa with the next pointer.