XOR Linked List: Memory-Efficient Doubly Linked List
Standard doubly linked lists are workhorses of computer science. They give you O(1) insertion and deletion at any position, bidirectional traversal, and straightforward implementation. But they come...
Key Insights
- XOR linked lists cut pointer storage in half by storing
prev ⊕ nextinstead of separate prev and next pointers, exploiting the self-inverse property of XOR operations. - The technique requires manual memory management and raw pointer arithmetic, making it incompatible with garbage-collected languages and modern smart pointers.
- While historically valuable for memory-constrained embedded systems, modern CPU cache behavior and cheap RAM mean XOR linked lists rarely provide practical benefits today—but they remain an excellent exercise in understanding pointer manipulation.
The Memory Problem with Doubly Linked Lists
Standard doubly linked lists are workhorses of computer science. They give you O(1) insertion and deletion at any position, bidirectional traversal, and straightforward implementation. But they come with a cost: every node carries two pointers.
On a 64-bit system, that’s 16 bytes of overhead per node just for navigation. For a list of a million small integers, you’re spending 16MB on pointers alone. In the 1970s and 80s, when memory was measured in kilobytes, this overhead was painful.
The XOR linked list emerged as a clever hack to cut that overhead in half. Instead of storing two separate pointers, each node stores a single value: the XOR of its previous and next node addresses. Using the mathematical properties of XOR, you can derive either neighbor’s address if you know the other one.
The trade-off is real: you gain memory efficiency but lose simplicity, debuggability, and compatibility with most modern programming paradigms. Let’s dig into how it actually works.
How XOR Linking Works
The XOR operation has three properties that make this technique possible:
A ⊕ A = 0 (XOR with itself yields zero)
A ⊕ 0 = A (XOR with zero yields the original)
A ⊕ B ⊕ A = B (XOR is self-inverse)
In a standard doubly linked list, node B stores pointers to both A and C:
[A] <--prev-- [B] --next--> [C]
--next--> <--prev--
In an XOR linked list, node B stores only addr(A) ⊕ addr(C):
[A] <-- addr(A) ⊕ addr(C) --> [C]
(stored in B.link)
Here’s the key insight: if you’re traversing from A to B, you already know A’s address. To find C:
B.link ⊕ addr(A) = addr(A) ⊕ addr(C) ⊕ addr(A) = addr(C)
The same logic works in reverse. If you’re coming from C, XOR B’s link field with C’s address to get A’s address. You always need to know where you came from to figure out where you’re going.
Node Structure and Basic Setup
Here’s the fundamental structure in C:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef struct Node {
int data;
struct Node* link; // prev XOR next
} Node;
// XOR two node pointers
Node* xor_ptrs(Node* a, Node* b) {
return (Node*)((uintptr_t)a ^ (uintptr_t)b);
}
typedef struct {
Node* head;
Node* tail;
} XORList;
XORList* create_list() {
XORList* list = malloc(sizeof(XORList));
list->head = NULL;
list->tail = NULL;
return list;
}
The xor_ptrs function handles the pointer arithmetic. We cast to uintptr_t (an unsigned integer type guaranteed to hold a pointer) to perform the XOR, then cast back to a pointer.
For boundary nodes, we use NULL (address 0) as the missing neighbor:
- Head node’s link =
NULL ⊕ addr(second_node)=addr(second_node) - Tail node’s link =
addr(second_to_last) ⊕ NULL=addr(second_to_last)
This works because XOR with zero is identity.
Core Operations: Insertion
Insertion requires updating the XOR links of adjacent nodes. Here’s insertion at the beginning:
void insert_at_head(XORList* list, int data) {
Node* new_node = malloc(sizeof(Node));
new_node->data = data;
if (list->head == NULL) {
// Empty list: new node is both head and tail
new_node->link = NULL; // NULL XOR NULL
list->head = new_node;
list->tail = new_node;
} else {
// New node's link: NULL XOR old_head
new_node->link = xor_ptrs(NULL, list->head);
// Old head's link was: NULL XOR second_node
// New link should be: new_node XOR second_node
// We compute: old_link XOR NULL XOR new_node
list->head->link = xor_ptrs(xor_ptrs(list->head->link, NULL), new_node);
list->head = new_node;
}
}
Insertion at the tail follows the same pattern:
void insert_at_tail(XORList* list, int data) {
Node* new_node = malloc(sizeof(Node));
new_node->data = data;
if (list->tail == NULL) {
new_node->link = NULL;
list->head = new_node;
list->tail = new_node;
} else {
// New node's link: old_tail XOR NULL
new_node->link = xor_ptrs(list->tail, NULL);
// Old tail's link was: prev XOR NULL
// New link should be: prev XOR new_node
// We compute: old_link XOR NULL XOR new_node
list->tail->link = xor_ptrs(xor_ptrs(list->tail->link, NULL), new_node);
list->tail = new_node;
}
}
The pattern for updating an existing node’s link is: old_link ⊕ old_neighbor ⊕ new_neighbor. This effectively replaces one neighbor with another.
Core Operations: Traversal and Deletion
Traversal requires maintaining two pointers: the current node and the previous node. With both, you can compute the next node’s address.
void traverse_forward(XORList* list) {
Node* prev = NULL;
Node* curr = list->head;
printf("Forward: ");
while (curr != NULL) {
printf("%d ", curr->data);
// next = prev XOR curr->link
Node* next = xor_ptrs(prev, curr->link);
prev = curr;
curr = next;
}
printf("\n");
}
void traverse_backward(XORList* list) {
Node* next = NULL;
Node* curr = list->tail;
printf("Backward: ");
while (curr != NULL) {
printf("%d ", curr->data);
// prev = next XOR curr->link
Node* prev = xor_ptrs(next, curr->link);
next = curr;
curr = prev;
}
printf("\n");
}
Deletion is more complex because you need to update two neighbors:
int delete_node(XORList* list, int value) {
if (list->head == NULL) return 0;
Node* prev = NULL;
Node* curr = list->head;
Node* next = xor_ptrs(prev, curr->link);
while (curr != NULL) {
if (curr->data == value) {
// Found the node to delete
if (prev != NULL) {
// Update prev's link: remove curr, add next
// prev->link was: prev_prev XOR curr
// New link: prev_prev XOR next
prev->link = xor_ptrs(xor_ptrs(prev->link, curr), next);
} else {
// Deleting head
list->head = next;
}
if (next != NULL) {
// Update next's link: remove curr, add prev
// next->link was: curr XOR next_next
// New link: prev XOR next_next
next->link = xor_ptrs(xor_ptrs(next->link, curr), prev);
} else {
// Deleting tail
list->tail = prev;
}
free(curr);
return 1;
}
prev = curr;
curr = next;
if (curr != NULL) {
next = xor_ptrs(prev, curr->link);
}
}
return 0; // Not found
}
Limitations and Practical Considerations
XOR linked lists have significant drawbacks that limit their modern applicability.
Garbage collection incompatibility. Languages with garbage collectors (Java, Python, Go, JavaScript) can’t use this technique. The GC needs to trace object references, but XOR’d pointers don’t look like valid references. The GC will collect nodes it can’t trace, corrupting your list. Even C++ smart pointers won’t work—they need actual pointer values, not XOR’d combinations.
Debugging nightmares. You can’t inspect a node and see its neighbors. Every pointer examination requires knowing the address you came from. Debugger watch expressions become useless. Memory corruption bugs become nearly impossible to diagnose.
Cache performance. Modern CPUs are optimized for sequential memory access. The memory savings from XOR linking (8 bytes per node on 64-bit systems) rarely translate to performance gains. Cache lines are typically 64 bytes; saving 8 bytes per node won’t reduce cache misses unless your nodes are tiny. The extra XOR operations add CPU overhead that often exceeds any memory bandwidth savings.
When it actually makes sense. XOR linked lists remain relevant in specific contexts:
- Embedded systems with kilobytes of RAM
- Real-time systems where memory allocation is forbidden after initialization
- Educational settings demonstrating pointer manipulation
- Interview questions testing bitwise operation understanding
Historical Curiosity or Practical Tool?
The XOR linked list is a beautiful hack from an era when every byte mattered. It demonstrates deep understanding of pointer representation and bitwise operations.
For production code in 2024, you have better options:
Unrolled linked lists store multiple elements per node, amortizing pointer overhead across several values. They’re cache-friendly and work with any language.
Memory pools pre-allocate node storage, eliminating per-node allocation overhead and improving cache locality.
Intrusive linked lists embed link pointers in the data structure itself, eliminating separate node allocations.
The XOR linked list’s real value today is educational. Implementing one forces you to understand pointer representation at the bit level, reason about memory addresses as numeric values, and appreciate the elegance of XOR’s mathematical properties. It’s a rite of passage for systems programmers, even if the code never ships.
If you’re working in a genuinely memory-constrained environment—a microcontroller with 2KB of RAM, a bootloader, or bare-metal firmware—XOR linked lists might earn their complexity. For everyone else, appreciate the cleverness, learn from the technique, and use a standard doubly linked list.