Zig Linked Lists

A linked list is a collection where each element holds its value and a pointer to the next element. Unlike arrays that store everything in a continuous block of memory, linked list nodes can live anywhere in memory and connect through pointers. This makes inserting or removing elements at any position fast — no shifting required.

The Concept

  Array:
  [10][20][30][40][50]   ← all together, fixed positions

  Linked list:
  [10|→] → [20|→] → [30|→] → [40|→] → [50|null]
   head                                  tail

  Each box = one node: value + pointer to next
  Last node points to null (end of list)

Building a Singly Linked List

const std = @import("std");

fn LinkedList(comptime T: type) type {
    return struct {
        const Node = struct {
            value: T,
            next:  ?*Node = null,
        };

        head:      ?*Node = null,
        allocator: std.mem.Allocator,
        len:       usize = 0,

        const Self = @This();

        fn init(allocator: std.mem.Allocator) Self {
            return .{ .allocator = allocator };
        }

        fn deinit(self: *Self) void {
            var current = self.head;
            while (current) |node| {
                const next = node.next;
                self.allocator.destroy(node);
                current = next;
            }
        }

        fn prepend(self: *Self, value: T) !void {
            const node = try self.allocator.create(Node);
            node.* = .{ .value = value, .next = self.head };
            self.head = node;
            self.len += 1;
        }

        fn append(self: *Self, value: T) !void {
            const node = try self.allocator.create(Node);
            node.* = .{ .value = value, .next = null };
            if (self.head == null) {
                self.head = node;
            } else {
                var current = self.head.?;
                while (current.next) |next| current = next;
                current.next = node;
            }
            self.len += 1;
        }

        fn printAll(self: *Self) void {
            var current = self.head;
            while (current) |node| {
                std.debug.print("{any} → ", .{node.value});
                current = node.next;
            }
            std.debug.print("null\n", .{});
        }
    };
}

Using the Linked List

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

    var list = LinkedList(i32).init(alloc);
    defer list.deinit();

    try list.append(10);
    try list.append(20);
    try list.append(30);
    try list.prepend(5);

    list.printAll();
    std.debug.print("Length: {d}\n", .{list.len});
}

Output:

5 → 10 → 20 → 30 → null
Length: 4

Insertion and Removal

        // Insert after a specific value
        fn insertAfter(self: *Self, target: T, value: T) !bool {
            var current = self.head;
            while (current) |node| {
                if (node.value == target) {
                    const new_node = try self.allocator.create(Node);
                    new_node.* = .{ .value = value, .next = node.next };
                    node.next = new_node;
                    self.len += 1;
                    return true;
                }
                current = node.next;
            }
            return false;
        }

        // Remove the first node with a specific value
        fn remove(self: *Self, value: T) bool {
            if (self.head == null) return false;
            if (self.head.?.value == value) {
                const old = self.head.?;
                self.head = old.next;
                self.allocator.destroy(old);
                self.len -= 1;
                return true;
            }
            var current = self.head.?;
            while (current.next) |next| {
                if (next.value == value) {
                    current.next = next.next;
                    self.allocator.destroy(next);
                    self.len -= 1;
                    return true;
                }
                current = next;
            }
            return false;
        }

  Insert 15 after 10:
  Before: 5 → 10 → 20 → 30 → null
  After:  5 → 10 → 15 → 20 → 30 → null

  Remove 20:
  Before: 5 → 10 → 15 → 20 → 30 → null
          skip 10 → 15 → link 15 to 30 → free 20
  After:  5 → 10 → 15 → 30 → null

The Standard Library SinglyLinkedList

Zig's standard library provides std.SinglyLinkedList for production use. It uses an intrusive design — the node is embedded inside your own struct, avoiding a separate allocation per node:

const std = @import("std");

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

    const List = std.SinglyLinkedList(u32);
    var list = List{};

    var n1 = try alloc.create(List.Node);
    var n2 = try alloc.create(List.Node);
    var n3 = try alloc.create(List.Node);
    defer alloc.destroy(n1);
    defer alloc.destroy(n2);
    defer alloc.destroy(n3);

    n1.* = .{ .data = 100 };
    n2.* = .{ .data = 200 };
    n3.* = .{ .data = 300 };

    list.prepend(n3);
    list.prepend(n2);
    list.prepend(n1);

    var it = list.first;
    while (it) |node| {
        std.debug.print("{d}\n", .{node.data});
        it = node.next;
    }
}

Array vs Linked List Trade-offs

  Operation         │ Array ([]T)   │ Linked List
  ──────────────────┼───────────────┼─────────────────
  Access by index   │ O(1) fast     │ O(n) slow
  Append to end     │ O(1) amortized│ O(n) (or O(1) with tail ptr)
  Insert at front   │ O(n) shift    │ O(1) fast
  Insert at middle  │ O(n) shift    │ O(1) once found
  Remove at front   │ O(n) shift    │ O(1) fast
  Memory use        │ Compact       │ Extra pointer per node
  Cache friendliness│ Excellent     │ Poor (scattered memory)

Use a linked list when you frequently insert or remove from the front or middle of a list, and access by index is rare. Use an array or std.ArrayList when you need fast random access and mostly append to the end. In practice, arrays outperform linked lists in most real workloads because of CPU cache locality — array elements sit next to each other in memory, so reading one often preloads nearby elements automatically.