Implement Doubly Linked List with single pointer field in its Node

Hi folks,
During interview of BARC I was asked a very interesting question i.e. "Can we implement Doubly Linked List by using single pointer, How if yes?".
So here I am trying to explain you the concept of the implemetation of Doubly Linked List (Two Way Linked List) by using Single pointer.

Before going in to the concept we must understand what is Doubly or Two way Linked List.
A Doubly Linked List has following attributes:
  1. There are two pointers START & END, START contains the Address of 1st Node, and END Contains Address of Last Node.
  2. Each node of the list contains 2 pointer (NEXT, PREV) and 1 data part. NEXT contains the address of next node and PREV contains address of previous node.
  3. PREV of 1st node & NEXT of last node will contains null values.

Algorithm for Insertion of node in Two way linked list using single pointer field


Concept: In 2way linked list with single pointer, each node consists of 1 data part and 1 pointer part. The pointer part will now contain XOR of the address of Previous and Next Node. Reason behind using difference XOR is, if XORing for A and B gives C then XORing of C with A gives B and XORing of C with B gives A as result, So that it is easy to find Next Node's Address by using XOR with stored values.
List: It is actually the list in which Node is to be inserted.
START: Pointer contains the address of Starting Node.
END: Pointer contains the address of Ending Node.
Node: Node which is to be inserted.
Curr: Pointer pointing the current node, this will be used to traverse the list
Prev: Pointer pointing the Previous node
Value: Value of a Node after which new node is to be inserted
NextNode: this will contain address of the node which is next to current node
N_NextNode: this will contain address of Node which is next to NextNode.