>_ barehands / blog ← Challenges

Express Lanes for Sorted Data: A Skip List Without the Borrow-Checker Fight

Jun 10, 2026

A skip list with express lanes on higher levels that a search drops down through

A balanced tree gets you sorted data with O(log n) operations, but the balancing (rotations, color flips, the cases you copy from a textbook and pray) is famously fiddly. A skip list reaches the same O(log n) with a structure you could explain to a child: a linked list where some nodes also carry express lanes that skip over many others, and the height of each node's tower is decided by flipping a coin.

It is the structure behind Redis sorted sets and LevelDB's memtable, and it is delightful precisely because it has no balancing logic at all. The randomness does the balancing for you.

How a search works

Every node sits on the bottom level (level 0, the full linked list). Some nodes also appear on level 1, fewer on level 2, and so on, each level roughly half as populated as the one below. To find a key, you start at the top level of the head sentinel and walk right while the next key is smaller than your target, then drop down a level and repeat. The high lanes let you leap over big stretches; the low lanes let you land precisely. Expected cost: O(log n), because each level halves the work.

Inserting is the same search, but you remember the last node you stood on at each level (the update array), then splice your new node in at exactly those points, up to its randomly chosen height.

The Rust problem, and the Rust answer

Here is the catch. A skip list node holds a vector of forward links, one per level of its tower, and those links point at other nodes that point back, and you mutate them while you hold references all over the place. That is pointer-heavy, mutable, aliased linked data, which is the borrow checker's least favorite thing. The naive Vec<Option<Box<Node>>>-with-references design will not compile, and the Rc<RefCell<>> version is a runtime-borrow minefield.

The idiomatic Rust move is to not use pointers at all. Put every node in one Vec (an arena) and make the links plain usize indices into it:

struct Node {
    key: i32,
    val: i32,
    next: Vec<Option<usize>>, // forward link per level, by index
}

pub struct SkipList {
    nodes: Vec<Node>, // the arena: owns every node
    head: usize,      // sentinel
    level: usize,
    rng: u64,         // tiny xorshift, for tower heights
}

Now a "link" is just a number, so there is no aliasing to reason about and no unsafe. Walking the list reads self.nodes[x].next[lvl]; splicing rewrites a few indices. The search core is unremarkable, which is the whole point:

while let Some(nx) = self.nodes[x].next[lvl - 1] {
    if self.nodes[nx].key < key { x = nx; } else { break; }
}

And the coin flip that picks a tower height is a four-line PRNG, kept built-in so the structure is deterministic and dependency-free:

fn rand_level(&mut self) -> usize {
    let mut lvl = 1;
    while lvl < MAX_LEVEL {
        self.rng ^= self.rng << 13;
        self.rng ^= self.rng >> 7;
        self.rng ^= self.rng << 17;
        if self.rng & 1 == 0 { break; } // ~50% chance to stop each level
        lvl += 1;
    }
    lvl
}

Two lessons in one structure

About skip lists: randomness is a legitimate substitute for balancing logic. You give up worst-case guarantees (a very unlucky run of coin flips could make a tall, useless tower) in exchange for expected O(log n) and an implementation with no special cases. In practice the trade is great, which is why production databases ship them.

About Rust: when a data structure is "all pointers," reach for an index arena before you reach for Rc<RefCell<>> or unsafe. Storing nodes in a Vec and linking by index turns a borrow-checker brawl into ordinary code. It is the same move that tames LRU caches, graphs, and trees. Indices are pointers that the borrow checker does not have to police, and that is exactly what you want for a web of nodes that all refer to each other.

A coin, a vector, and some indices, and you have an ordered map that competes with a balanced tree and never needs rebalancing.

Build it yourself. Solve the Skip List challenge on barehands and get graded on correctness and speed. No crates, just the standard library.

← All posts