Doubly Linked List with Space Complexity of Singly ?

Sounds weird and ill-logical isn’t it :)

Its not new, neither my own idea. Thought of sharing it with C++ code to show the power of XOR.

This non-destructive operator (XOR) is of tremendous use and amazing.

With a linked list the major concern is the space consumed by an extra pointer in the structure.

For singly linked list, there is one extra pointer in each node to point to the next node to help traversing it.
In doubly linked list, there are two extra pointers in each node, one point to the previous node and the other point to next node to help traversing in backward and forward direction respectively. This is one of the advantage of Doubly over Singly.

Now depending upon the machine’s word size, if it is 32 bit, the pointer consumes 4 extra bytes and in 64 bit machine it consumes 8 extra bytes. Which is quite a bit. Think of a list which has smaller data size than actual pointer size. Overhead is huge.

What if we get the advantage of Doubly Linked List traversal in both the direction in Singly Linked List wihout using an extra pointer in every node ?

Rememer we always traverse in the linked list to reach to a particular node in O(n) complexity. Therefore, this extra 1 pointer which we use to XOR with the node’s next pointer also moves along with each traversal.

Lets see how to use XOR to traverse in both the directions.

I have written a code in C++ to demonstrate.

<script src=”https://gist.github.com/sisingh/9b68efcdcac0124b375ae0ac52a50ada.js"></script>

#include <iostream>
using std::cout;
using std::endl;
template < typename TYPE >
class NODE {
public:
NODE() {
next = NULL;
}
NODE(const TYPE data) : data(data), next(NULL) { }
TYPE getData() {
return data;
}
NODE * getNext() {
return next;
}
void setNext(long next) {
this->next = reinterpret_cast<NODE *>(next);
}
private:
TYPE data;
NODE *next;
};
template <typename TYPE>
class LIST {
public:
LIST() {
XORdata = head = tail = NULL;
}
void add(TYPE data);
void traverseForward();
void traverseBackward();
private:
NODE<TYPE> *head;
NODE<TYPE> *tail;
NODE<TYPE> *XORdata;
};
template <typename TYPE>
inline
void LIST<TYPE>::traverseBackward() {
NODE<TYPE> *tempTail = tail;
NODE<TYPE> *tempTail1 = tail;
NODE<TYPE> *tempXOR = XORdata;
while(tempTail) {
cout << “Data : “ << tempTail->getData() << endl;
long p1 = reinterpret_cast<TYPE> (tempTail->getNext());
long p2 = reinterpret_cast<TYPE> (tempXOR);
tempTail = reinterpret_cast<NODE <TYPE> * >(p1^p2);
tempXOR = tempTail1;
tempTail1 = tempTail;
}
}
template <typename TYPE>
inline
void LIST<TYPE>::traverseForward() {
NODE<TYPE> *tempHead = head;
NODE<TYPE> *tempHead1 = head;
NODE<TYPE> *tempXOR = NULL;
while(tempHead) {
cout << “Data : “ << tempHead->getData() << endl;
if (!tempHead->getNext()) break;
long p1 = reinterpret_cast<TYPE> (tempHead->getNext());
long p2 = reinterpret_cast<TYPE> (tempXOR);
tempHead = reinterpret_cast< NODE<TYPE> * >(p1^p2);
tempXOR = tempHead1;
tempHead1 = tempHead;
}
}
template <typename TYPE>
inline
void LIST<TYPE>::add(TYPE data) {
if(NULL == head) {
tail = head = new NODE<TYPE>(data);
} else {
NODE<TYPE> *temp = new NODE<TYPE>(data);
long p1 = reinterpret_cast<TYPE>(XORdata);
long p2 = reinterpret_cast<TYPE>(temp);
tail->setNext(p1^p2);
XORdata = tail;
tail = temp;
}
}
int main(int argc, char **argv, char **arge) try {
LIST<long> list;
for(int i = 1; i < 16; ++i ) {
list.add (i);
}
cout << “Forward Traversal “ << endl;
list.traverseForward();
cout << “Now moving backward !!!” << endl;
list.traverseBackward();
return 0;
} catch(…) {
cout << “Uncaught exception!” << endl;
}

Enjoy…