comptime T (episode 14), searched, inserted into, and removed from, all with the ?*Node optionals you now know cold from episode 106;update array is the trick that makes insert and remove fall out of that loop almost for free;std.testing.allocator (episode 12);?*Node, and allocator ownership are fuzzy, re-read that one first;T and own every byte;Learn Zig Series):Last episode I closed with a promise: let a node hold more than one forward pointer, pointers that skip ahead by different strides, and the humble linked list stops being a slow O(n) walk and becomes something you can search in logarithmic time. That structure has a name -- the skip list -- and it is one of my favourite things to teach, because it delivers balanced-tree performance without a single line of the rotation logic that makes balanced trees miserable to write. It gets there by cheating in the most honest way imaginable: it flips coins. Before we build it, let me clear the small debt from episode 106.
Exercise 1 -- reverse a singly linked list in place. The classic three-pointer walk: keep the node you already flipped (prev), the node you're on (curr), and stash next before you overwrite the link, or you saw off the branch you're standing on. No allocations, no new nodes, just rewiring.
// Add this inside SinglyLinkedList(comptime T: type). We reverse by walking once and
// flipping each node's `next` to point at its predecessor. `next` MUST be read before
// we overwrite `node.next`, or the rest of the list vanishes -- same "save before you
// clobber" discipline as the deinit loop from last episode.
fn reverse(self: *Self) void {
var prev: ?*ListNode = null;
var curr = self.head;
while (curr) |node| {
const next = node.next; // stash the rest of the list before we cut the link
node.next = prev; // flip this node to point backward
prev = node; // advance the "already reversed" cursor
curr = next; // advance the "still to do" cursor
}
self.head = prev; // the old tail is the new head
}
The empty and single-node cases need no special handling -- with an empty list curr is null and the loop never runs; with one node it runs once, sets that node's next to null (which it already was), and reassigns head to itself. Elegant precisely because it doesn't special-case anything.
Exercise 2 -- popBack and insertAfter for the doubly linked list. popBack is almost free because we already wrote O(1) remove last episode: grab the tail's value, then let remove do the splicing. insertAfter is the mirror of pushBack, patching four pointers and minding the case where we insert after the current tail.
// Both go inside DoublyLinkedList(comptime T: type) from episode 106.
// popBack: the tail's value out, then reuse remove() -- no need to duplicate splice logic.
fn popBack(self: *Self) ?T {
const node = self.tail orelse return null;
const value = node.value;
self.remove(node); // O(1), and it frees the node for us
return value;
}
// insertAfter: splice a fresh node in right behind `node`. The one case to get right is
// inserting after the current tail -- then there is no `node.next`, and the fresh node
// becomes the new tail.
fn insertAfter(self: *Self, node: *ListNode, value: T) !*ListNode {
const fresh = try self.allocator.create(ListNode);
fresh.* = .{ .value = value, .prev = node, .next = node.next };
if (node.next) |n| n.prev = fresh else self.tail = fresh;
node.next = fresh;
self.len += 1;
return fresh;
}
Exercise 3 -- a working LRU cache on top of the doubly linked list plus a hash map (episode 22). The hash map gives O(1) "where is this key", the list gives O(1) "make this the most-recent" and O(1) "evict the least-recent". Neither can do it alone; married, they're the LRU workhorse.
// A real, compilable LRU cache. Uses episode 106's DoublyLinkedList for recency order
// and a std.AutoHashMap for lookup. On a hit we move the node to the back (most recent);
// on overflow we evict the front (least recent). Note the honest trade: because our
// ep106 remove() frees the node, "move to back" is remove-then-pushBack rather than an
// in-place relink. A production list would expose an unlink-without-free to avoid that.
fn LruCache(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Entry = struct { key: K, value: V };
const List = DoublyLinkedList(Entry);
map: std.AutoHashMap(K, *List.ListNode),
order: List,
capacity: usize,
fn init(allocator: std.mem.Allocator, capacity: usize) Self {
return .{
.map = std.AutoHashMap(K, *List.ListNode).init(allocator),
.order = List.init(allocator),
.capacity = capacity,
};
}
fn deinit(self: *Self) void {
self.order.deinit(); // frees every node
self.map.deinit();
}
fn get(self: *Self, key: K) ?V {
const node = self.map.get(key) orelse return null;
const entry = node.value; // copy out before remove frees the node
self.order.remove(node);
const fresh = self.order.pushBack(entry) catch return null;
self.map.put(key, fresh) catch {}; // re-point the map at the new node
return entry.value;
}
fn put(self: *Self, key: K, value: V) !void {
if (self.map.get(key)) |node| { // overwrite: drop the old node first
self.order.remove(node);
_ = self.map.remove(key);
}
const node = try self.order.pushBack(.{ .key = key, .value = value });
try self.map.put(key, node);
if (self.order.len > self.capacity) { // over budget: evict least-recent
const oldest = self.order.head.?;
const old_key = oldest.value.key;
self.order.remove(oldest);
_ = self.map.remove(old_key);
}
}
};
}
That's the debt paid. Nota bene: exercise 3 is the seed of a pattern -- "a fast index married to an ordered chain" -- that comes back hard today, because a skip list is exactly that idea folded in on itself. Let's build it.
Imagine a sorted linked list of a thousand nodes. Finding a value means walking up to a thousand next pointers -- O(n), miserable. Now imagine you keep a second list on top that contains only every other node, with each of those nodes pointing both down into the full list and forward to the next node in the express lane. To search, you ride the express lane until you overshoot, drop down one level, and continue. You've halved the walk. Stack another express lane on top of that, holding every fourth node, and you halve it again. Keep stacking and each level doubles your stride, so a list of n elements needs about log2(n) levels and a search touches only a handful of nodes per level. That is a skip list: a tower of sorted linked lists, sparse at the top, dense at the bottom, where the bottom level holds everything and every level above is a shrinking express lane.
The genius bit -- the thing that makes it practical rather than a bookkeeping nightmare -- is how we decide which nodes ride which express lanes. A rigid "every other node" scheme falls apart the instant you insert or delete, because you'd have to renumber half the structure to keep the levels perfectly spaced. So we don't keep them perfectly spaced. When a new node arrives, it flips a coin: heads, it gets promoted to the next level up and flips again; tails, it stops. A node's height is just how many heads it flipped in a row (plus one). On average half the nodes reach level 2, a quarter reach level 3, an eighth reach level 4, and so on -- which is exactly the density the ideal express-lane scheme wanted, achieved with zero coordination and zero rebalancing. Randomness does the balancing for free. That still delights me after all these years ;-)
In episode 106 a node had one next. Here a node has a whole array of forward pointers -- one per level it participates in -- and its length is its height. A tall node reaches into the high express lanes; a short node only exists on the ground floor. Because heights vary per node and are decided at runtime, that array has to be a heap-allocated slice (episode 5's slices, episode 7's allocator), sized when the node is born.
const std = @import("std");
// A skip-list node carries its value and a SLICE of forward pointers -- forward[i] is
// "the next node at level i". The slice length is this node's height, decided by coin
// flips at insert time. forward[0] threads the complete bottom-level list (every node);
// higher indices are the sparse express lanes. Each entry is a ?*Node -- the same
// optional pointer from episode 106, meaning "next at this level, or the honest end".
fn skipNode(comptime T: type) type {
return struct {
value: T,
forward: []?*@This(),
};
}
Compare that to last episode's next: ?*Node. The element type is identical -- an optional pointer, "a next node or nothing". We've just gone from one of them to a slice of them. Everything you learned about peeling optionals with if/orelse applies unchanged; there's simply more of it, indexed by level.
The manager type holds a sentinel head -- a dummy node whose value is meaningless but whose forward slice is full-height (max_level entries), so it can point into every express lane at once. Searches always start from this head. We also carry the current highest level actually in use (so we don't waste time descending through empty top lanes), a length, an allocator, and a seeded random number generator. Seeding it explicitly matters enormously for testing, as we'll see.
fn SkipList(comptime T: type, comptime lessThan: fn (a: T, b: T) bool) type {
return struct {
const Self = @This();
const Node = skipNode(T);
const max_level: usize = 16; // supports ~2^16 = 65k elements comfortably at p=0.5
const p: f64 = 0.5; // promotion probability -- the coin's bias
head: *Node, // sentinel: value is unused, forward has max_level entries
level: usize, // highest level currently in use (1 = ground floor only)
len: usize,
allocator: std.mem.Allocator,
rng: std.Random.DefaultPrng,
fn init(allocator: std.mem.Allocator, seed: u64) !Self {
const head = try allocator.create(Node);
head.forward = try allocator.alloc(?*Node, max_level);
@memset(head.forward, null); // head points nowhere until we insert
head.value = undefined; // sentinel value is never read
return .{
.head = head,
.level = 1,
.len = 0,
.allocator = allocator,
.rng = std.Random.DefaultPrng.init(seed),
};
}
// Coin-flip height: start at 1, and while the coin says "promote" (and we haven't
// hit the ceiling), climb. At p=0.5 this yields height>=2 half the time, >=3 a
// quarter of the time, ... -- precisely the express-lane density we want.
fn randomLevel(self: *Self) usize {
var lvl: usize = 1;
while (self.rng.random().float(f64) < p and lvl < max_level) : (lvl += 1) {}
return lvl;
}
fn createNode(self: *Self, value: T, height: usize) !*Node {
const node = try self.allocator.create(Node);
node.forward = try self.allocator.alloc(?*Node, height);
@memset(node.forward, null);
node.value = value;
return node;
}
};
}
Passing lessThan as a comptime function parameter (episode 14) is how we stay generic over ordering without hard-coding <. The standard library's ordered containers take a comparator for the same reason: T might be a struct you want sorted by one field, and only you know the order. For u32 you'd pass a two-line "a is less than b" function and be done.
Every operation on a skip list -- find, insert, remove -- begins with the same descent. Start at the sentinel head on the highest level in use. Slide forward along that level as long as the next node's value is still less than your target. The moment the next node would overshoot (or the lane ends), drop down one level and keep sliding. When you fall off the bottom level, the node immediately to your right is the only possible match. That's the entire algorithm, and it's genuinely just a staircase: right, right, down, right, down, right.
// find: descend from the top express lane, sliding right while the next value is still
// too small, dropping a level each time we'd overshoot. After the bottom level, the
// candidate is exactly forward[0] of wherever we stopped. Returns the node or null.
fn find(self: *Self, value: T) ?*Node {
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1; // levels are 0-indexed; self.level is a count, so pre-decrement
while (node.forward[i]) |next| {
if (lessThan(next.value, value)) node = next else break;
}
}
// `node` is now the greatest node strictly less than `value` (or the head).
const candidate = node.forward[0] orelse return null;
// Equal means: neither less than the other. That's how we express "==" using only lessThan.
if (!lessThan(candidate.value, value) and !lessThan(value, candidate.value)) return candidate;
return null;
}
Notice the little trick at the end: we only have a lessThan, no equals, so we express equality as "neither is less than the other". That's a standard move when you build ordered structures from a single comparator, and it's worth internalising -- it keeps the interface minimal and it's how the real containers do it too. The expected cost of this descent is O(log n), because we spend O(1) sliding per level on average and there are O(log n) levels. The worst case is O(n) -- if the coins conspire to make every node the same height you've got a plain linked list again -- but the probability of that decays so fast it's a non-issue in practice, which is the whole probabilistic bargain.
Insert is the search you just wrote, with one addition: as you descend, you remember the last node you stood on at each level -- the node whose forward pointer at that level will need rewiring to point at the newcomer. We stash those in an update array indexed by level. Once we've found the insertion point, we roll a height for the new node, patch any brand-new top levels to start at the head, and splice the node into every level up to its height. It's the doubly-linked splice from last episode, done once per level the node reaches.
// insert: descend while recording, in `update[i]`, the last node we passed at level i --
// each of those is a node whose forward[i] must be rerouted through the newcomer. Then
// roll a height, extend the active level if this node is the new tallest, and splice.
fn insert(self: *Self, value: T) !void {
var update: [max_level]*Node = undefined;
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (lessThan(next.value, value)) node = next else break;
}
update[i] = node; // remember the pre-insertion node at THIS level
}
const lvl = self.randomLevel();
if (lvl > self.level) {
// The new node is taller than anything so far: the new top lanes start at the head.
var j = self.level;
while (j < lvl) : (j += 1) update[j] = self.head;
self.level = lvl;
}
const fresh = try self.createNode(value, lvl);
var k: usize = 0;
while (k < lvl) : (k += 1) {
fresh.forward[k] = update[k].forward[k]; // new node inherits what update[k] pointed to
update[k].forward[k] = fresh; // and update[k] now points at the new node
}
self.len += 1;
}
Read the splice loop against episode 106's pushBack and it's the same two-line dance -- "new node inherits the old link, old node points at new node" -- just repeated for each level the coin granted. This implementation allows duplicate values (a new equal key simply lands next to the old one); if you wanted set semantics you'd check for an existing match before inserting and update in place instead. I'll leave that flavour to the exercises.
Remove is insert's twin. Same descent, same update array. Once we've descended, the node to unlink (if it exists) is update[0].forward[0]. We walk up from the ground floor unhooking it at each level it participates in -- and we stop the moment a level's forward pointer isn't the victim, because that means the victim never reached this level. Finally we free the node's tower and the node itself (episode 7's ownership rule: whoever allocated it frees it), and we trim any now-empty top levels so future searches don't descend through dead lanes.
// remove: find the node via the recorded update[] path, then unhook it level by level.
// Returns true if a matching node was found and freed, false if it wasn't present.
fn remove(self: *Self, value: T) bool {
var update: [max_level]*Node = undefined;
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (lessThan(next.value, value)) node = next else break;
}
update[i] = node;
}
const target = update[0].forward[0] orelse return false;
if (lessThan(target.value, value) or lessThan(value, target.value)) return false; // not equal -> not present
var k: usize = 0;
while (k < self.level) : (k += 1) {
if (update[k].forward[k] != target) break; // target didn't reach this high; done
update[k].forward[k] = target.forward[k]; // splice the express lane past it
}
self.allocator.free(target.forward); // free the tower slice...
self.allocator.destroy(target); // ...then the node (order matters: read before free)
// Trim empty top levels so we don't descend through dead air on the next search.
while (self.level > 1 and self.head.forward[self.level - 1] == null) : (self.level -= 1) {}
self.len -= 1;
return true;
}
The update[k].forward[k] != target guard is the subtle line. A short node only lives on the low levels, so above its height the express lanes point over it to something else. The instant we see a level that doesn't point at our victim, we know the victim isn't up there and we're finished -- no need to climb to max_level blindly. And as always, we read target.forward[k] before we free target, the exact use-after-free trap I waved both hands at last episode.
Cleaning up the whole structure is the same ground-floor walk as a plain linked list, because forward[0] threads every node in order. We free each node's tower slice, then the node, then the sentinel head's slice and the head itself.
// deinit: forward[0] is the complete bottom-level list, so one walk visits every node.
// Free each node's tower slice AND the node; finally free the sentinel head.
fn deinit(self: *Self) void {
var it = self.head.forward[0];
while (it) |node| {
it = node.forward[0]; // read next BEFORE freeing (episode 106's lesson)
self.allocator.free(node.forward);
self.allocator.destroy(node);
}
self.allocator.free(self.head.forward);
self.allocator.destroy(self.head);
}
Here's the wrinkle a probabilistic structure adds: if the RNG is truly random, your test does something slightly different every run, and a test you can't reproduce is a test you can't trust. The fix is the same one game developers and simulation writers use -- seed the generator with a fixed value. Same seed, same sequence of coin flips, same tower heights, byte-for-byte identical structure every single run. The randomness that balances the structure at runtime becomes perfectly repeatable under test. Pair that with std.testing.allocator (episode 12) and you get the two things that matter: correct ordering and proof that not one node leaked.
fn u32Less(a: u32, b: u32) bool {
return a < b;
}
test "skip list: ordered membership and no leaks" {
var list = try SkipList(u32, u32Less).init(std.testing.allocator, 0x5EED); // fixed seed!
defer list.deinit(); // testing.allocator fails the test if this frees too little
// Insert deliberately out of order -- the skip list must sort them for us.
const values = [_]u32{ 42, 7, 99, 7, 13, 3, 56 };
for (values) |v| try list.insert(v);
try std.testing.expectEqual(@as(usize, values.len), list.len); // duplicates allowed
// Everything we put in is findable...
try std.testing.expect(list.find(3) != null);
try std.testing.expect(list.find(99) != null);
// ...and things we never inserted are not.
try std.testing.expect(list.find(100) == null);
try std.testing.expect(list.find(0) == null);
// The bottom level MUST be fully sorted ascending -- the load-bearing invariant.
var it = list.head.forward[0];
var prev: u32 = 0;
while (it) |node| : (it = node.forward[0]) {
try std.testing.expect(node.value >= prev);
prev = node.value;
}
// Remove present and absent keys, and confirm the counts and membership react.
try std.testing.expect(list.remove(13)); // present -> true
try std.testing.expect(!list.remove(1000)); // absent -> false
try std.testing.expectEqual(@as(usize, values.len - 1), list.len);
try std.testing.expect(list.find(13) == null);
}
That walk over forward[0] checking node.value >= prev is the assertion I'd defend hardest in review: it proves the single invariant everything else depends on -- the ground floor is sorted. If insert botched a splice, this catches it instantly, in stead of letting a subtly corrupt structure limp along and fail somewhere unrelated three functions later. And because we seeded the RNG, this test is as deterministic as any test over a sorted array, despite the coins flipping under the hood.
Skip lists give you expected O(log n) search, insert, and delete -- the same asymptotic class as a balanced binary search tree. The word "expected" is doing real work: it's an average over the coin flips, not a guarantee. There's a vanishingly small chance the RNG produces a pathological all-same-height structure that degrades to O(n), but "vanishingly small" here means probabilities like 2 raised to negative large numbers -- less likely than your machine being hit by a cosmic ray mid-search. In exchange for that theoretical wart, you get code you can actually write correctly on the first try, which is not something anyone says about red-black trees.
The cache story is the same uncomfortable truth from last episode, and I won't sugar-coat it: a skip list is a pointer-chasing structure, so every hop is a potential cache miss (episode 34's territory), and against a plain sorted array searched by binary search it loses on raw lookup speed because the array is contiguous and cache-friendly. So why does anyone use one? Because a sorted array is O(n) to insert into the middle -- you have to shove everything over -- while a skip list splices in O(log n) without moving a byte. The skip list wins precisely when you need a container that stays sorted and mutates constantly: frequent inserts and deletes interleaved with lookups and occassional range scans. If your data is write-once-read-many, sort an array and binary-search it; if it churns, the skip list earns its pointers.
The headline user is Redis. Its sorted set type -- the thing behind every leaderboard, every "top N by score", every priority queue people bolt onto Redis -- is a skip list underneath (paired with a hash map, exactly the marriage from exercise 3, so it can do both O(1) lookup-by-member and O(log n) ordered range queries). Redis's creator picked a skip list over a balanced tree explicitly because it's simpler to implement, simpler to get right, and just as fast in practice. When you run ZADD and ZRANGE, you're driving the structure you just built.
Beyond Redis, skip lists show up in the memtables of LSM-tree databases like LevelDB and RocksDB -- the in-memory sorted buffer that absorbs writes before they're flushed to disk needs fast ordered inserts, which is the skip list's sweet spot. They also turn up in concurrent-data-structure libraries (Java's ConcurrentSkipListMap is the famous one), and the reason ties directly back to our design: because there are no rotations, a lock-free concurrent skip list is achievable, whereas a lock-free balanced tree is a research paper you probably don't want to implement on a deadline. The absence of rebalancing isn't just a convenience for you and me -- it's what makes the structure friendly to parallelism.
In C, a skip list is a comfortable afternoon's work -- William Pugh's original 1990 paper includes C-flavoured pseudocode that's almost copy-paste ready, and the whole thing is maybe a hundred lines. The catch is the same as every C data structure: the forward-pointer arrays are raw malloc'd memory with no bounds checking, an off-by-one in the level indexing is silent heap corruption, and there's no testing.allocator to shout when you forget to free a tower. Zig doesn't change the algorithm one bit -- our code is the same shape as Pugh's -- but ?*Node turns "did you handle the end of the lane" into a compile-time obligation, and the testing allocator turns leaks into red bars. Same structure, far fewer 3am debugging sessions.
In Rust, the skip list is less painful than the doubly linked list was, which surprises people. A skip list's pointers all flow strictly forward -- no node points back at its predecessor -- so you avoid the mutual-aliasing nightmare that sent us into Rc<RefCell<>> or unsafe last episode. You still fight the borrow checker over the multiple forward pointers sharing access, and serious crates like crossbeam-skiplist still reach for unsafe and atomics for the concurrent case, but a simple single-threaded skip list in safe Rust is far more tractable than a doubly linked one. It's a nice illustration that "which structure is hard in Rust" is really "which structure has backward or shared mutable pointers".
In Go, you'd typically pull in a third-party package (the standard library has no skip list), and the generics added in Go 1.18 finally make a clean typed one possible without interface{} boxing on every element. Idiomatically, though, a Go programmer reaching for "sorted with fast inserts" often just uses a map plus a slice they re-sort, or grabs a red-black tree package -- the skip list is more a specialist's tool there. Our Zig version, by contrast, owns every allocation explicitly and pays no GC tax, which matters exactly in the write-heavy hot paths (memtables, leaderboards) where skip lists actually live.
count(self: *Self, value: T) usize that returns how many nodes hold a value equal to the target. Since our insert permits duplicates, they sit adjacent on forward[0]; find the first match with the usual descent, then walk forward[0] counting equal values until one isn't. Test it against a list containing several copies of the same key.range(self, lo: T, hi: T, out: *std.ArrayList(T)) !void that appends, in sorted order, every value v with lo <= v <= hi. Descend to the first node >= lo, then walk forward[0] collecting until you pass hi. This is the operation Redis's ZRANGEBYSCORE is built on -- prove it returns the right slice for a query fully inside, partly overlapping, and entirely outside the data.insert take a key and a value, treat equal keys as the same entry (update the value in place instead of adding a duplicate), and add get(key) ?V. You'll compare keys with lessThan on the key type only. Back it with std.testing.allocator and prove that overwriting an existing key does not change len and does not leak.Step back and notice the shape of what we did: we took a linked list, gave each node a random number of forward pointers, and bought ourselves logarithmic search without ever writing a rebalancing rule. The balancing came from probability. That's one of two great answers to the question "how do I keep an ordered collection fast under constant mutation" -- the randomised answer. The other answer is deterministic: instead of trusting coins, you enforce a strict structural rule and do real work to maintain it on every insert and delete, so the balance is guaranteed rather than merely expected. That family of structures fans out from a simple binary node into shapes that pack many keys into each node -- tuned, in the fastest of them, to the size of a disk block or a cache line, so that touching memory once buys you a whole fistful of comparisons. That deterministic road is where we go next. Same first principles -- nodes, pointers, ownership, the optionals you now know cold -- pointed at guaranteed balance in stead of probable balance. One pointer at a time, we keep climbing.
Thanks for reading, and de groeten!
@scipio