Siklossy's List

Surprisingly I didn't find much information about siklossy's list on the web so I decided to write a little introduction here. The idea is to create a double linked list using just one pointer for the next and the previous elements but without loosing pointer combinations, this is, without loosing the number of directions able to store. Okay, this sounds impossible but it is not!

Let take a look at the binary exclusive or operator (represented by '+' since it's the binary addition with no carry).

Definition:

+01
001
110

The interesting property here is:
(x+y)+x=y
With 'x' taking either true or false. And 'y' taking either true or false.
Note that without braces this continue to be true (associative property) and also changing the order (commutative property).
So, how do we express an ordinary double linked list:

double linked list
using just one pointer to store the next and previous values (as shown below)?
Siklossy's List

Lets take Z element, for example, and lets say that &x is the address of x.
The trick is to store in Z's pointer the value of &Y+&T. So then if we are in Z coming from Y we just need to calculate &Y + the value stored in Z pointer to get &T value. And likewise if we come from T we just need to calculate the value of Z pointer + &T to get &Y.
The constraint that we have regarding an ordinary double linked list is that we need to know the addresses of two consecutive elements to start walking through the list (instead of one) and we need a small extra time to compute the '+', but we save one pointer for each node.
To make this clear, let see it with actual numbers:
Suppose that:

X is stored at the address 0100
Y is stored at the address 0110
Z is stored at the address 1101
T is stored at the address 0101
M is stored at the address 1011

What value should X pointer have?
Since it's the first element of the list, we can operate it with an imaginary previous element address 0000. Let's see if this is useful:
X pointer will be:
0000+ &Y= 0000+ 0110= 0110= &Y
So when starting, we just need to operate with 0000 or just go to where first element pointer is pointing, since for any 'x':
x + 0 = x

What value should Y pointer have?
&X+&Z=0100+1101= 1001

What value should Z pointer have?
&Y+&T=0110+0101=0011

What value should T pointer have?
&Z+&M=1101+1011=0110

What value should M pointer have?
As when starting we can use an imaginary next element or just remember that for first and last elements we operate against 0 with is the same as not operating, so:
M pointer = &T+0000 = &T = 0101

So finally the list is:


Siklossy's List with addresses