Xor linked list
Xor linked lists are a curious use of the exclusive disjunction binary operation. While an ordinary (doubly) linked list will store addresses to the previous and next list items, requiring two address fields in its data type:
A-1 ... A B C ... C+1
<- prev <- prev <- prev <-
-> next -> next -> next ->
an Xor linked list will store the same information in one address field thus: the XOR-value of the address for previous and the address for next is stored 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: in B, you will 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, because it is:
- difficult to debug, and
- no longer as necessary because of cheap RAM storage, and
- prevents most garbage collection schemes from working since there are no valid pointers in the data structures.
