372: Skip List Concept in Rust

Difficulty: 5 Level: Master Probabilistic sorted data structure with O(log n) operations and better cache behavior than tree-based alternatives.

The Problem This Solves

`BTreeMap` gives you sorted keys, `O(log n)` insert and lookup, and range queries. So why would you want a skip list? Cache performance. A `BTreeMap` node contains 11–16 keys and requires pointer chasing through arbitrary heap addresses. A skip list is a layered linked list — sequential memory access patterns make it much friendlier to CPU caches on modern hardware. Skip lists also support lock-free concurrent implementations more naturally than trees, which is why they appear in databases (LevelDB, RocksDB), language runtimes (Java's `ConcurrentSkipListMap`), and high-throughput data stores. The `crossbeam-skiplist` crate provides a production-quality concurrent skip list for Rust. For purely single-threaded code, `BTreeMap` is usually the right choice. Skip lists become interesting when you need concurrent sorted access or are tuning cache behavior at scale.

The Intuition

A skip list is a sorted linked list with multiple layers. The bottom layer is a regular sorted linked list. Each higher layer is a "fast lane" — a sparser version of the layer below, skipping over most elements. To search, you start at the top layer and walk right as long as the next element is ≤ your target, then drop down a layer and repeat. You find your target by binary-search-like jumps without a tree structure. Each element is promoted to higher layers with probability `p` (typically 0.5). This randomness gives probabilistic balance: no rebalancing needed, unlike red-black trees or AVL trees. The expected height of the tallest tower is `O(log n)`.

How It Works in Rust

The `crossbeam-skiplist` crate provides a production concurrent skip list:

use crossbeam_skiplist::SkipMap;

let map = SkipMap::new();

map.insert(3, "three");
map.insert(1, "one");
map.insert(4, "four");
map.insert(1, "one-again"); // updates value for key 1

// Sorted iteration
for entry in map.iter() {
 println!("{}: {}", entry.key(), entry.value());
}
// Output: 1: one-again, 3: three, 4: four

// Range query
for entry in map.range(1..=3) {
 println!("{}", entry.key());
}

For a conceptual single-threaded implementation, each node carries a `Vec<Option<*mut Node>>` of forward pointers — one per level the node participates in.

What This Unlocks

Concurrent sorted maps — `SkipMap` supports multiple threads without a global lock.
Database internals — LSM tree memtables (LevelDB, RocksDB) use skip lists for the in-memory sorted buffer.
Cache-friendly sorted access — sequential memory access patterns versus tree pointer chasing.

Key Differences

Concept	OCaml	Rust
Sorted map	`Map` (balanced BST, functional, persistent)	`BTreeMap` (B-tree) or `SkipMap` (skip list)
Concurrent sorted map	No stdlib equivalent	`crossbeam_skiplist::SkipMap` (lock-free)
Rebalancing	Structural (persistent trees)	Not needed (probabilistic balance)
Cache behavior	Poor (pointer chasing)	Better (more sequential layout in skip lists)

use std::collections::BTreeMap;

// Skip list concept: we use BTreeMap as the backing store with level simulation
// Real skip list needs unsafe Rust or Rc<RefCell<>> for linked nodes

struct SkipListSimulation {
    // Level 0: all elements (base level)
    level0: Vec<i32>,
    // Level 1: every ~2nd element (express lane)
    level1: Vec<i32>,
    // Level 2: every ~4th element (super express lane)
    level2: Vec<i32>,
}

impl SkipListSimulation {
    fn new() -> Self { Self { level0: Vec::new(), level1: Vec::new(), level2: Vec::new() } }

    fn rebuild_levels(&mut self) {
        self.level1 = self.level0.iter().step_by(2).copied().collect();
        self.level2 = self.level0.iter().step_by(4).copied().collect();
    }

    fn insert(&mut self, val: i32) {
        match self.level0.binary_search(&val) {
            Ok(_) => return, // already exists
            Err(i) => self.level0.insert(i, val),
        }
        self.rebuild_levels();
    }

    fn search(&self, val: i32) -> bool {
        // Search using express lanes (top-down)
        let start = match self.level2.binary_search(&val) {
            Ok(_) => return true,
            Err(i) => if i > 0 { self.level2[i-1] } else { i32::MIN },
        };
        let start1 = match self.level1.binary_search(&val) {
            Ok(_) => return true,
            Err(i) => if i > 0 { self.level1[i-1].max(start) } else { start },
        };
        // Final scan in level0
        let begin = self.level0.partition_point(|&x| x < start1);
        for &x in &self.level0[begin..] {
            if x == val { return true; }
            if x > val { break; }
        }
        false
    }

    fn delete(&mut self, val: i32) -> bool {
        if let Ok(i) = self.level0.binary_search(&val) {
            self.level0.remove(i);
            self.rebuild_levels();
            true
        } else { false }
    }
}

fn main() {
    let mut sl = SkipListSimulation::new();
    for v in [5,3,7,1,9,4,6,2,8,0,10] { sl.insert(v); }
    println!("Level 0: {:?}", sl.level0);
    println!("Level 1 (express): {:?}", sl.level1);
    println!("Level 2 (super): {:?}", sl.level2);
    println!("Search 7: {}", sl.search(7));
    println!("Search 11: {}", sl.search(11));
    sl.delete(5);
    println!("After delete 5: {:?}", sl.level0);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn insert_search() {
        let mut sl = SkipListSimulation::new();
        for v in [3,1,4,1,5,9,2,6] { sl.insert(v); }
        assert!(sl.search(5)); assert!(!sl.search(7));
    }
    #[test] fn delete() {
        let mut sl = SkipListSimulation::new();
        sl.insert(3); sl.insert(5); sl.insert(7);
        assert!(sl.delete(5)); assert!(!sl.search(5));
    }
    #[test] fn sorted_order() {
        let mut sl = SkipListSimulation::new();
        for v in [5,2,8,1,9,3] { sl.insert(v); }
        assert_eq!(sl.level0, vec![1,2,3,5,8,9]);
    }
}

(* OCaml: simplified skip list concept *)

(* We model skip list as sorted list with 'express lanes' *)
type 'a node = {
  value : 'a;
  next  : 'a node option array;  (* one per level *)
}

(* Simplified: just show the concept with a sorted list *)
let insert_sorted lst v =
  let rec go = function
    | [] -> [v]
    | x::xs -> if v <= x then v::x::xs else x :: go xs
  in go lst

let search lst v = List.exists ((=) v) lst

let () =
  let lst = List.fold_left insert_sorted [] [5;3;7;1;9;4;6;2;8] in
  Printf.printf "Sorted: [%s]\n" (String.concat ";" (List.map string_of_int lst));
  Printf.printf "Search 7: %b\n" (search lst 7);
  Printf.printf "Search 10: %b\n" (search lst 10)