# 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:

```text
[10][20][30][40]
```

A linked list stores items as separate nodes:

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

Each node contains two things:

```text
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:

```text
[10][20][30][40]
```

The CPU can read nearby values efficiently.

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

```text
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.

```text
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.

```text
[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.

| Structure | Strength | Weakness |
|---|---|---|
| `ArrayList` | Fast iteration and index access | Middle insert/remove may shift items |
| Linked list | Node insertion/removal without moving values | Slow index access and poor cache locality |

## Singly Linked List

A singly linked list has one pointer per node:

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

The last node points to `null`.

Here is a simple node type:

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

Read the fields:

```zig
value: i32
```

This stores the data.

```zig
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:

```text
maybe a pointer to another Node
```

## Building Nodes Manually

Here is a small linked list built from stack variables:

```zig
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:

```text
10
20
30
```

The list looks like this:

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

The variable `current` walks through the list.

```zig
var current: ?*Node = &first;
```

At each step, `current` is either:

```text
a pointer to a node
```

or:

```text
null
```

This loop continues while `current` is not null:

```zig
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:

```text
[10] -> [30]
```

We want to insert `20` after `10`.

The result should be:

```text
[10] -> [20] -> [30]
```

Pointer changes:

```zig
new_node.next = first.next;
first.next = &new_node;
```

Complete example:

```zig
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:

```text
10
20
30
```

The order of assignment matters.

Do this first:

```zig
second.next = first.next;
```

Then this:

```zig
first.next = &second;
```

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

## Removing After a Node

Suppose we have:

```text
[10] -> [20] -> [30]
```

We want to remove the node after `10`.

The result:

```text
[10] -> [30]
```

The pointer change is:

```zig
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:

```zig
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.

```zig
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:

```zig
*Node
```

Then this initializes the node:

```zig
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.

```zig
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:

```zig
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:

```text
previous <- [value] -> next
```

A node might look like this:

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

This allows movement in both directions.

```text
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:

```zig
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:

```text
ListNode(value, next)
```

Your value is placed inside the node.

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

```zig
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:

```text
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:

```text
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:

```zig
first.next = node_to_remove.next;
```

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

```zig
allocator.destroy(node_to_remove);
```

The second mistake is using a pointer after freeing it.

Wrong:

```zig
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:

```zig
first.next = &second;
second.next = first.next;
```

Now `second.next` points to itself.

Correct order:

```zig
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.

```text
[10][20][30][40]
```

A linked list is a chain of boxes.

```text
[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:

```zig
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.