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.

As shown Doubly linked list above in the figure, we can traverse the List either way. Now we have to make an algorithm to Create a list simmilar to the above but there will be only 1 pointer part for each node.

Concept of 2way Linked list with single pointer:


Concept: In 2way linked list with single pointer, each node consists of 1 data part and 1 pointer part. The pointer part will now contains 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.

Here 4 cases are possible which are as followed

1. New node is Starting Node: In this case only pointer field of Start and End will be updated which will point the new node.

2. New node is at 2nd position: As our logic [pointer] part of node will be containing XOR of previous and next node. In this case we will have to update the pointer part of the 1st node, since there are no previous node for the 1st node so that [pointer] part of the 1st node will be containing the address of the 2nd node.

3. New node is at the middle of the list: In this case if CurrNode is the node after which we are inserting the new node, PrevNode contains address of the previous node to current node, NextNode contains address of Next node to the CurrNode and Node is the New Node which is to be inserted, then following steps will be taken..

                                   tempPtr = NextNode->Ptr XOR CurrNode
                                   NextNode->ptr = tempPtr XOR Node
                                   Node->ptr = NextNode XOR CurrNode
                                   CurrNode->ptr = PrevNode XOR Node

 4. New node is at the End of the List: In this case if CurrNode  is the current end node of the list PrevNode is the Previous node of the CurrNode, then following steps will be taken..
                                  Node->ptr = End
                                  CurrNode = Node XOR PrevNode
                                  End = Node