Learn Zig Series (#106) - Linked Lists: Singly and Doubly

avatar

Learn Zig Series (#106) - Linked Lists: Singly and Doubly

zig.png

What will I learn?

  • Why a linked list is the simplest data structure you can build out of nothing but a node and a pointer, and why starting the data-structures arc here (rather than with something flashier) pays off for everything that follows;
  • How to build a singly linked list from scratch as a generic over comptime T (episode 14), owning its nodes through an allocator (episodes 7 and 26) and cleaning up after itself without leaking a single byte;
  • Why Zig's ?*Node -- an optional pointer -- is the quiet hero here: it makes "the list ends" and "this node has no next" the same idea the compiler forces you to handle, so a null-pointer dereference is a compile problem, not a 3am problem;
  • How a doubly linked list buys you O(1) removal of any node you already hold a pointer to, what the extra prev link and tail pointer cost you in bookkeeping, and why that one property is the reason half the systems you use lean on it;
  • What an intrusive list is (the links live inside your struct), why the standard library and the Linux kernel both prefer it, and how @fieldParentPtr lets you walk back from a link to the thing that owns it;
  • Why linked lists are cache-hostile and lose badly to an ArrayList for plain iteration -- and the handful of situations where they still win decisively;
  • How this all maps onto the equivalents in C, Rust, and Go, including why a linked list is famously the data structure that makes Rust programmers reach for unsafe.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Zig 0.14+ distribution (download from ziglang.org);
  • A solid grip on pointers and optionals from episode 8, and on allocators from episodes 7 and 26 -- a linked list is basically those two ideas holding hands, so if either is fuzzy, re-read those first;
  • Comfort with generics via comptime from episode 14, since we build these containers over an arbitrary T;
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#106) - Linked Lists: Singly and Doubly

Last episode we finished the reverse proxy and I promised a turn. All through the networking arc we leaned on slices, hash maps and pools as if they were furniture -- always just there, provided by the standard library, used without a second thought. That's fine right up until the day the stdlib's trade-offs don't fit your problem, and then you're stuck, because you never actually learned what's inside the box. So we go back to first principles now, and we start at the very bottom: the linked list, which is the simplest data structure you can build out of nothing but a value, a pointer, and an allocator. If you understand this one honestly, every fancier structure in the coming episodes is just this idea with more pointers.

Here's the whole concept in one breath. An array (episode 5) stores its elements shoulder-to-shoulder in one contiguous block -- element i lives at base + i * size, which is why indexing is instant and iteration screams. A linked list throws that layout away. Each element sits in its own little box -- a node -- allocated wherever the allocator felt like putting it, and each node holds a pointer to the next box. There is no base + i * size anymore; to reach the fifth element you must start at the first and follow four pointers. You trade random access and cache-friendliness for one thing: the ability to insert or remove an element by rewiring a pointer or two, without shoving everything else over. That trade is the entire personality of the structure, and everything below is a consequence of it.

The node is the whole idea

A node is a struct that holds a payload and a link to the next node. The link is the interesting part, and it's where Zig's type system does its first bit of quiet work. What is "the next node" when you're standing on the last node? There isn't one. In C you'd write NULL and pray every reader remembers to check it. In Zig the link is an optional pointer, ?*Node, which is a completely different animal: the compiler will not let you dereference it until you've proven it isn't null, usually by peeling it open with if or orelse. "The list ends here" and "this pointer is null" become the exact same, un-ignorable idea.

const std = @import("std");

// A node holds a value and an OPTIONAL pointer to the next node. The `?` is the
// entire safety story: `next` is either a real *Node or the honest absence of one,
// and Zig refuses to let you follow it without first handling the null case. In C
// this same field is a raw pointer and a promise; here it's a proof obligation.
fn Node(comptime T: type) type {
    return struct {
        value: T,
        next: ?*@This() = null,
    };
}

Notice we made it a generic over comptime T (episode 14), so one definition serves a list of u32, a list of Point, a list of whatever. @This() inside the returned struct refers to the node type itself, which is how a node points at another node of its own kind without us having to name the type before it exists.

A singly linked list from scratch

Now we wrap those nodes in a small manager type that owns them. Ownership is the word to hold onto: the list created each node through an allocator (episodes 7 and 26), so the list is responsible for destroying every one of them. Forget that and you leak; the good news is that Zig's testing allocator will catch you red-handed, which we'll exploit in a moment.

fn SinglyLinkedList(comptime T: type) type {
    return struct {
        const Self = @This();
        const ListNode = struct {
            value: T,
            next: ?*ListNode = null,
        };

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

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

        // Prepend a value. This is the operation a singly linked list is BORN for:
        // allocate one node, point it at the current head, make it the new head.
        // No shifting, no reallocation -- genuinely O(1) no matter how long the list.
        fn pushFront(self: *Self, value: T) !void {
            const node = try self.allocator.create(ListNode);
            node.* = .{ .value = value, .next = self.head };
            self.head = node;
            self.len += 1;
        }

        // Remove and return the front value, or null if empty. We must grab the value
        // out BEFORE we destroy the node -- reading freed memory is exactly the bug
        // the borrow checker exists to prevent in other languages, and here it's on us.
        fn popFront(self: *Self) ?T {
            const node = self.head orelse return null;
            self.head = node.next;
            const value = node.value;
            self.allocator.destroy(node);
            self.len -= 1;
            return value;
        }

        // Walk every node and free it. The list allocated them, so the list frees them.
        // This is the deinit you MUST call, and the one testing.allocator polices.
        fn deinit(self: *Self) void {
            var it = self.head;
            while (it) |node| {
                it = node.next; // read `next` BEFORE destroying, or we chase a dangling ptr
                self.allocator.destroy(node);
            }
            self.head = null;
            self.len = 0;
        }
    };
}

Read deinit twice, because it contains the single most common linked-list bug in miniature. We save node.next into it before calling destroy(node). Reverse those two lines -- destroy first, then try to read node.next -- and you're dereferencing freed memory, undefined behaviour, the kind of bug that works fine on your laptop and corrupts the heap in production on a Tuesday. Zig won't stop you from writing it wrong here (the pointer is real, the access is legal to the compiler), which is precisely why I'm pointing at it with both hands.

Iterating is the same optional-peeling dance, and it's worth seeing on its own because you'll write it a hundred times:

// Idiomatic traversal: `while (optional) |captured|` runs the body only while the
// pointer is non-null, binding the unwrapped *ListNode to `node`. The continue-
// expression advances the cursor. When `next` is finally null, the loop just ends.
var it = list.head;
while (it) |node| : (it = node.next) {
    std.debug.print("{d} ", .{node.value});
}

That while (optional) |capture| : (advance) shape is Zig idiom you should be able to write in your sleep by now (we first met it around episode 8). It reads as "for as long as there's a next node, work on it, then step forward", and the null that ends the list ends the loop for free.

The catch, and why doubly linked lists exist

The singly linked list is elegant and it is also, for quite some operations, useless. Prepending is O(1), popping the front is O(1), lovely. But suppose you're standing on a node in the middle of the list and you want to remove it. To rewire around it you need its predecessor (so you can point that predecessor's next past the doomed node) -- and a singly linked node has no idea who points at it. Your only recourse is to walk from the head again looking for "the node whose next is this one", which is O(n). For a structure whose entire selling point is cheap removal, that's a betrayal.

The fix is almost insultingly simple: give every node a second pointer, prev, aiming backward. Now a node knows both its neighbours, and removing it is a matter of introducing its two neighbours to each other and freeing it -- O(1), no walk required, as long as you already hold a pointer to the victim. We also keep a tail pointer on the list so appending to the back is O(1) too (a singly list can append to the back cheaply only if it also tracks the tail, and even then it can't cheaply remove from the back -- the doubly list gets both).

fn DoublyLinkedList(comptime T: type) type {
    return struct {
        const Self = @This();
        const ListNode = struct {
            value: T,
            prev: ?*ListNode = null,
            next: ?*ListNode = null,
        };

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

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

        // Append to the back. Because we keep a `tail`, this is O(1). The empty-list
        // case is the one to get right: with no tail, the new node becomes BOTH head
        // and tail. That single branch is where most hand-rolled versions go wrong.
        fn pushBack(self: *Self, value: T) !*ListNode {
            const node = try self.allocator.create(ListNode);
            node.* = .{ .value = value, .prev = self.tail, .next = null };
            if (self.tail) |t| {
                t.next = node;
            } else {
                self.head = node; // list was empty: this node is the head too
            }
            self.tail = node;
            self.len += 1;
            return node;
        }

        // Remove a node we already hold a pointer to -- the payoff operation. Splice
        // its predecessor to its successor and vice-versa, patching head/tail when the
        // node sits on an end. No traversal, O(1). THIS is why doubly linked lists exist.
        fn remove(self: *Self, node: *ListNode) void {
            if (node.prev) |p| p.next = node.next else self.head = node.next;
            if (node.next) |n| n.prev = node.prev else self.tail = node.prev;
            self.allocator.destroy(node);
            self.len -= 1;
        }

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

Look hard at remove, because those two lines are the whole doubly-linked payoff and they're denser than they look. if (node.prev) |p| p.next = node.next else self.head = node.next means: if I have a predecessor, point it past me; otherwise I was the head, so the head is now whoever came after me. The second line does the mirror image for the successor and the tail. Handle both ends correctly and removal of an interior node is genuinely constant time, no matter how long the list. That property -- "pull any node out instantly, given a pointer to it" -- is the reason doubly linked lists sit at the heart of LRU caches, allocator free lists, and OS scheduler run queues.

Intrusive lists: how the pros actually do it

Everything above is an owning list: the list allocates a node, copies your value into it, and owns that memory. That's the friendly, textbook design, and it's what you reach for first. But it has a real cost -- every insert is a heap allocation, and every node is a separate cache-cold hop. The standard library and the Linux kernel both prefer a sharper design called an intrusive list, and it's worth meeting now because it explains a Zig builtin you'll see everywhere.

In an intrusive list, the link fields don't live in a node the list allocates -- they live inside your own struct. Your Task (or Connection, or whatever) carries a next/prev pair as an ordinary field, and the list just threads through objects you already own. No extra allocation per insert, and the object and its links share a cache line. The twist: given a pointer to the embedded link, how do you get back to the Task that contains it? That's exactly what @fieldParentPtr is for.

// Intrusive style: the links live INSIDE the payload type, so putting a Task on a list
// costs zero extra allocations. Given a pointer to the `.node` field, @fieldParentPtr
// walks back to the Task that owns it -- the same trick the kernel's list_head uses.
const Link = struct { prev: ?*Link = null, next: ?*Link = null };

const Task = struct {
    id: u32,
    node: Link = .{},

    fn fromLink(link: *Link) *Task {
        return @fieldParentPtr("node", link);
    }
};

Zig's own std.DoublyLinkedList is intrusive in exactly this spirit: you embed a node field in your type and the list stitches your objects together without ever allocating on your behalf. It's a little more ceremony to use, but for hot paths where you're already holding the objects -- connections in a pool, tasks in a scheduler -- it's the design that pays. I'm not going to pretend the owning version we built is what a kernel uses; it isn't, and now you know why ;-)

Testing without leaking a byte

Because these structures own heap memory, the test that matters most isn't "does push then pop give the right value" -- it's "did we free everything". Zig hands you std.testing.allocator for exactly this: it tracks every allocation and fails the test if anything is still outstanding when the test ends. Pair it with defer list.deinit() and a leak becomes a red bar, not a slow memory climb you notice in production three weeks later (episode 12's whole philosophy, applied).

test "singly list: LIFO order and no leaks" {
    var list = SinglyLinkedList(u32).init(std.testing.allocator);
    defer list.deinit(); // if this frees too little, testing.allocator fails the test

    try list.pushFront(1);
    try list.pushFront(2);
    try list.pushFront(3);
    try std.testing.expectEqual(@as(usize, 3), list.len);

    // pushFront prepends, so pop order is the reverse of insert order.
    try std.testing.expectEqual(@as(?u32, 3), list.popFront());
    try std.testing.expectEqual(@as(?u32, 2), list.popFront());
    try std.testing.expectEqual(@as(?u32, 1), list.popFront());
    try std.testing.expectEqual(@as(?u32, null), list.popFront()); // empty -> null
}

The doubly linked list earns a test aimed squarely at its reason for existing -- yanking an interior node in O(1) and leaving the chain, the length, and both ends consistent:

test "doubly list: O(1) interior removal keeps the chain honest" {
    var list = DoublyLinkedList(u32).init(std.testing.allocator);
    defer list.deinit();

    _ = try list.pushBack(10);
    const middle = try list.pushBack(20);
    _ = try list.pushBack(30);

    list.remove(middle); // pull the middle node out by pointer -- no traversal

    try std.testing.expectEqual(@as(usize, 2), list.len);
    // head and tail must now be neighbours: 10 <-> 30, nothing dangling in between.
    try std.testing.expectEqual(@as(u32, 10), list.head.?.value);
    try std.testing.expectEqual(@as(u32, 30), list.tail.?.value);
    try std.testing.expectEqual(list.tail, list.head.?.next);
    try std.testing.expectEqual(list.head, list.tail.?.prev);
}

Those last two assertions are the ones I'd defend hardest in review: after a middle removal, head.next must be the tail and tail.prev must be the head. If your remove botched either splice, one of them points at freed memory or at the node you just deleted, and this test goes red instantly in stead of silently corrupting the list.

Performance: the uncomfortable truth

Now the part the textbooks undersell. A linked list looks fast on paper -- O(1) insert, O(1) remove -- but Big-O counts operations, not cache misses, and on modern hardware the cache miss is what actually costs you. Iterating a linked list means following a pointer to a node that could be anywhere in memory, then following its next to another node that could be anywhere else. Every hop is a potential cache miss, and a cache miss is ~100+ cycles the CPU spends staring at a wall. An ArrayList (episode 22's neighbourhood), by contrast, is one contiguous block: the hardware prefetcher sees you marching forward and streams the next elements into cache before you ask for them. For plain iteration, the array wins so decisively it's not even a contest -- often by an order of magnitude, even though both are "O(n)".

So when does a linked list actually earn its keep? Three honest cases:

  • You splice constantly in the middle and rarely iterate the whole thing. O(1) removal given a node pointer, with no element-shifting, is a real win an array can't match.
  • You need pointers into the collection to stay valid as it grows and shrinks. An ArrayList can reallocate and move every element out from under your pointers; a linked list never moves a node once allocated, so a pointer you stashed stays good.
  • Intrusive, allocation-free membership. When an object needs to be on a list without any extra allocation (a task on a run queue, a buffer on a free list), the intrusive linked list is the natural fit.

Outside those, reach for ArrayList first and only switch when a profiler (episode 34, not your gut) tells you the shifting or the reallocation is the bottleneck. The linked list you just learned to build is a precision tool, not a default.

Real-world applications

The doubly linked list's O(1)-removal superpower shows up in more places than you'd guess. The canonical one is the LRU cache: a hash map from key to node gives you O(1) lookup, and a doubly linked list of those same nodes gives you O(1) "move this node to the front on access" and O(1) "evict the node at the back". Neither structure can do it alone; married together they're the workhorse behind page caches, database buffer pools, and CDN edges.

// The SHAPE of an LRU cache (sketch, not the full build): a hash map for O(1) find,
// a doubly linked list for O(1) recency reordering. On a hit you unlink the node and
// push it to the front; when you're over capacity you evict list.tail. The doubly
// linked list is here purely because it can pull ANY node out in O(1) -- exactly the
// property we spent this whole episode earning.
fn LruCache(comptime K: type, comptime V: type) type {
    return struct {
        map: std.AutoHashMap(K, *DoublyLinkedList(V).ListNode),
        order: DoublyLinkedList(V),
        capacity: usize,
        // get(): map.get(key) -> unlink node -> pushBack -> return value
        // put(): if over capacity, remove(order.head) and drop its map entry
    };
}

The other big one you've already brushed against: allocator free lists (episode 26). A pool allocator keeps its recycled blocks on a singly linked list threaded through the free blocks themselves -- the "next free block" pointer lives in the free memory, costing zero extra storage. Free is "push this block onto the free list", allocate is "pop the front". That's a singly linked list doing load-bearing work at the very bottom of the memory stack, and now you can see exactly how it works. OS schedulers use linked lists for run queues; adjacency-list graph representations are arrays of linked lists; the pattern is genuinely everywhere once you've built it once.

How this compares to C, Rust, and Go

In C, the intrusive doubly linked list is a rite of passage -- the Linux kernel's list_head and its container_of macro (which is @fieldParentPtr by another name) are exactly the design we sketched, and generations of C programmers have hand-written node->prev->next = node->next and gotten it subtly wrong. What Zig adds isn't a different algorithm; it's the ?*Node optional, which turns "did you check for NULL" from a code-review argument into a compile error. The pointer arithmetic is identical; the class of bug where you forget the end-of-list case is simply gone.

In Rust, the linked list is infamous -- it's the poster child for "the borrow checker and I disagree". A doubly linked list needs two nodes to point at each other, which is shared mutable aliasing, which is precisely what Rust's ownership model forbids. Rust programmers end up reaching for Rc<RefCell<Node>> (runtime-checked, allocation-heavy) or dropping into unsafe with raw pointers -- and the standard library's own LinkedList is written in unsafe under the hood for exactly this reason. There's even a famous tutorial titled roughly "learn Rust with entirely too many linked lists" whose whole premise is that this simple structure is where Rust hurts most. Zig's answer is different in spirit: it doesn't prove your pointer discipline is correct, it just gets out of your way and lets testing.allocator and a good test suite catch the mistakes. More rope, and a safety net you have to string up yourself.

In Go, you'd use container/list, which is a ready-made doubly linked list holding interface{} (now any) values -- convenient, but every element is boxed and type-asserted on the way out, and the garbage collector owns the node lifecycle so there's no deinit to write or forget. It's the "batteries included, performance later" trade Go makes everywhere: you get a working list in three lines and pay for it in allocations and type assertions. Our Zig version is more code, but you own every byte and every pointer, and there's no GC deciding when your nodes die.

Exercises

  1. Add a reverse method to SinglyLinkedList that flips the list in place -- no new allocations, just rewire every node's next to point at its predecessor and swap the head. The classic three-pointer walk (prev, curr, next) is the way; mind the empty and single-node cases.
  2. Give DoublyLinkedList a popBack that removes and returns the tail value in O(1) (returning ?T), plus an insertAfter(node, value) that splices a fresh node in immediately after a node you already hold. Both should keep head, tail, and len consistent, and both should have a test that removes/inserts at an end as well as the middle.
  3. Turn the LruCache sketch into a working cache with get(key) ?V and put(key, value) !void, backed by a std.AutoHashMap for lookup and your DoublyLinkedList for recency order. On a hit, move the node to the back; when put would exceed capacity, evict the front node and drop its map entry. Prove with std.testing.allocator that a full run of puts and evictions leaks nothing.

Where this is heading

Step back and look at what we actually built: a value, an optional pointer, an allocator, and the discipline to free what you create. That's the entire linked list, and it's the seed of everything to come. The moment you let a node hold more than one forward pointer -- pointers that skip ahead by different strides -- you get a structure that can be searched in logarithmic time instead of linear, and suddenly the humble node-and-pointer arrangement stops being a slow list and becomes something genuinely fast. That's the direction the next episode takes: same nodes, same pointers, same ?*Node optionals you now know cold, arranged so that finding an element doesn't mean walking past every element before it. We keep building upward from here, one pointer at a time.

Bedankt en tot de volgende keer!

@scipio

stem stemsocial steemstem zig programming
0
0
0.000
0 comments