372 Advanced

372: Skip List Pattern

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "372: Skip List Pattern" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Linked lists support O(1) insert/delete at a known position but O(n) search. Key difference from OCaml: | Aspect | Rust skip list simulation | OCaml `Set.Make` |

Tutorial

The Problem

Linked lists support O(1) insert/delete at a known position but O(n) search. Balanced BSTs (AVL, red-black) support O(log n) search with complex rotation logic. Skip lists (William Pugh, 1990) achieve O(log n) expected time for search, insert, and delete using a simpler probabilistic approach: multiple layers of linked lists where each layer skips over elements, creating "express lanes" for fast traversal. Redis's sorted sets, LevelDB's memtable, and HBase use skip lists as their core sorted data structure. This example demonstrates the concept with sorted vectors as simulated express lanes, illustrating the layered search principle.

🎯 Learning Outcomes

• Understand the skip list concept: multiple sorted layers, each a subset of the layer below

• Navigate by starting at the highest layer (largest steps) and moving down

• Use binary search within each level for efficient express-lane searching

• Recognize that real skip lists use probabilistic node promotion (each level has ~50% of elements from below)

• See why skip lists are preferred over balanced BSTs in concurrent settings (easier to make lock-free)

• Implement insert maintaining the sorted invariant across all levels

Code Example

#![allow(clippy::all)]
//! Skip List Pattern
//!
//! Probabilistic data structure with O(log n) search using express lanes.

/// Skip list simulation using sorted vectors at multiple levels
pub struct SkipList {
    level0: Vec<i32>,
    level1: Vec<i32>,
    level2: Vec<i32>,
}

impl SkipList {
    pub 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();
    }

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

    pub fn search(&self, val: i32) -> bool {
        // Use express lanes (top-down search)
        if self.level2.binary_search(&val).is_ok() {
            return true;
        }
        if self.level1.binary_search(&val).is_ok() {
            return true;
        }
        self.level0.binary_search(&val).is_ok()
    }

    pub 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
        }
    }

    pub fn len(&self) -> usize {
        self.level0.len()
    }

    pub fn is_empty(&self) -> bool {
        self.level0.is_empty()
    }

    pub fn to_vec(&self) -> Vec<i32> {
        self.level0.clone()
    }
}

impl Default for SkipList {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut sl = SkipList::new();
        for v in [3, 1, 4, 1, 5, 9, 2, 6] {
            sl.insert(v);
        }
        assert!(sl.search(5));
        assert!(sl.search(3));
        assert!(!sl.search(7));
    }

    #[test]
    fn test_delete() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(2);
        sl.insert(3);
        assert!(sl.delete(2));
        assert!(!sl.search(2));
        assert!(sl.search(1));
        assert!(sl.search(3));
    }

    #[test]
    fn test_sorted_order() {
        let mut sl = SkipList::new();
        for v in [5, 3, 7, 1, 9] {
            sl.insert(v);
        }
        assert_eq!(sl.to_vec(), vec![1, 3, 5, 7, 9]);
    }

    #[test]
    fn test_duplicates() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(1);
        sl.insert(1);
        assert_eq!(sl.len(), 1);
    }

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert!(sl.is_empty());
        assert!(!sl.search(1));
    }
}

(* 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)

Key Differences

Aspect	Rust skip list simulation	OCaml `Set.Make`
Underlying structure	Multiple sorted vectors (simulation)	AVL tree (real O(log n))
Concurrent safety	Real skip lists can be lock-free	`Set` operations require synchronization
Insert complexity	O(n) for this simulation (Vec insert)	O(log n)
Search complexity	O(log n) per level via binary search	O(log n)
Real implementation	`crossbeam-skiplist` crate	Not needed; `Set` suffices

OCaml Approach

OCaml's standard skip list equivalent is a balanced BST via Map.Make:

module IntSet = Set.Make(Int)

(* Real skip list in OCaml requires imperative refs for linked nodes *)
(* Functional approximation: sorted list with layer filtering *)
let level0 = ref []
let level1 () = List.filteri (fun i _ -> i mod 2 = 0) !level0
let level2 () = List.filteri (fun i _ -> i mod 4 = 0) !level0

let insert v =
  if not (List.mem v !level0) then
    level0 := List.sort compare (v :: !level0)

let search v = List.mem v (level2 ()) || List.mem v (level1 ()) || List.mem v !level0

In practice, OCaml uses Set.Make (AVL tree) for sorted sets — the skip list's main advantage (simpler concurrent implementations) doesn't apply in OCaml's GC-managed environment.

Full Source

#![allow(clippy::all)]
//! Skip List Pattern
//!
//! Probabilistic data structure with O(log n) search using express lanes.

/// Skip list simulation using sorted vectors at multiple levels
pub struct SkipList {
    level0: Vec<i32>,
    level1: Vec<i32>,
    level2: Vec<i32>,
}

impl SkipList {
    pub 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();
    }

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

    pub fn search(&self, val: i32) -> bool {
        // Use express lanes (top-down search)
        if self.level2.binary_search(&val).is_ok() {
            return true;
        }
        if self.level1.binary_search(&val).is_ok() {
            return true;
        }
        self.level0.binary_search(&val).is_ok()
    }

    pub 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
        }
    }

    pub fn len(&self) -> usize {
        self.level0.len()
    }

    pub fn is_empty(&self) -> bool {
        self.level0.is_empty()
    }

    pub fn to_vec(&self) -> Vec<i32> {
        self.level0.clone()
    }
}

impl Default for SkipList {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut sl = SkipList::new();
        for v in [3, 1, 4, 1, 5, 9, 2, 6] {
            sl.insert(v);
        }
        assert!(sl.search(5));
        assert!(sl.search(3));
        assert!(!sl.search(7));
    }

    #[test]
    fn test_delete() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(2);
        sl.insert(3);
        assert!(sl.delete(2));
        assert!(!sl.search(2));
        assert!(sl.search(1));
        assert!(sl.search(3));
    }

    #[test]
    fn test_sorted_order() {
        let mut sl = SkipList::new();
        for v in [5, 3, 7, 1, 9] {
            sl.insert(v);
        }
        assert_eq!(sl.to_vec(), vec![1, 3, 5, 7, 9]);
    }

    #[test]
    fn test_duplicates() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(1);
        sl.insert(1);
        assert_eq!(sl.len(), 1);
    }

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert!(sl.is_empty());
        assert!(!sl.search(1));
    }
}

(* 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)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_search() {
        let mut sl = SkipList::new();
        for v in [3, 1, 4, 1, 5, 9, 2, 6] {
            sl.insert(v);
        }
        assert!(sl.search(5));
        assert!(sl.search(3));
        assert!(!sl.search(7));
    }

    #[test]
    fn test_delete() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(2);
        sl.insert(3);
        assert!(sl.delete(2));
        assert!(!sl.search(2));
        assert!(sl.search(1));
        assert!(sl.search(3));
    }

    #[test]
    fn test_sorted_order() {
        let mut sl = SkipList::new();
        for v in [5, 3, 7, 1, 9] {
            sl.insert(v);
        }
        assert_eq!(sl.to_vec(), vec![1, 3, 5, 7, 9]);
    }

    #[test]
    fn test_duplicates() {
        let mut sl = SkipList::new();
        sl.insert(1);
        sl.insert(1);
        sl.insert(1);
        assert_eq!(sl.len(), 1);
    }

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert!(sl.is_empty());
        assert!(!sl.search(1));
    }
}

Deep Comparison

OCaml vs Rust: Skip List

Both can implement using linked structures or arrays.

Exercises

Probabilistic promotion: Implement a real skip list where inserted nodes are promoted to higher levels with 50% probability; use Vec<(i32, usize)> (value, height) for nodes linked via Vec<usize> index arrays.

Range query: Add range(lo, hi) -> Vec<i32> that returns all elements in [lo, hi]; use level2's binary search to find the start position, then linear scan through level0.

Delete: Implement remove(&mut self, val: i32) -> bool that removes the value from all levels where it appears, returning whether it was found.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust