Skip to interview prep
Apexed

113. How does an XOR (memory-efficient) doubly linked list work?

HardLinked lists

Technical
Show model answer

Instead of storing separate prev and next pointers, each node stores `link = address(prev) XOR address(next)`. When traversing, you know the address of the node you came from, so `next = link XOR prev` recovers the next address; traversal works in both directions starting from either end. This halves pointer storage per node.

The costs: you cannot jump into the middle of the list and move from there without knowing a neighbour, deleting a node given only its address is impossible without the neighbour, debuggers and garbage collectors cannot follow the disguised pointers, and garbage-collected languages like JavaScript, Python or Java do not expose raw addresses. It is a curiosity for memory-constrained C code rather than a common practical choice.

How does an XOR (memory-efficient) doubly linked list work — Data structures & algorithms interview question — Apexed