Belated Valentine's Gift for Programmers

These days I’m about as deep into the web world as it gets, but I have some nuggets of C/C++ awesomeness still trapped in my head. If you program with these languages, and you’re looking to snag a job, I've absolutely turned heads during Microsoft & Google interviews by describing the following technique:

It’s possible to maintain a doubly linked list using only one pointer per node (normally, a doubly linked list requires two: prev & next).

If you think you can puzzle this out, by all means stop reading right now, and flex your brain a bit, it’s a neat problem.

The trick involves using a bit-wise XOR operator to encode BOTH prev  & next into the single pointer variable in each node (Let’s call that variable prevXORnext). In order to go to forward in the list, you need only XOR the current node’s prevXORnext with the pointer of the previous node you were on. (This means you’ll need to wrap the linked list w/ a lightweight iterator class that maintains the current node’s pointer, as well as a pointer to the node you were previously on). To go “backwards” calculate the next node’s pointer, then set the iterators “last node” to that value, and XOR again with current to reverse direction. Insertion involves modifying the XOR values of the two neighbor nodes, and setting the new node’s prevXORnext to their addresses XOR'ed.

I encourage you to actually implement this before dropping it in an interview; it absolutely works, and the common traversal/insertion/deletion cases are obvious, however there are a fair number of corner cases on and below n=3.

Happy Valentine’s Day, hackers!

(Attribution: I learned this trick when I was an Intern at NuMega /* makers of SoftICE */ from the legendary (to me) hacker, Andy Wilson. Implementing this as a young teen was definitely a programming high-point)