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.
|Email:||(Your email is not shared with anybody)|