XOR Linked Lists: One Link Field for Both Directions

A doubly linked node stores two addresses, one to each neighbour, and a traversal moves by reading one of them. The two addresses are not independent: from the current node, the successor is known and the predecessor is needed only to go back. If the node stores the bitwise exclusive or of the two, then a cursor that already knows one neighbour can recover the other by a single XOR. The field count drops from two to one, and the structure still traverses in both directions.

The trick is old and appears in the exercises of Knuth’s treatment of linked allocation, where it is presented as a memory-saving variation on the doubly linked node. It is more instructive as a study in what a representation costs than as a technique to deploy. It saves one machine word per node, and it breaks pointer validity, debugging, and the ability to unlink a node without knowing a neighbour.

The arithmetic

Let L be the predecessor address and R the successor address. The node stores L XOR R. A cursor walking forward holds the address of the previous node, so it knows L for the current node and computes:

stored   = L XOR R
stored XOR L = R

The same operation recovers L from R when walking backward. XOR is its own inverse, so one operator serves both directions, which is why the technique needs no direction flag. With a null-terminated list, the ends also have to be distinguished: the last node stores prev XOR 0, which equals the address of its predecessor, and a traversal leaning on that arithmetic will not see a terminator.

The C implementation needs the addresses as integers, because XOR on pointers is not defined by the standard. Converting a pointer to uintptr_t is defined if the type is wide enough, and converting back is defined for the round trip. The intermediate value is an integer that is not a valid pointer, which is the crux of every problem with the structure.

#include <stdint.h>

struct xnode {
    int value;
    uintptr_t link;    /* (uintptr_t)prev ^ (uintptr_t)next */
};

struct xlist {
    struct xnode *head;
    struct xnode *tail;
};

static void insert_front(struct xlist *l, struct xnode *n) {
    n->link = (uintptr_t)l->head;               /* prev is NULL, so link = next */
    if (l->head) {
        /* old head's prev becomes n: new_link = n ^ old_next */
        l->head->link = (uintptr_t)n ^ l->head->link;
    } else {
        l->tail = n;
    }
    l->head = n;
}

Note the update to the old head: its stored value was NULL XOR old_next, and after the insertion its predecessor is n, so the stored value must become n XOR old_next. Rewriting it requires the old value, which is why the expression reads n ^ old_link rather than recomputing from neighbours.

Traversal carries two cursors:

void walk(const struct xlist *l) {
    struct xnode *prev = NULL;
    struct xnode *cur = l->head;
    while (cur) {
        struct xnode *next = (struct xnode *)(cur->link ^ (uintptr_t)prev);
        /* visit cur */
        prev = cur;
        cur = next;
    }
}

The correctness condition is that prev is genuinely the predecessor of cur at every step. Starting from head with prev = NULL works because the head’s stored value is NULL XOR next. Starting from any other node requires knowing one of its neighbours, which is the whole design.

What the saving actually is

For a 4-byte payload on a 64-bit target, the plain doubly linked node is 24 bytes and the XOR node is 16 bytes, a saving of one third. For a 64-byte payload the plain node is 80 bytes and the XOR node 72 bytes, a saving of one tenth. The saving is always one machine word, and its relative value falls as the payload grows.

Compare against the singly linked node, which is also one link field. The XOR list is not smaller than a singly linked list; it is the same size and supports backward traversal. That is the accurate framing: the XOR list buys bidirectionality at the storage cost of unidirectionality, by paying a compute cost and a correctness cost instead.

The compute cost is one XOR and one integer-to-pointer conversion per hop. On any modern processor that is one cycle of arithmetic on a dependency chain that is dominated by the load latency, so it is effectively free. The correctness cost is not.

Why it breaks in practice

Four problems make the technique rare in real code, and each is a consequence of storing a value that is not a valid address.

Garbage collectors and tracing tools cannot follow the chain. A collector that scans memory for pointers will not find the links, because the stored value is not a pointer to anything. A conservative collector will not retain the nodes, and a copying collector cannot update the links without knowing the traversal state. The structure is therefore restricted to manually managed memory or to a runtime with precise, type-aware scanning that understands the encoding.

Debuggers and sanitisers cannot walk it. A watchpoint on the link field shows an integer with no meaning. A memory error detector cannot tell which node a link refers to, so it cannot validate the access. Leak detectors that traverse the heap by following pointers will not see the chain at all.

Unlinking needs a neighbour. Removing a node requires updating the two neighbours’ link fields, and each update needs the value of the other neighbour. Given only the node’s address, the operation is not possible; the caller must hold a cursor with a known predecessor. This is the same limitation as the singly linked list, and it removes the main practical advantage of a doubly linked layout.

It is undefined in languages without integer-pointer conversion. The C standard defines the round trip through uintptr_t when the type is wide enough, but the value is not a pointer and dereferencing it is not permitted. Languages with moving garbage collectors and no integer representation of references, such as Java or Go without unsafe, cannot express the encoding at all. Rust can express it with usize casts inside unsafe, and the same caveats apply.

There is a fifth, subtler problem: the stored value is a difference of two addresses, not an address, so a cycle in the chain does not show up as a pointer that reappears. A cursor walking by the documented rule stops when it reaches the sentinel, and no value comparison on the link fields identifies the point at which the walk has gone wrong.

Null neighbours and sentinel rings

The XOR encoding has a specific interaction with the ends of a list that is easy to get wrong. If the list is null-terminated, the head stores NULL XOR next, which equals next. The head’s link field is therefore a valid pointer, and reading it without the XOR step yields the successor by accident. Code that does so works for the head and fails on the next hop.

The correct discipline is that every read of the link field goes through the XOR with the known neighbour, including the first. Code that special-cases the head to avoid the XOR is relying on the coincidence that 0 XOR x == x.

For a circular list with a sentinel, the sentinel’s link is last XOR first, which is neither neighbour unless one of them is null. A traversal starting at the sentinel must therefore know one of them, and the usual choice is to start at sentinel->next with prev = sentinel. This is exactly the same cursor discipline as the null-terminated case, and it is why the encoding composes poorly with the sentinel simplification described in Doubly Linked Lists and the Sentinel Header: the sentinel removes branches but the XOR encoding reintroduces the need to track a cursor.

Where the encoding does pay

The technique is defensible in a narrow set of conditions, all of which are about memory that cannot be spent.

Fixed-budget embedded structures. A structure with a hard limit on RAM per element, where the elements are numerous and small, gains a proportion worth having. A 4-byte payload in a 16-byte XOR node uses two thirds of the 24-byte plain layout, which can be the difference between fitting a microcontroller’s SRAM and not.

Read-only or append-only chains. If the structure is built once and traversed many times, the unlink limitation does not arise. The encoding then costs nothing but the cursor discipline, and the traversal code is a small, testable loop.

Structures already requiring custom traversal. If the consumer walks the chain with its own cursor logic, as a file system walking a block chain does, the extra cursor state is already present. The encoding then saves a field without adding an interface constraint.

Outside those conditions the plain doubly linked node is the better default. One machine word per element is usually a smaller cost than the loss of tooling, and the tooling is what finds the bugs that the extra field would have prevented.

Relation to other compressed links

The XOR trick is one of a family of link encodings that trade a stored address for a computable one. Storing the difference next - prev rather than the XOR gives the same storage with different arithmetic and the same tooling problems. Storing an index rather than an address, described in Index-Based Linked Lists, keeps the value meaningful and relocatable but still is not a pointer. Storing a 32-bit offset from the node to its successor is a compression that works when the structure is smaller than 4 GiB and preserves the ability to convert to a pointer by addition.

Each of these trades one machine word, on a 64-bit target eight bytes, for a conversion at every access. The XOR variant is the only one that requires the traversal to carry state, which is why it is the least used of the family despite being the most elegant. The general principle is worth keeping: a link is information, and information can be stored in any encoding. The engineering question is always whether the encoding survives contact with the tools that inspect memory.