A few years ago, I was working with a developer who was trying to build a custom priority queue for a high-frequency trading simulation. He had started with a standard binary heap, but he needed the ability to iterate through the elements in sorted order frequently without destroying the heap. He tried implementing a Red-Black tree, but he spent nearly a week just fighting the rotation logic and the borrow checker's refusal to let him swap nodes around. He was exhausted. I told him to stop over-engineering the balance and just implement a Skip List. He looked at me like I was suggesting we write the whole thing in Assembly. But once he saw that he could get $O(\log n)$ search and insert using nothing but linked lists and a coin flip, he was hooked. He traded the complex rotation invariants for a bit of probability, and the code became significantly more maintainable.

At its core, a Skip List is just a sorted linked list with "express lanes." If you're looking for a value in a standard linked list, you have to touch every single node. In a Skip List, we build multiple layers of lists. The bottom layer has every element. The layer above it skips some elements, the one above that skips even more, and so on. You start at the top level, jump across the big gaps, and then drop down a level when you've overshot your target. It's essentially a binary search performed on a linked list.

Designing the Layered Node Structure

In Rust, the biggest hurdle isn't the algorithm—it's the memory layout. A Skip List node needs to point to multiple "next" nodes (one for each level it exists in). If you try to use Box for every level, you'll quickly run into ownership nightmares because you're essentially creating a complex graph. While you could use Rc<RefCell<T>>, that introduces runtime overhead that defeats the purpose of using Rust for high-performance data structures.

The "pro" move here is to use an arena—a Vec that owns all the nodes—and use indices (usize) as pointers. This bypasses the borrow checker's struggle with cyclic or multi-referenced graphs and keeps your data contiguous in memory, which is much friendlier to the CPU cache. Here is how we define our node and the list wrapper:

struct Node<T> {
    value: T,
    // forward[i] is the index of the next node at level i
    forward: Vec<Option<usize>>,
}

pub struct SkipList<T> {
    nodes: Vec<Node<T>>,
    head: Vec<Option<usize>>, // The "start" pointers for each level
    max_level: usize,
    current_level: usize,
}

I prefer this approach because it transforms a pointer-chasing problem into an array-indexing problem. It makes the logic cleaner and the cleanup trivial: when the SkipList is dropped, the Vec is dropped, and everything vanishes without a complex recursive teardown.

Handling Probabilistic Height and Insertion

The magic of the Skip List is in how we decide how many "express lanes" a new node gets. We don't use a complex balancing algorithm; we use a random number generator. I usually implement a simple random_level function that flips a coin: as long as it's heads, we increment the level, up to a predefined maximum. This ensures that, statistically, each level has half as many nodes as the level below it.

When inserting, you have to keep track of the "update" path. Since you're moving right and then down, you need to remember the last node you visited at every single level. These are the nodes whose forward pointers will need to be updated to point to the new node. I've found that using a fixed-size array or a small Vec to store these update indices is the most straightforward way to handle this.

impl<T: Ord> SkipList<T> {
    fn insert(&mut self, value: T) {
        let mut update = vec![None; self.max_level];
        let mut curr = None;

        // Traverse from top to bottom to find insertion points
        for i in (0..self.current_level).rev() {
            while let Some(next_idx) = self.get_next_idx(curr, i) {
                if self.nodes[next_idx].value < value {
                    curr = Some(next_idx);
                } else {
                    break;
                }
            }
            update[i] = curr;
        }

        let level = self.random_level();
        if level > self.current_level {
            for i in self.current_level..level {
                update[i] = None;
            }
            self.current_level = level;
        }

        // Create the node and stitch it into the levels
        let new_node_idx = self.nodes.len();
        self.nodes.push(Node {
            value,
            forward: vec![None; level],
        });

        for i in 0..level {
            if let Some(prev_idx) = update[i] {
                self.nodes[prev_node_idx].forward[i] = Some(new_node_idx);
            } else {
                self.head[i] = Some(new_node_idx);
            }
        }
    }
}

You'll notice that get_next_idx is a helper I'd use to handle the Option wrapping. The beauty of this is that the "Search" operation is now just a simplified version of the "Insert" traversal. You just keep jumping as far as you can at the current level before dropping down. If you hit the bottom level and the next node isn't your target, the value isn't in the list.

📋 Practical Task

Implementing the Skip List Search and Level Generator

Now it's your turn to put the probabilistic logic into practice. You are provided with a partial SkipList implementation using the arena (Vec) pattern. Your task is to complete two critical components:

• The random_level method: Implement this using the rand crate. It should start at level 1 and increment the level by 1 for every "heads" (a 50% chance), capping the result at self.max_level.
• The contains method: Implement the search logic. Start from the highest current level of the list, move forward as long as the next node's value is less than the target, and drop down one level when you can no longer move forward. Return true if the value is found at the bottom level.

Constraint: Do not use unsafe code; stick to the index-based arena approach to ensure memory safety.