Make delicious recipes!

Storing a doubly linked list using space of only one pointer in each node


If every node had 2 pointers: prev and next and we XORed them to a variable called xorPtr, then its easy to get prev = (next XOR xorPtr) and similarly for next pointer.


So, if we store the xorPtr only at each node, then we just need to keep track of prev pointer while traversing the list. Using prevPointer and xorPtr, we can get the next pointer.


The solution is efficient but not widely used in practice because:

1) It makes debugging difficult

2) Automated tools that may be traversing a list will not work.

3) If there are pointers to some nodes in the list from other places in the code, they cannot be used to traverse the list in any direction because the prev or next pointer would not be available then.

4) In modern systems, memory is not so much of a constraint, so generally saving memory in this way is not recommended.




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal