Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 225 ยท Linked Lists

Unrolled and XOR Linked Lists

Two clever linked list variants: unrolled lists store many items per node for cache-friendly speed, XOR lists store one link for two pointers. With code.

A plain singly linked list is simple, but it is not kind to real hardware. Each node is a separate small allocation, with a pointer to chase for every single element. The CPU cache loves data that sits next to each other in memory, and a linked list scatters it. Every node also pays for its own pointer and allocator bookkeeping, so for small elements the overhead can be larger than the data itself.

This lesson looks at two variants that attack those costs from different sides. The unrolled linked list puts several elements in each node, trading a little extra shifting for far fewer nodes and far better cache behaviour. The XOR linked list shrinks a doubly linked list by storing a single value per node that encodes both neighbours. They are not everyday tools in Python, but they teach how data layout affects speed, a theme you will meet again in memory and data layout.

Unrolled linked lists

An unrolled list is a linked list of small arrays. Each node holds up to capacity items and one pointer to the next node.

flowchart LR
    H["head"] --> N1["node 1<br/>[3, 7, 9, 12]"]
    N1 --> N2["node 2<br/>[15, 20]"]
    N2 --> N3["node 3<br/>[31, 40, 41]"]
    N3 --> X["None"]

Three nodes hold nine items, so there are three pointers instead of nine.

The rules keep the nodes reasonably full:

  • Lookup by index: walk node by node, subtracting each node's size, until the index falls inside a node, then index into the array. That is O(n / capacity) pointer steps, plus O(1) inside the node.
  • Insert: find the node, insert into its array (shifting at most capacity items). If the array overflows, split it into two half-full nodes.
  • Delete: remove from the array. If a node becomes too empty (say below half), merge it with a neighbour or borrow from it.

With a capacity around the square root of n you get O(sqrt n) for index operations, the same trade-off as sqrt decomposition. With a capacity that matches the cache line or page size, the list becomes very friendly to the hardware: one pointer dereference brings in many items at once.

Python An unrolled linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a node reaches capacity + 1 items, it splits into two halves, so every node (except possibly the first and last) stays at least about half full. That gives a guaranteed storage efficiency of roughly 50% to 100% for data, compared with a plain list, where every node is 100% overhead plus one element.

Where unrolled lists shine

In languages with manual memory such as C and C++, an unrolled list can be several times faster than a linked list for scanning, because the scan reads sequential memory inside each node. The per-node overhead (an allocator header and a pointer) is divided by the capacity. A text editor can store lines or characters this way; some functional-language runtimes use similar "chunked" lists; and std::deque and Python's collections.deque are close relatives: a deque is a linked list of fixed blocks.

The price: insertion and deletion are more complicated, and iterators held across a split or merge need care.

XOR linked lists

A doubly linked list needs two pointers per node, prev and next. An XOR list keeps only one field, link = address(prev) XOR address(next). The trick relies on a property of XOR: a ^ b ^ b == a.

To walk forward, you must remember the address you just came from. If you are at node cur, and prev is the previous node's address, the next address is cur.link ^ prev. To walk backward, start from the tail and do the same with the roles reversed. The list uses half the pointer memory of a doubly linked list.

flowchart LR
    A["A<br/>link = 0 ^ B"] --- B["B<br/>link = A ^ C"]
    B --- C["C<br/>link = B ^ D"]
    C --- D["D<br/>link = C ^ 0"]

Each node stores prev XOR next. Knowing where you came from lets you recover where to go.

Python hides real memory addresses and its garbage collector would not see a pointer hidden inside an XOR, so we simulate memory with a list. An "address" is an index into the list, and address 0 means null.

Python An XOR linked list on simulated memory

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The most surprising line is reverse: because a node's link is symmetric in its two neighbours, swapping head and tail reverses the whole list in O(1), with no pointer rewriting.

Insertion and deletion

To insert after a given node you must know both its address and the address of its predecessor (or successor), because the XOR link alone cannot tell you which way is which. Typically you find the node during a traversal, where you already carry prev. Deleting works the same way: patch the XOR links of the two neighbours by XOR-ing out the removed node's address and XOR-ing in the other neighbour's address.

Why XOR lists are rare

  • They need real pointer arithmetic. In Java, Python, Go and other garbage-collected languages the collector cannot follow a hidden pointer and may even move objects, so XOR lists are impossible or only possible over an array like our simulation.
  • Debuggers, memory-safety tools and compilers' alias analysis cannot understand them.
  • You cannot start a traversal from the middle without a known neighbour.
  • Memory is rarely so tight that saving one pointer per node justifies all this.

They are mainly an excellent puzzle and a way to learn that data can carry more structure than it appears to.

Choosing between them

Variant Saves Costs Good for
Plain linked list Nothing special Cache misses, pointer overhead Teaching; O(1) splice with a known node
Unrolled list Pointers, cache misses Shifting inside nodes, split and merge code Sequences scanned often, text buffers
XOR list One pointer per node Needs raw addresses; awkward and unsafe Memory-starved C code, puzzles

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a node of an unrolled linked list contain?

    Grouping several items per node reduces the number of pointers and keeps items next to each other in memory.
  2. 2. What happens when an insertion overflows a node of an unrolled list?

    Splitting keeps every node at least about half full, which guarantees a good storage efficiency.
  3. 3. What does an XOR linked list store in each node, besides the value?

    link = prev ^ next. Because x ^ y ^ y == x, knowing one neighbour lets you recover the other.
  4. 4. Why is it a problem to build an XOR list in a garbage-collected language?

    A pointer disguised inside an XOR is invisible to the collector, which might free or relocate the nodes.

Summary

  • Unrolled lists store up to a fixed number of items per node: fewer pointers, better cache locality, index lookup in O(n / capacity) steps; they split on overflow and merge or borrow on underflow.
  • XOR lists store prev ^ next in a single field, so a doubly linked list takes half the pointers; you traverse by remembering the node you came from, and reversing is O(1).
  • XOR lists need raw pointer arithmetic, so they are mostly a curiosity; unrolled lists reappear as blocks in deques and text buffers.

Next: Stacks