Xor linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation to decrease storage for doubly-linked lists. An ordinary doubly-linked list stores addresses to the previous and next list items, requiring two address fields in each list node:
... A-1 A B C C+1 ...
<– prev <– prev <– prev <–
–> next –> next –> next –>
An Xor linked list will compress the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field:
... A-1 A B C C+1 ...
–> A-1 XOR B <–> A XOR C <–> B XOR C+1 <–
When you traverse the list from left to right: supposing you are at B, you can take the address of the previous item, A, and XOR it with the value in the XOR field. You will then have the address for C and you can continue traversing the list. The same pattern applies in the other direction.
To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction.
Most authorities no longer recommend using this particular trick for the following reasons:
- general-purpose debugging tools cannot follow the XOR chain, making debugging more difficult;
- except in some embedded systems, RAM storage has become cheap, making the trick less necessary; and
- conservative garbage collection schemes do not work with data structures that do not contain literal pointers.
A more practical and effective approach for decreasing the storage used by linked lists are unrolled linked lists.
See also
