XOR Doubly-Linked List

A neat idea I learned today:

You can make a doubly-linked list that only needs to store a single pointer – the xor of the prev and next pointers – to allow traversal of the list from either direction.

When moving forward we xor current ptr with prev. Moving backward xor with next to get prev. That it. How do we get prev/next for xor? The only way to get in the middle of the list is using iterator. Which can hold one extra pointer. For the first/last nodes extra pointer is NULL.

— numba888 on Hacker News

This concept has a Wikipedia page.