Introduction

A XOR linked list is a space-saving variation of a doubly linked list. Instead of storing separate prev and next pointers, each node stores one value equal to prev XOR next, and traversal works only because you already know one of the two addresses at each step.

The Core Identity

The entire trick depends on one XOR property:

A XOR B XOR A = B

If a node stores both = prev XOR next and you know prev, you can recover next:

next = both XOR prev

Likewise, if you know next, you can recover prev.

That is why traversal always carries one extra piece of state: the address of the node you just came from.

Conceptual Layout

In a normal doubly linked list:

node.prev
node.next

In a XOR linked list:

node.both = address(prev) XOR address(next)

For the head node, the previous address is zero. For the tail node, the next address is zero. So the first node stores 0 XOR next, which is just next.

Low-Level Example in C

This structure is only practical in low-level languages that let you manipulate addresses directly. In C, uintptr_t is the usual integer type for pointer-sized arithmetic.

1#include <stdint.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef struct Node {
6    int value;
7    uintptr_t both;
8} Node;
9
10static Node *xor_ptr(Node *a, Node *b) {
11    return (Node *)((uintptr_t)a ^ (uintptr_t)b);
12}
13
14int main(void) {
15    Node *a = malloc(sizeof(Node));
16    Node *b = malloc(sizeof(Node));
17    Node *c = malloc(sizeof(Node));
18
19    a->value = 10;
20    b->value = 20;
21    c->value = 30;
22
23    a->both = (uintptr_t)xor_ptr(NULL, b);
24    b->both = (uintptr_t)xor_ptr(a, c);
25    c->both = (uintptr_t)xor_ptr(b, NULL);
26
27    Node *prev = NULL;
28    Node *curr = a;
29
30    while (curr != NULL) {
31        printf("%d\n", curr->value);
32        Node *next = xor_ptr(prev, (Node *)curr->both);
33        prev = curr;
34        curr = next;
35    }
36
37    free(a);
38    free(b);
39    free(c);
40    return 0;
41}

The important line is:

Node *next = xor_ptr(prev, (Node *)curr->both);

Given the previous node and the mixed address stored in both, you recover the next node.

Why People Rarely Use It

The memory saving is real in theory, but the tradeoff is usually not worth it in modern software.

Reasons it is uncommon:

• debugging is much harder
• pointer arithmetic is easy to get wrong
• garbage-collected languages do not expose raw addresses safely
• many tools expect ordinary pointers, not XOR-encoded ones
• the memory saved is often insignificant compared with the complexity added

A normal doubly linked list is easier to maintain, easier to profile, and much safer.

Insertion and Deletion Are Tricky

Traversal is the easy part. Updates are where XOR lists become awkward. To insert a node between left and right, you must recompute the both field of all affected nodes carefully. If one pointer is wrong, the entire structure becomes unreadable.

That fragility is a major reason XOR lists are mostly educational. They are good for understanding pointer representation and invariants, but poor as a default production choice.

Common Pitfalls

The biggest mistake is trying to implement XOR lists in a language where object addresses are not stable or not accessible. In Java, C#, Python, and JavaScript, this design is generally a bad fit.

Another mistake is assuming the XOR field can be inspected meaningfully in a debugger. It usually cannot, because it is not a valid standalone pointer.

A third problem is forgetting that you always need the previous node to compute the next one. Random access is not improved at all, and backward traversal still requires state.

Summary

• A XOR linked list stores prev XOR next instead of two separate pointers.
• Traversal works because knowing one neighbor lets you recover the other.
• The technique is mainly practical in low-level languages with raw pointer arithmetic.
• Insert and delete operations are harder than in a normal doubly linked list.
• In most real code, the small memory savings do not justify the complexity.