Memory efficient Doubly Linked List – XOR Linked List

By Pritam
Apr 3rd, 2012
0 Comments
2526 Views
Memory efficient Doubly Linked List
Have you ever realized what is at the core of internet? Any guesses? Yes it is data and information. Large and large chunks of data is created or edited or deleted every moment throughout the internet. Now the main point which arises here is how this data is stored during program execution and then transferred. For now let’s focus on data storage. Various data structure (a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently, wiki definition), simple or complex, are there, to choose from, to store data during program execution. Generally data structures are used according the need of the moment but few data structures are very well suited for a particular application like List is used to store list of objects or Hash Table is used for compiler implementation and so on. 
In this tutorial we will look at a special kind of list, Doubly Linked List
Node Definition
typedef int T;
typedef struct listNode {
 T elm;
 struct listNode * previous;
 struct listNode * next;
 };
 
Conventional Doubly Linked List

Conventional Doubly Linked List

This list, as many of you already know, requires 2 pointers to store the reference of previous and next node. Thus to store one data item we need to store 2 pointers and 1 data value or we can say that to store one data value we are wasting twice as much memory as was actually useful for us. Whenever a system is designed memory and the execution time are the two parameters based on which design decisions are made. To solve memory issue Prokash Sinha proposed a memory efficient doubly linked list whose node definition is as follows: 
Node Definition
typedef int T;
typedef struct listNode{
 T elm;
 struct listNode * ptrdiff;
 }; 
The above node definition shows memory efficient version of the Doubly Linked List using one space for address field for every node. This memory efficient Doubly Linked List is called Memory Efficient Linked List or XOR Linked List as the list uses bitwise XOR operation to save space for one address. 

In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes. By definition previous node of StartNode is null and next node of LastNode is also null.

Below is the chart showing a XOR Linked List

Memory effiecient Doubly Linked List - XOR Linked List

Memory effiecient Doubly Linked List - XOR Linked List


For above example, using our definition of XOR Linked Lists we can say that:

The ptrdiff pointer of A contains -> NULL ⊕ A


The ptrdiff pointer of B contains -> A ⊕ C
The ptrdiff pointer of C contains -> B ⊕ D
The ptrdiff pointer of D contains -> C ⊕ NULL
So now how do we travel to and from in the above data structure. How XOR Linked list actually solve our memory related problem?
Properties of ⊕ :

A ⊕ A = 0

A ⊕ O = A

A ⊕ B = B ⊕ A (Symmetric)

( A ⊕ B ) ⊕ C = A ⊕ ( B ⊕ C ) (Transitive)
Now suppose we are on node B and we want to move on to Node C. We have to perform the following operation:
The Pointer difference at Node B is A ⊕ C.
Now taking XOR of the above pointer difference with address of A we will get reference to C,
A ⊕ (A ⊕ C) = (A ⊕ A) ⊕ C = O ⊕ C = C
Similarly we can find the reference of node A.
Thus we can see in the above example that we can move back and forth in a linked list using just one pointer.
Basic operations on XOR Linked list:
1. Traversal:
The list traversal is the most important operation on a list as insertion in or deletion from list can be done only after successfully traversing the list. Traversal procedure is more or less equivalent to GetNextNode procedure. Let’s say we provide the StartNode to start traversing. Now we know that previous node of StartNode is null and we already have ptrdiff for the StartNode (XOR of previous node and next node). Thus taking XOR of null and ptrdiff we get address of next node (XOR property no. 1 ).
Code Snippet
typedef listNode * plistNode;
plistNode NextNode( plistNode pNode,plistNode pPrevNode){
    return ((plistNode)((int) pNode->ptrdiff ^ (int) pPrevNode));
}
2. Insertion
Algorithm to follow:
  • Traverse the list to the node where new node to be inserted.
  • We then place the node after this found node.
  • Because the next node has pointer difference, we dissolve it by XORing with the found node.
  • We then do exclusive XORing with the new node, as the new node would be its previous node.
  • Fixing the current node by following the same logic, we first dissolve the pointer difference by XORing with the next current node.
  • We then do another XORing with the new node, which provides us with the correct pointer difference.
  • Finally, since the new node would sit between the found current node and the next node, we get the pointer difference of it by XORing them.
Code Snippet
void insertAfter(plistNode pNew, T theElm){
   plistNode pPrev, pCurrent, pNext;
   pPrev = NULL;
   pCurrent = pStart;

   while (pCurrent) {
      pNext = NextNode(pCurrent, pPrev);
      if (pCurrent->elm == theElm) {
         /* traversal is done */
         if (pNext) {

            /* fix the existing next node */
            pNext->ptrdiff = (plistNode) ((int) pNext->ptrdiff ^ (int) pCurrent ^ (int) pNew);

            /* fix the current node */
            pCurrent->ptrdiff = (plistNode) ((int) pNew ^ (int) pNext ^ (int) pCurrent->ptrdiff);

            /* fix the new node */
            pNew->ptrdiff = (plistNode) ((int) pCurrent ^ (int) pNext);
            break;
      }
      pPrev = pCurrent;
      pCurrent = pNext;
   }
}
Thus we see that a memory-efficient implementation of a doubly linked list is possible to have without compromising much timing efficiency. A clever and better design would give us a canonical set of primitive operations for both implementations, but the time consumptions would not be significantly different for those comparable primitives.

About the Author

- Co-Founder of IdleBrains, is software Engineer by profession with expertise in .NET technologies and data structures. An avid reader and writer, loves to keep himself well versed with new technologies. When not working can be found on Badminton court or chatting with friends. Among other hobbies, loves to listen old hindi numbers of Kishore Kumar and Mukesh.

Leave a Reply

Your email address will not be published. Required fields are marked *

facebook comments: