XOR doubly linked list
Since a couple of days I’ve been working hard on the new Al Zimmermann’s Programming Contest: Cards (also called Topswops).
The challenge
The idea is very easy, you take a series of numbers, from 1 to N. You shuffle the numbers around, for example:
- 5,3,1,2,4
Now we reverse the amount of numbers as stated by the first entry in the list. So in this case we reverse 5, and we get:
- 4,2,1,3,5
We keep doing this, now reversing 4:
- 3,1,2,4,5
- 2,1,3,4,5
- 1,2,3,4,5
At this point, 1 is in front, we are done! No more reversals are possible.
The problems
When implementing this the first thing I did was to create an array and reverse parts of the array by swapping the items around. The problem is that the amount of swaps is pretty big!
So I started thinking about other ways to save the numbers in this challenge.. how about a linked list? This won’t work because when updating the linked list you’ll have to reverse all the pointers in the part you are reversing.
So how about using a doubly linked list? This won’t work because we have to swap the next/previous pointers for all the nodes we reverse.
XOR doubly linked list
Then I learned about the XOR doubly linked list. Let me explain how it works. The idea is that you don’t have next and previous pointers, but you just have one pointer. This pointer is both the next AND the previous pointer! How is this possible you might ask?
Well, this is where the XOR comes into play. Lets do a tiny bit of math:
A ^ B = C
Now:
C ^ A = B
C ^ B = A
A property of the XOR is, if we have one value, we can calculate what the other value is!
When we create the list we XOR the next and previous together, and we save the pointer to the first element in a seperate pointer. Lets say A = previous, B = next, C = stored value:
- previous ^ next = stored value
- stored value ^ previous = next
- stored value ^ next = previous
If we traverse our XOR doubly linked list we know the current element and the one before that (previous), so we can always calculate the pointer to the next element!
The advantages
So why would we do this? It involves a bit more processing power and will obviously save you half of the pointer-memory compared to a normal doubly linked list. We now keep one XOR-ed value instead of two pointers.
But there is another great advantage which might be usefull in the competition I mentioned above, reversability! As stated above using a doubly linked list wasn’t helpfull because when we reverse a part all the previous and next pointers have to be swapped. But we don’t have these pointers anymore, they are XOR-ed into one value! That means that we don’t have to change anything!
Lets assume we have a list of 80 items, and we want to reverse the first 40, what do we need to do now?
- Traverse to the 40th element
- Adjust the value of the 40th pointer, now the first element:
TERMINATOR ^ (PTR TO 39) - Adjust the value of the 1st pointer, it must have
(PTR TO 2) ^ (PTR TO 41) - Adjust the value of the 41th pointer, it must have
(PTR TO 1) ^ (PTR TO 42) - Pointer to the first element is now 40 (this has become our first element)
Done! We have adjusted three pointers and nothing in the middle. B.t.w. TERMINATOR is a value which indicates the boundaries of the first and last elements, I’ve used -1 for this. When traversing we use this to check if we are done.
Lets traverse the above reversed list, first we go to the first element (40) and perform the following XOR:
- stored_value (40) ^ TERMINATOR = next (39)
This will result in 39, now we continue:
- stored_value (39) ^ previous (40) = next (38)
- stored_value (38) ^ previous (39) = next (37)
- …
- stored_value (2) ^ previous (3) = next (1)
- stored_value (1) ^ previous (2) = next (41) !!
- stored_value (41) ^ previous (1) = next (42) !!
- stored_value (42) ^ previous (41) = next (43) etc etc
It works!
A bit of dissapointment
After implementing this it doesn’t seem to be faster then using swaps to reverse everything in the whole array. This is probably due to a couple of things:
- The locality of a normal array is faster in memory
- You’ll have to traverse N-nodes to reach the target to reverse
- The competition has max 97 elements, this might be too small to see the advantage
My algorithm until now only used a single pointer to keep track of the first element, but it might be usefull to also keep a pointer to the last element. For example if we need to reverse everything up to N-1, I need to traverse from 1 to N-1. But if you have a last-element pointer, using the doubly in the XOR doubly linked list, we can just go backwards from N.
Ah well, it might not have been usefull (yet?) but it is a beautiful algorithm!