XOR Linked Lists

July 2026 · 17 min read

A doubly linked list stores two pointers per node, prev and next, so it can be walked in either direction. The XOR linked list asks: can we get bidirectional traversal from one pointer-sized field? The answer is yes, through a bit trick that is genuinely clever — and the more interesting lesson is why, despite working, it is almost always the wrong choice. This post builds it correctly and then dismantles the case for ever shipping it.

One Field Instead of Two

Each node in a doubly linked list carries two 8-byte pointers on a 64-bit machine: 16 bytes of links per node. The XOR trick collapses them into a single field, conventionally named npx ("next-prev-xor"), holding the bitwise XOR of the two neighbour addresses:

npx = addr(prev) XOR addr(next)

That is 8 bytes instead of 16 — the pointer overhead is halved. The end nodes use the null address (numeric 0) for their missing neighbour, so the head stores 0 XOR addr(next) and the tail stores addr(prev) XOR 0. At first glance this looks impossible: a single number cannot name two different addresses. And it cannot — on its own. The trick only works in motion, when you already know one neighbour.

The Arithmetic That Makes It Work

XOR has one property that carries the whole design: it is its own inverse. For any values a and b:

a XOR a = 0          (self-annihilation)
a XOR 0 = a          (identity)
(a XOR b) XOR a = b  (self-inverse: XOR by a again to undo)

Now suppose you are walking forward and you know the node you just came from, prev. The current node stores npx = prev XOR next. XOR that field with the prev you are holding and the prev terms cancel:

npx XOR prev = (prev XOR next) XOR prev = next

You have recovered next from one stored field plus one remembered pointer. Symmetrically, if you know next you recover prev = npx XOR next. So traversal is always "I remember where I came from, XOR it out, and the field hands me where to go". Two directions fall out of the same identity:

• Forward from the head: seed prev = 0 (nothing precedes the head), and each step computes next = npx XOR prev.
• Backward from the tail: seed next = 0 (nothing follows the tail), and each step computes prev = npx XOR next.

The catch is now visible: you can only move if you are already moving. Handed a bare pointer to some interior node, with no neighbour in hand, you cannot decode npx at all — it is one number hiding two addresses, and without one of them you can recover neither. That single limitation is the root of almost every problem later in this post.

A Complete C++ Implementation

Pointers cannot be XORed directly — the operator is not defined on pointer types — so we round-trip through std::uintptr_t, the unsigned integer type guaranteed wide enough to hold a pointer. Every XOR happens in integer space; every dereference happens after casting back.

#include <cstdint>
#include <iostream>

struct Node {
    int           value;
    std::uintptr_t npx;      // addr(prev) XOR addr(next)
    explicit Node(int v) : value(v), npx(0) {}
};

// XOR two node pointers by value, returning the result as a pointer.
inline Node* xorPtr(Node* a, Node* b) {
    return reinterpret_cast<Node*>(
        reinterpret_cast<std::uintptr_t>(a) ^ reinterpret_cast<std::uintptr_t>(b));
}

Insertion at the front has to fix up exactly one existing node — the old head, whose prev changes from null to the new node. Because the old head stored 0 XOR next, and we want newNode XOR next, we simply XOR the new node's address into the old head's field; the unchanged next term survives untouched.

class XorList {
    Node* head_ = nullptr;
    Node* tail_ = nullptr;
public:
    void insert_front(int v) {
        Node* n = new Node(v);
        n->npx = reinterpret_cast<std::uintptr_t>(head_);   // prev=null, next=old head
        if (head_)
            head_->npx ^= reinterpret_cast<std::uintptr_t>(n);  // patch old head's prev
        else
            tail_ = n;                                          // first node is also tail
        head_ = n;
    }

    void traverse_forward() const {
        Node* prev = nullptr;
        Node* cur  = head_;
        while (cur) {
            std::cout << cur->value << ' ';
            Node* next = xorPtr(reinterpret_cast<Node*>(cur->npx), prev);  // npx XOR prev
            prev = cur;
            cur  = next;
        }
    }

    void traverse_backward() const {
        Node* next = nullptr;
        Node* cur  = tail_;
        while (cur) {
            std::cout << cur->value << ' ';
            Node* prev = xorPtr(reinterpret_cast<Node*>(cur->npx), next);  // npx XOR next
            next = cur;
            cur  = prev;
        }
    }

    ~XorList() {
        Node* prev = nullptr;
        Node* cur  = head_;
        while (cur) {
            Node* next = xorPtr(reinterpret_cast<Node*>(cur->npx), prev);
            prev = cur;         // keep the address to decode the next node
            delete cur;         // ... which we now XOR *after* freeing it
            cur  = next;
        }
    }
};

Notice the teardown loop already forces a code smell: to decode node i+1 you must XOR with the address of node i, which you just deleted. You never dereference the freed pointer, only reuse its integer value — but you are handling the value of an object whose lifetime has ended, which the standard already frowns on. The algorithm cannot avoid it; walking an XOR list requires carrying the previous node's address forward, deleted or not.

A Worked Four-Node List

Say the four nodes A, B, C, D land at these (illustratively small) addresses. Each npx is the XOR of the addresses on either side, with 0 standing in for a missing neighbour:

Walk it forward, seeding prev = 0x00. Each step XORs the stored field with the address you arrived from:

cur=A(0x10) prev=0x00 :  next = 0x20 ^ 0x00 = 0x20  → B
cur=B(0x20) prev=0x10 :  next = 0x20 ^ 0x10 = 0x30  → C
cur=C(0x30) prev=0x20 :  next = 0x60 ^ 0x20 = 0x40  → D
cur=D(0x40) prev=0x30 :  next = 0x30 ^ 0x30 = 0x00  → nullptr (stop)

Every stored field was a single 8-byte number, yet the walk recovered the full forward chain. Reversing — seed next = 0x00, start at D — recovers 0x30 ^ 0x00 = 0x30 = C, then 0x60 ^ 0x40 = 0x20 = B, and so on back to A.

Watch the Decode Step

The animation walks the same four nodes forward. Each step shows the arithmetic next = npx XOR prev that produces the address of the following node from the field stored in the current one.

Why It Is Almost Always Wrong

The trick works. It is still a bad idea in essentially all modern code, and the reasons compound.

It is undefined behaviour in strict C++. The standard does not promise that a pointer survives a round trip through integer arithmetic. reinterpret_cast<uintptr_t>(p) then back is only guaranteed to reproduce p if you cast the same value straight back — not after XORing it with something else. Under the C++ pointer provenance rules, a pointer synthesised from arithmetic has no provenance tying it to the object it happens to address, so dereferencing it is UB. Optimisers that assume provenance (and the machinery behind -fstrict-aliasing) are entitled to miscompile this code, and "it worked on my compiler" is the whole guarantee you get.

It is invisible to garbage collectors. A tracing or conservative collector (the Boehm GC, or any managed runtime) finds live objects by scanning memory for values that look like pointers. An XORed field looks like a random integer, not an address, so the collector cannot see that A keeps B reachable. Your nodes get collected out from under you while still in the list. XOR lists are fundamentally incompatible with any environment that scans for pointers.

It defeats every tool you debug with. A debugger cannot follow npx to the next node — there is no next pointer to follow. AddressSanitizer and Valgrind track pointer provenance to catch use-after-free and out-of-bounds; a synthesised pointer defeats their bookkeeping, so they both miss real bugs and, worse, the manufactured pointers can trip their own invariants. You have traded 8 bytes for the loss of your entire diagnostic toolchain.

You cannot delete a node from a bare pointer. Ordinary doubly linked lists let you erase a node in O(1) given only a pointer to it — you have its prev and next. An XOR list node hands you one number that is useless without a neighbour, so an "erase this node" API is impossible; you must re-walk from an end to recover the context.

It breaks under any allocator that moves or compresses pointers. Compacting garbage collectors relocate objects; pointer-compression schemes (V8, the JVM's compressed oops) store 32-bit offsets instead of raw addresses. Both assume they can find and rewrite every stored pointer. An XORed field is not recognisable as a pointer, so it is neither found nor fixed — the list silently points into freed or moved memory.

When It Is Actually Reasonable

There are exactly two honest homes for this technique. The first is a deeply memory-constrained embedded system with a fixed, non-moving allocator, no garbage collector, no sanitizer in the shipping build, and a hand-verified compiler — where 8 bytes per node across a large table is a real fraction of scarce RAM and none of the objections above apply. The second is as an interview brain-teaser, where it is a fine test of whether you understand XOR's self-inverse property and pointer/integer casts. Outside those, every alternative dominates it:

The index approach is the quiet winner: 32-bit handles into a contiguous array beat the XOR list on memory and keep everything the XOR list throws away — debuggability, sanitizer support, GC compatibility, and O(1) erase — because there are no raw pointers to hide. See Unrolled & Intrusive Lists for the allocation-free options.

Related XOR Tricks Worth Knowing

The same self-inverse identity powers a family of interview classics, and it is worth separating the ones that are merely cute from the ones that are genuinely useful.

XOR swap exchanges two integers without a temporary:

a ^= b;  b ^= a;  a ^= b;   // now a and b are swapped

It is a worse choice than std::swap in every way. It is wrong when both operands alias the same location — xorSwap(x, x) zeroes it, because the first a ^= b already makes a zero. It creates a serial dependency chain of three dependent operations where a register swap has none, so it is slower on any out-of-order CPU. And it obscures intent from the optimiser, which recognises and lowers std::swap to the ideal instructions. Know it exists; never ship it.

Find the missing (or duplicate) number. This one is genuinely good. XOR every index 0..n together with every array value; identical terms annihilate in pairs and the lone survivor is the missing element — O(n) time, O(1) space, no overflow risk (unlike the sum-based version). The same pairing trick finds the single number that appears an odd number of times among duplicates. These, and the deeper XOR-basis and trie techniques, are covered in XOR Patterns.

Check Yourself

Six situations. Pick the statement that is actually true of an XOR linked list.

Practice

• Implement insert_front, insert_back, and both traversals, then verify forward and backward walks print mirror images. core use uintptr_t and a single xorPtr helper.
• Add an erase(Node* n, Node* neighbour) that requires a neighbour argument. limitation feel directly why a bare-pointer erase is impossible.
• Rebuild the same list with 32-bit array indices instead of XOR pointers. alternative compare memory, then run both under AddressSanitizer and note which one it can instrument.
• LeetCode 136 — Single Number xor the self-inverse identity in its purest form: XOR everything, duplicates cancel.
• LeetCode 268 — Missing Number xor XOR indices against values so only the gap survives; O(1) space, no overflow.
• Compile the XOR list at -O2 -fstrict-aliasing and again with pointer-provenance warnings on. ub read the diagnostics and explain each one against the provenance rules.