XOR Linked List

Today was fairly slow at work so when Walter messaged me on gchat I responded. Having just finished App Academy Walter is very up to date on the most efficient data structures, and had apparently spent the morning researching xor (exclusive or) linked lists. I am currently taking an evening class in data structures so when he messaged me to try and teach me about them I was interested to hear more. In fact, my professor had mentioned them, but not demonstrated an implementation. 

To understand xor linked lists we need to understand the problem they solve. Suppose you're super memory constricted and want a linked list you can traverse both forward and backward, but with only one extra reference rather than the prev and next references typical of doubly linked lists. That's where xor linked lists come in; one reference at each node containing information for both next and previous.

As indicated in the name, the crucial part of this is the xor operator (^ in javascript) which returns the higher of two values if they are different, and zero if they are the same. So when xoring two 16 bit ints, 00000000000000001^00000000000000010 = 00000000000000011. This means 1 xor 2 = 3, and as Walter told me to do, you can check this in the javascript console of your web browser with 1^2. Walt also informed me that because xor is lossless, 1^2 =3, 1^3 =2, 3^1 = 2, 3^2 =1 ... and so on for all permutations of the three numbers.

(Before I really get into it here's some notation I just invented, this won't hold true elsewhere, but in the following, {} is a variable resulting from the xor operation and anything in [] is an object storing our node data and the previously mentioned variable.)

Now think for a moment that this property of xor holds true for everything, not just numbers in bitwise format. Think if we had [null], [1], [2], [3], [4], [null] as our example list, and {[null] xor [2]} stored in node [1], {[1] xor [3]} stored in node 2, and so on, where the objects being xor'd are actually addresses in memory! Then given the information [null], [1], {[null] xor [2]} we can take {[null] xor [2]} xor [null] to get the memory address that [2] is stored in. We can now drop [null] and store [1], [2] in memory. In [2] we'll also find the value for {[1] xor [3]}, and by taking {[1] xor [3]} xor [1] we will find the address for the value after [2] is [3]. 

Continuing this pattern we could traverse the whole tree. In all we would need to store four nodes of information, our first two and last two, then use the above pattern to traverse the list forward or backward. I did some googling and there are a few problems with this technique. First it's pretty risky in Java, where you cannot access memory directly and are liable to have your unreferenced objects get gc'd. Also, it apparently really messes with debuggers and makes it hard or impossible to step through code. Finally, memory is cheap, this is a data structure I could see used in some kind of controller with little memory, but not a modern desktop or laptop.

I know this was a long post and probably difficult to read, but thanks for reading anyways. Future posts will be much less daunting, and there will probably be days where I post something like "I'm hungover and learned that naps are great". Thanks to Walter for having sparked this post, check out his github.