Introduction

A doubly linked list normally stores two links per node: one to the previous node and one to the next. If you insist on using only one pointer-sized field per node while still supporting forward and backward traversal, the classic answer is an XOR linked list. The idea is clever, but it comes with real tradeoffs in safety, portability, and debuggability.

The Core Idea: Store prev XOR next

In a normal doubly linked list node, the links look like this conceptually:

• 'prev'
• 'next'

In an XOR linked list, you store only one field, often called both, which contains:

address(prev) XOR address(next)

If you know one neighbor, you can recover the other:

next = both XOR prev

That is why traversal still works in both directions even though only one pointer-sized value is stored.

A Minimal C Representation

C is a natural language for demonstrating this because it gives direct access to addresses.

1#include <stdint.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef struct Node {
6    int value;
7    struct Node* both;
8} Node;
9
10static Node* xor_ptr(Node* a, Node* b) {
11    return (Node*)((uintptr_t)a ^ (uintptr_t)b);
12}

uintptr_t matters here because pointer XOR should go through an integer type designed to hold pointer values safely.

Appending Nodes

To append a node, update the old tail and the new node consistently.

1void append(Node** head, Node** tail, int value) {
2    Node* node = malloc(sizeof(Node));
3    node->value = value;
4    node->both = xor_ptr(*tail, NULL);
5
6    if (*tail != NULL) {
7        Node* prev = xor_ptr((*tail)->both, NULL);
8        (*tail)->both = xor_ptr(prev, node);
9    } else {
10        *head = node;
11    }
12
13    *tail = node;
14}

The tail’s old both value effectively encoded prev XOR NULL. After appending, it must encode prev XOR newNode.

Traversing Forward

Traversal works because you always keep track of the previous node while walking.

1void print_forward(Node* head) {
2    Node* prev = NULL;
3    Node* current = head;
4
5    while (current != NULL) {
6        printf("%d\n", current->value);
7        Node* next = xor_ptr(prev, current->both);
8        prev = current;
9        current = next;
10    }
11}

At each step:

• 'current->both equals prev XOR next'
• XORing that with prev gives next

That is the entire mechanism.

Traversing Backward

Backward traversal is symmetrical if you keep a tail pointer.

1void print_backward(Node* tail) {
2    Node* next = NULL;
3    Node* current = tail;
4
5    while (current != NULL) {
6        printf("%d\n", current->value);
7        Node* prev = xor_ptr(next, current->both);
8        next = current;
9        current = prev;
10    }
11}

This is why the structure behaves like a doubly linked list even though each node stores only one pointer-sized link field.

Why This Is Rare in Real Software

XOR linked lists are a classic interview or low-level data-structure exercise, but they are uncommon in production systems.

Reasons include:

• harder debugging because pointer relationships are not explicit
• poor compatibility with garbage-collected languages
• awkward interaction with sanitizers, debuggers, and memory tools
• harder insertion and deletion logic than an ordinary doubly linked list

In modern software, memory savings from one pointer per node are often not worth the maintenance cost.

Languages Where This Is a Bad Idea

Managed languages such as Java, C#, Go, and Swift are poor fits because raw address manipulation is restricted or unsafe. Even in C and C++, XOR linked lists are more of a niche technique than a recommended default.

If the real goal is lower memory usage, a different data structure may be better:

• a regular linked list with better node packing
• a dynamic array
• an indexed pool with integer offsets instead of raw pointers

Those designs are usually easier to reason about.

Common Pitfalls

A common mistake is XORing raw pointers without converting through uintptr_t. That is not the right way to express pointer arithmetic safely.

Another issue is forgetting that traversal always needs the previous node. You cannot jump to the next node from the current node alone because the stored field encodes both neighbors together.

Developers also underestimate how hard deletion becomes. Updating one node is not enough; neighboring nodes must be recomputed carefully.

Finally, this structure is difficult to inspect in a debugger because the link field is not a direct pointer to anything human-readable.

Summary

• A doubly linked list with one pointer-sized link per node is usually implemented as an XOR linked list.
• Each node stores prev XOR next instead of separate prev and next pointers.
• Traversal works only because you carry the previous node along while walking the list.
• The technique is clever but significantly harder to debug and maintain than a normal doubly linked list.
• In most production code, the memory savings do not justify the complexity.