↩ back to Linear

XOR Linked List

A doubly linked list buys backward traversal and O(1) removal given a direct node reference by giving every node two pointers, prev and next. An XOR linked list buys the same backward traversal — same bidirectional walk, same asymptotic time — with only one field per node, by storing neither pointer on its own but their bitwise XOR: link = prev ⊕ next. Walking still works because XOR is its own inverse: given the address you just arrived from and a node's stored link, XORing the two together recovers the address you're going to next, whichever direction that is. What that single scrambled number can't give back is a free O(1) unlink using nothing but the node's own address, the way a doubly linked list's prev pointer does — see Pitfalls.

The trick is easiest to see with three nodes at addresses 1, 2, and 3, holding values A, B, and C in that order. Node 1, the head, has no predecessor, so its link is just its successor's address XORed with 0: 0 ⊕ 2 = 2. Node 3, the tail, has no successor, so its link is its predecessor XORed with 0: 2 ⊕ 0 = 2. Node 2, the only one with a neighbor on both sides, has both smashed together: 1 ⊕ 3 = 2. A walker arriving at node 2 from node 1 (walking forward) already knows prev = 1, so it computes next = link ⊕ prev = 2 ⊕ 1 = 3 — correct, node 3. A walker arriving at node 2 from node 3 (walking backward) knows prev = 3 instead, so the exact same formula gives next = 2 ⊕ 3 = 1 — also correct, the opposite direction, same stored number, same arithmetic. One field, two different answers, depending only on which neighbor you already had in hand.

Try it

Insert values at the front or back and watch every node's link field — the single number standing in for two pointers. Step forward or backward one hop at a time to see the actual XOR arithmetic recover each neighbor's address live, then delete a value and read why the walk down to it wasn't optional this time.

Core operations

• insertFront(x) / insertBack(x) — O(1). A new node's link is just the address of the neighbor it's attached to (the old head or tail), XORed with 0 since it has no neighbor on the other side yet. The affected old end doesn't get its link overwritten the way a real pointer would — it gets XOR-toggled: oldEnd.link ^= newAddr. That single line is doing the same job as fixing up one `prev` or `next` pointer on a doubly linked list's neighbor, just phrased as a flip instead of an assignment.
• step(dir) — O(1) per hop, carrying prev and curr forward as it goes: next = link(curr) ⊕ prev, then prev, curr = curr, next. A full walk from one end is O(n), same as a doubly linked list, but every hop needs the address just left behind as explicit running state — a doubly linked node carries that for you for free in its own prev/next field, an XOR linked node doesn't store it anywhere at all once you've moved past it.
• findValue(x) — walk forward from the head comparing values, O(n), tracking prev the whole way as an unavoidable side effect of walking at all — which turns out to matter for delete, below.
• removeGivenNeighbor(prevAddr, currAddr) — the actual O(1) unlink, and the headline difference from a doubly linked list: it needs two addresses, not one. Given curr's own address alone, link(curr) is a single number equal to prevAddr ⊕ nextAddr — one equation, two unknowns, genuinely unsolvable without already knowing one of them. There is no method with the shape of a doubly linked list's removeNode(node) here; see Pitfalls for exactly how far that goes wrong.
• deleteValue(x) — findValue(x) already walked from the head tracking prev, so by the time x is found, both addresses removeGivenNeighbor needs are already sitting in hand. O(n) overall, identical to a doubly linked list's deleteValue — the walk was never avoidable for a delete-by-value anyway, on either structure.

Reference implementation

Real XOR linked lists XOR actual memory addresses, which JavaScript never hands out. This reference implementation stands in a plain array for memory: each node lives at array index addr - 1, so addr behaves exactly like a raw address would, and 0 is reserved to mean "no neighbor," the same role a null pointer plays in a real implementation.

class XorLinkedList {
  #mem = [];   // #mem[addr - 1] = { value, link }
  #head = 0;   // 0 means "no node" — reserved, real addresses start at 1
  #tail = 0;
  #size = 0;

  get size() { return this.#size; }
  isEmpty() { return this.#size === 0; }

  insertBack(x) {
    const addr = this.#mem.length + 1;
    this.#mem.push({ value: x, link: this.#tail });
    if (this.#tail !== 0) this.#mem[this.#tail - 1].link ^= addr;
    if (this.#head === 0) this.#head = addr;
    this.#tail = addr;
    this.#size++;
    return addr;
  }

  insertFront(x) {
    const addr = this.#mem.length + 1;
    this.#mem.push({ value: x, link: this.#head });
    if (this.#head !== 0) this.#mem[this.#head - 1].link ^= addr;
    if (this.#tail === 0) this.#tail = addr;
    this.#head = addr;
    this.#size++;
    return addr;
  }

  // one hop, either direction: caller supplies where it came from
  step(currAddr, prevAddr) {
    const link = this.#mem[currAddr - 1].link;
    return link ^ prevAddr;
  }

  findValue(x) {
    let prev = 0, curr = this.#head;
    while (curr !== 0) {
      const next = this.step(curr, prev);
      if (this.#mem[curr - 1].value === x) return { addr: curr, prevAddr: prev, nextAddr: next };
      prev = curr;
      curr = next;
    }
    return null;
  }

  removeGivenNeighbor(currAddr, prevAddr, nextAddr) {
    if (prevAddr !== 0) this.#mem[prevAddr - 1].link ^= (currAddr ^ nextAddr);
    else this.#head = nextAddr;
    if (nextAddr !== 0) this.#mem[nextAddr - 1].link ^= (currAddr ^ prevAddr);
    else this.#tail = prevAddr;
    this.#size--;
  }

  deleteValue(x) {
    const found = this.findValue(x);
    if (found === null) return false;
    this.removeGivenNeighbor(found.addr, found.prevAddr, found.nextAddr);
    return true;
  }
}

Verified against a plain-array model over 30,000 randomized operations — inserts at either end and deletes by value, with the list's forward walk and backward walk checked against the model after every single operation, not just the forward one. Also hand-traced a 4-node list built by insertBack('10'); insertBack('20'); insertBack('30'); insertBack('40'): addresses 1-4 end up with links 2, 2, 6, 3, and a forward walk from the head computes 2⊕0=2 → 2⊕1=3 → 6⊕2=4 → 3⊕3=0 (end), recovering 10, 20, 30, 40 in order; a backward walk from the tail on the same list computes 3⊕0=3 → 6⊕4=2 → 2⊕3=1 → 2⊕2=0 (end), recovering 40, 30, 20, 10. Deleting '20' (address 2, found with prevAddr=1, nextAddr=3) updates address 1's link from 2 to 2 ⊕ (2 ⊕ 3) = 3 and address 3's link from 6 to 6 ⊕ (2 ⊕ 1) = 5; a forward walk afterward correctly recovers 10, 30, 40. See /tmp/xor_test/demo_seed.js, not committed, it's scratch — this is the exact trace the shipped demo below reproduces.

Pitfalls

A bare address isn't enough to delete a node. The whole appeal of a doubly linked list's removeNode(node) is that node alone is sufficient — node.prev and node.next are both sitting right there. An XOR linked node's link field is one number equal to prevAddr ⊕ nextAddr, and one equation with two unknowns has no unique solution: given only link(2) = 2 in the 4-node example above, (prevAddr, nextAddr) = (1, 3) satisfies it — the real answer — but so does (7, 5), or (0, 2), or infinitely many other pairs whose XOR happens to equal 2. The number carries no way to tell which pair is real. The only way to delete a node is to already know at least one of its neighbors, which in practice means arriving at it mid-walk, exactly what findValue does above by tracking prev the entire time. A method that takes only a node's own address and deletes it in O(1), the signature that makes a doubly linked list's version so convenient, is not something this structure can offer at all — not a missing feature, a mathematical impossibility given what's actually stored.

Forgetting to XOR-toggle the other end. Every insert touches two nodes: the new one, and whichever old end it attaches to — and that old end's link needs to be XOR-toggled, not left alone, the same way a doubly linked list's old end needs its next or prev pointer fixed up. Skipping that step on a bare insertBack reproduces silently: appending '10', '20', then '30' without updating the previous tail's link on each append leaves address 1's link permanently 0 — the value it had when it was still the tail and had no successor. Walking forward from the head computes next = 0 ⊕ 0 = 0 at the very first node and stops immediately: a measured forward walk returns ['10'], silently missing '20' and '30' entirely, with no error of any kind. The list still looks fine from the write side — every insert reported success — the corruption only shows up the next time something tries to read past the first node.

Where XOR linked lists show up

• Nowhere in a garbage-collected language, and that's not incidental. The trick needs an actual address to XOR — a raw integer a language is willing to hand back to you and let you do arithmetic on. JavaScript, Java, Python, and Go never expose one; this page's own reference implementation has to fake it with array indices standing in for addresses. That's a real limitation, not a simplification for teaching purposes.
• Memory-constrained embedded and kernel code, in C or a similarly low-level language. Real pointers are real integers there, XOR-able like any other integer, and halving the per-node pointer overhead is a genuine, measurable win when every byte of a node is budgeted for — the exact tradeoff this page's opening paragraphs describe.
• Anywhere the deletion pitfall above is a dealbreaker, this structure is the wrong choice regardless of the memory savings. A cache or scheduler that stores node addresses externally and expects to unlink one later, the way an LRU cache does with a doubly linked list's node references, can't do that here — the stored address alone is exactly what Pitfalls shows isn't enough.

Complexity

Time: insertFront and insertBack are O(1), same as a doubly linked list. A full traversal in either direction is O(n), same as a doubly linked list. findValue and deleteValue are O(n), same as a doubly linked list — the walk was never avoidable on either structure. The one place they diverge: deleting a node given only its own address is O(1) on a doubly linked list and not expressible at all here, per Pitfalls; deleting given a node's address and the neighbor just arrived from is O(1) on both. Space: O(n) for n nodes, with exactly one link field per node — matching a plain singly linked list's one-pointer footprint while matching a doubly linked list's bidirectional traversal, the combination this structure exists to offer. That combination costs nothing extra in the asymptotics; it costs the deletion guarantee described above, and it costs the ability to run at all in a language that won't give out raw addresses.

This site's guide, Choosing a Linear Data Structure, sets this entry aside for a different reason than Monotonic Stack and Monotonic Deque: not because it isn't a real storage option, but because a language like the ones this site's demos run in never hands out a real memory address to XOR in the first place.