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:
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:
TwoWay_SinglePtr(List,Start,End,Value,PrevValue)
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
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:
- There are two pointers START & END, START contains the Address of 1st Node, and END Contains Address of Last Node.
- 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.
- 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:
TwoWay_SinglePtr(List,Start,End,Value,PrevValue)
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
Here in this I am assumeing that innitially PrevNode pointer is 0 rather than null for explaining, simmilarli next2nextNode pointer (tempPtr) is 0.
ReplyDeleteso that I have not put any null condition for these pointers..
These assumptions were made for explaining purpose
Why can't we implement a single list with stack traversal.. we know random access isn't allowed in lists, hence store only the next addresses, and keep storing the previous addresses in the stack.
ReplyDeleteAlthough an overhead of an extra data structure would be present in this case
Hi Abhay,
DeleteIf you implement the 2way linked list by storing previous pointer in the stack, in that case actually you are doing nothing just shifting the pointer to the stack, and for traversing you will require an extra pointer and stack, which will be extra overhead as well as wastage of memory. Our main motive of implementing 2 way linkedlist with single pointer is to save memory, which is not there in your implementation.
Whereas, in above implementation, only overhead part is XORing of pointers, which will be very fast at assembly level.
And above implementation is valid only at assembly level, since no high level language allows oprations on pointers (except "-" in C).