How to implement a double linked list with only one pointer?
algorithm, data-structures
Solution
This sounds as if it's impossible, the way it's stated. You can't implement two pointers using only one, in general.
You might be able to squeeze two 16-bit offsets into the space used by the single (assumed 32-bit) pointer, or some other "clever hack", but in general this sounds impossible.
This article describes a trick based on XOR:ing the pointer values, but I would consider that a hack (it does bitwise arithmetic on pointer values).
Problem
How to implement a double linked list with only one pointer? It takes O(1) time to find the prev and next Node. ``` struct Node { int val; Node* p; }; ```