Why Linked Lists Exist

Linked Lists

A linked list is a collection where each item points to the next item.

An array stores items beside each other in memory:

[10][20][30][40]

A linked list stores items as separate nodes:

[10] -> [20] -> [30] -> [40]

Each node contains two things:

value
pointer to next node

That pointer connects the nodes into a chain.

Why Linked Lists Exist

With an array or ArrayList, the items are stored in one continuous memory block.

That is good for speed:

[10][20][30][40]

The CPU can read nearby values efficiently.

But inserting or removing in the middle can require shifting many items:

Before:
[10][20][30][40]

Remove 20:
[10][30][40]

Internally, 30 and 40 must move left.

A linked list avoids that kind of shifting. To remove a node, you change pointers.

Before:
[10] -> [20] -> [30]

After removing 20:
[10] --------> [30]

The values do not move. Only the links change.

The Tradeoff

Linked lists are not automatically faster than arrays.

They are often slower for simple iteration because nodes can live in different places in memory.

[10] somewhere
[20] somewhere else
[30] somewhere else

The CPU cannot read them as efficiently as a dense array.

Use a linked list when you need stable nodes and cheap insertion or removal once you already have a node.

Use an ArrayList when you mostly append, iterate, index, or store dense data.

Singly Linked List

A singly linked list has one pointer per node:

[value | next] -> [value | next] -> [value | null]

The last node points to null.

Here is a simple node type:

const Node = struct {
    value: i32,
    next: ?*Node,
};

Read the fields:

value: i32

This stores the data.

next: ?*Node

This stores an optional pointer to the next node.

The ? means the pointer may be null.

The *Node means a pointer to a Node.

So ?*Node means:

maybe a pointer to another Node

Building Nodes Manually

Here is a small linked list built from stack variables:

const std = @import("std");

const Node = struct {
    value: i32,
    next: ?*Node,
};

pub fn main() void {
    var third = Node{ .value = 30, .next = null };
    var second = Node{ .value = 20, .next = &third };
    var first = Node{ .value = 10, .next = &second };

    var current: ?*Node = &first;

    while (current) |node| {
        std.debug.print("{}\n", .{node.value});
        current = node.next;
    }
}

Output:

10
20
30

The list looks like this:

first       second      third
[10] ----> [20] ----> [30] ----> null

The variable current walks through the list.

var current: ?*Node = &first;

At each step, current is either:

a pointer to a node

or:

null

This loop continues while current is not null:

while (current) |node| {
    std.debug.print("{}\n", .{node.value});
    current = node.next;
}

Inside the loop, node is the unwrapped pointer.

Inserting After a Node

Suppose we have:

[10] -> [30]

We want to insert 20 after 10.

The result should be:

[10] -> [20] -> [30]

Pointer changes:

new_node.next = first.next;
first.next = &new_node;

Complete example:

const std = @import("std");

const Node = struct {
    value: i32,
    next: ?*Node,
};

pub fn main() void {
    var third = Node{ .value = 30, .next = null };
    var first = Node{ .value = 10, .next = &third };

    var second = Node{ .value = 20, .next = null };

    second.next = first.next;
    first.next = &second;

    var current: ?*Node = &first;
    while (current) |node| {
        std.debug.print("{}\n", .{node.value});
        current = node.next;
    }
}

Output:

10
20
30

The order of assignment matters.

Do this first:

second.next = first.next;

Then this:

first.next = &second;

If you reverse the order, you lose the pointer to the old next node.

Removing After a Node

Suppose we have:

[10] -> [20] -> [30]

We want to remove the node after 10.

The result:

[10] -> [30]

The pointer change is:

first.next = first.next.?.next;

That line says:

1. get first.next
2. unwrap it with .?'
3. read that node’s next
4. store it back into first.next

A clearer version:

if (first.next) |node_to_remove| {
    first.next = node_to_remove.next;
}

This changes the chain.

It does not free heap memory. It only unlinks the node.

If the removed node was allocated on the heap, you must destroy it separately.

Heap-Allocated Nodes

Real linked lists often allocate nodes dynamically.

const std = @import("std");

const Node = struct {
    value: i32,
    next: ?*Node,
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    const first = try allocator.create(Node);
    first.* = Node{ .value = 10, .next = null };

    const second = try allocator.create(Node);
    second.* = Node{ .value = 20, .next = null };

    first.next = second;

    var current: ?*Node = first;
    while (current) |node| {
        std.debug.print("{}\n", .{node.value});
        current = node.next;
    }

    allocator.destroy(second);
    allocator.destroy(first);
}

allocator.create(Node) allocates memory for one Node.

It returns:

*Node

Then this initializes the node:

first.* = Node{ .value = 10, .next = null };

The .* means “the value stored at this pointer.”

Freeing a Whole Linked List

If you allocate many nodes, free all of them.

fn freeList(allocator: std.mem.Allocator, head: ?*Node) void {
    var current = head;

    while (current) |node| {
        const next = node.next;
        allocator.destroy(node);
        current = next;
    }
}

The important part is this:

const next = node.next;
allocator.destroy(node);
current = next;

You must save next before destroying the current node.

After destroy, the current node is no longer valid.

Doubly Linked List

A doubly linked list stores two links:

previous <- [value] -> next

A node might look like this:

const Node = struct {
    value: i32,
    prev: ?*Node,
    next: ?*Node,
};

This allows movement in both directions.

null <- [10] <-> [20] <-> [30] -> null

Doubly linked lists make removal easier when you already have a pointer to the node, because you can update both neighbors.

But each node uses more memory.

Zig Standard Library Linked Lists

Zig’s standard library includes linked list utilities.

Depending on the version and API, you may see types such as intrusive linked lists. The key idea is that the link fields are stored inside your own node type instead of wrapping each value in a separate container object.

The concept looks like this:

const Node = struct {
    value: i32,
    next: ?*Node,
    prev: ?*Node,
};

This style is common in systems programming.

The node is the data. The links are part of the data structure itself.

Intrusive vs Non-Intrusive Lists

A non-intrusive list owns separate list nodes:

ListNode(value, next)

Your value is placed inside the node.

An intrusive list puts the link fields inside your own type:

const Job = struct {
    id: u32,
    name: []const u8,
    next: ?*Job,
    prev: ?*Job,
};

This can be efficient because it avoids extra wrapper allocations.

It also gives you control over memory layout.

The cost is that the data type now knows it is part of a list.

When Linked Lists Are Useful

Linked lists can be useful when:

You already have pointers to nodes.

You need to remove nodes without shifting many elements.

You need stable addresses for nodes.

You are writing low-level systems code.

You are managing memory blocks, queues, schedulers, or intrusive structures.

Examples:

ready queue in a scheduler
free list in an allocator
list of active timers
linked list of parsed tokens
intrusive list of game objects

When Not to Use a Linked List

Do not use a linked list just because it sounds flexible.

For many programs, ArrayList is better.

An ArrayList is usually better when you need:

fast iteration
index access
compact memory
simple ownership
append-heavy workloads
sorting
binary search

This is especially true for beginners.

If you are unsure, start with ArrayList.

Move to a linked list only when you have a clear reason.

Common Beginner Mistakes

The first mistake is forgetting that unlinking is not freeing.

This removes a node from the chain:

first.next = node_to_remove.next;

But if node_to_remove was allocated on the heap, its memory still exists. You must call:

allocator.destroy(node_to_remove);

The second mistake is using a pointer after freeing it.

Wrong:

allocator.destroy(node);
current = node.next;

After destroy, node.next is invalid.

Save the next pointer first.

The third mistake is losing the rest of the list during insertion.

Wrong order:

first.next = &second;
second.next = first.next;

Now second.next points to itself.

Correct order:

second.next = first.next;
first.next = &second;

The fourth mistake is expecting fast index access.

A linked list cannot jump directly to item 500. It must walk node by node.

A Useful Mental Model

An ArrayList is a row of boxes.

[10][20][30][40]

A linked list is a chain of boxes.

[10] -> [20] -> [30] -> [40]

The array is better when you want to scan many items quickly.

The linked list is better when you want to splice nodes without moving the stored values.

Summary

A linked list stores items as nodes connected by pointers.

A singly linked node usually contains:

const Node = struct {
    value: T,
    next: ?*Node,
};

A doubly linked node also stores prev.

Linked lists make insertion and removal cheap when you already have the relevant node, but they are usually worse than arrays for iteration and indexing.

In Zig, linked lists also teach important pointer skills: optional pointers, heap allocation, node ownership, pointer updates, and safe destruction.