974 Advanced

974 Skip List

Functional Programming

Tutorial

The Problem

Implement a skip list — a probabilistic sorted data structure providing O(log n) average search, insert, and delete. Use an arena-based approach: nodes are stored in a Vec and referenced by index instead of raw pointers. Each node has a forward: Vec<usize> of index references to nodes at each level. Use a deterministic xorshift PRNG for reproducible tests.

🎯 Learning Outcomes

• Implement an arena allocator pattern: Vec<SkipListNode> where node 0 is the header sentinel

• Implement random_level() using a geometric distribution: keep incrementing level while PRNG output < P=0.5, up to MAX_LEVEL

• Implement search(value) -> bool by descending from max level and advancing forward[level] while value is too small

• Implement insert(value) using the same top-down search with an update array tracking the predecessor at each level

• Understand why index-based arenas avoid raw pointer unsafety in Rust while still achieving O(log n) operations

Code Example

#![allow(clippy::all)]
// 974: Skip List (Simplified)
// Probabilistic sorted structure: O(log n) average search/insert
// Uses raw indices instead of pointers (safer than raw pointers in Rust)

use std::collections::VecDeque;

const MAX_LEVEL: usize = 8;
const P: f64 = 0.5;

// Simple deterministic PRNG for reproducible tests (xorshift)
struct Rng(u64);
impl Rng {
    fn new(seed: u64) -> Self {
        Rng(seed)
    }
    fn next_f64(&mut self) -> f64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        (self.0 & 0xFFFF) as f64 / 0x10000 as f64
    }
    fn random_level(&mut self) -> usize {
        let mut level = 1;
        while level < MAX_LEVEL && self.next_f64() < P {
            level += 1;
        }
        level
    }
}

// Arena-based skip list: nodes stored in Vec, referenced by index
// 0 = header sentinel
struct SkipListNode {
    value: i64,
    forward: Vec<usize>, // indices into node arena; 0 = None (header is sentinel)
}

pub struct SkipList {
    nodes: Vec<SkipListNode>,
    level: usize,
    rng: Rng,
}

impl SkipList {
    pub fn new() -> Self {
        let header = SkipListNode {
            value: i64::MIN,
            forward: vec![0; MAX_LEVEL], // 0 = nil (self-loop = nil for header)
        };
        SkipList {
            nodes: vec![header],
            level: 0,
            rng: Rng::new(12345),
        }
    }

    fn is_nil(&self, idx: usize) -> bool {
        idx == 0 && self.nodes[0].forward[0] == 0 || (idx == 0 && self.level == 0)
    }

    pub fn search(&self, target: i64) -> bool {
        let mut current = 0usize; // start at header
        for i in (0..self.level).rev() {
            loop {
                let next = self.nodes[current].forward[i];
                if next == 0 {
                    break;
                }
                if self.nodes[next].value < target {
                    current = next;
                } else {
                    break;
                }
            }
        }
        let next = self.nodes[current].forward[0];
        next != 0 && self.nodes[next].value == target
    }

    pub fn insert(&mut self, value: i64) {
        let mut update = vec![0usize; MAX_LEVEL];
        let mut current = 0usize;

        for i in (0..self.level).rev() {
            loop {
                let next = self.nodes[current].forward[i];
                if next == 0 || self.nodes[next].value >= value {
                    break;
                }
                current = next;
            }
            update[i] = current;
        }

        let new_level = self.rng.random_level();
        if new_level > self.level {
            for i in self.level..new_level {
                update[i] = 0; // header
            }
            self.level = new_level;
        }

        let new_idx = self.nodes.len();
        let mut new_node = SkipListNode {
            value,
            forward: vec![0; new_level],
        };

        for i in 0..new_level {
            new_node.forward[i] = self.nodes[update[i]].forward[i];
            self.nodes[update[i]].forward[i] = new_idx;
        }
        self.nodes.push(new_node);
    }

    pub fn to_vec(&self) -> Vec<i64> {
        let mut result = vec![];
        let mut current = self.nodes[0].forward[0];
        while current != 0 {
            result.push(self.nodes[current].value);
            current = self.nodes[current].forward[0];
        }
        result
    }
}

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

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

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

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

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

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert_eq!(sl.to_vec(), Vec::<i64>::new());
        assert!(!sl.search(1));
    }

    #[test]
    fn test_single() {
        let mut sl = SkipList::new();
        sl.insert(42);
        assert_eq!(sl.to_vec(), vec![42]);
        assert!(sl.search(42));
        assert!(!sl.search(43));
    }
}

(* 974: Skip List (Simplified) *)
(* Probabilistic sorted structure. O(log n) average search/insert *)
(* Simplified: fixed max levels, random promotion *)

let max_level = 8
let p = 0.5  (* probability of promoting to next level *)

(* Random level generator *)
let random_level () =
  let level = ref 1 in
  while !level < max_level && Random.float 1.0 < p do
    incr level
  done;
  !level

type 'a node = {
  value: 'a;
  mutable forward: 'a node option array;  (* forward pointers per level *)
}

type 'a skip_list = {
  header: 'a node;  (* sentinel head node *)
  mutable level: int;
}

let create_node value level =
  { value; forward = Array.make level None }

let create () =
  let header = { value = Obj.magic (); forward = Array.make max_level None } in
  { header; level = 0 }

let search sl target =
  let current = ref sl.header in
  for i = sl.level - 1 downto 0 do
    let continue_ = ref true in
    while !continue_ do
      match !current.forward.(i) with
      | Some next when next.value < target ->
        current := next
      | _ -> continue_ := false
    done
  done;
  match !current.forward.(0) with
  | Some node when node.value = target -> true
  | _ -> false

let insert sl value =
  let update = Array.make max_level sl.header in
  let current = ref sl.header in
  for i = sl.level - 1 downto 0 do
    let continue_ = ref true in
    while !continue_ do
      match !current.forward.(i) with
      | Some next when next.value < value ->
        current := next
      | _ -> continue_ := false
    done;
    update.(i) <- !current
  done;
  let new_level = random_level () in
  if new_level > sl.level then begin
    for i = sl.level to new_level - 1 do
      update.(i) <- sl.header
    done;
    sl.level <- new_level
  end;
  let new_node = create_node value new_level in
  for i = 0 to new_level - 1 do
    new_node.forward.(i) <- update.(i).forward.(i);
    update.(i).forward.(i) <- Some new_node
  done

let to_list sl =
  let result = ref [] in
  let current = ref sl.header.forward.(0) in
  while !current <> None do
    let node = Option.get !current in
    result := node.value :: !result;
    current := node.forward.(0)
  done;
  List.rev !result

let () =
  Random.self_init ();
  let sl = create () in

  List.iter (insert sl) [5; 3; 7; 1; 9; 4; 6; 2; 8];

  let lst = to_list sl in
  assert (lst = [1;2;3;4;5;6;7;8;9]);

  assert (search sl 5);
  assert (search sl 1);
  assert (search sl 9);
  assert (not (search sl 0));
  assert (not (search sl 10));

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Arena	`Vec<SkipListNode>`	`DynArray.t` or `Array.t ref`
Null pointer	Index `0` (header sentinel)	Same convention
Raw pointers	Not needed — indices only	Not needed with arena
PRNG	Inline xorshift (deterministic)	`Random.float` (stdlib)
Level randomization	Geometric distribution, P=0.5	Same

Skip lists provide similar O(log n) average performance to balanced BSTs but are simpler to implement. They are used in Redis (sorted sets), LevelDB, and various in-memory databases.

OCaml Approach

type node = {
  value: int;
  mutable forward: int array;  (* indices into node array *)
}

type t = {
  nodes: node DynArray.t;  (* resizable array *)
  mutable level: int;
  rng: unit -> float;
}

let search sl v =
  let current = ref 0 in
  for lvl = sl.level - 1 downto 0 do
    while (DynArray.get sl.nodes (DynArray.get sl.nodes !current).forward.(lvl)).value < v do
      current := (DynArray.get sl.nodes !current).forward.(lvl)
    done
  done;
  let next = (DynArray.get sl.nodes !current).forward.(0) in
  next <> 0 && (DynArray.get sl.nodes next).value = v

OCaml's approach is structurally identical — arena-based with mutable forward arrays. The key difference is that OCaml uses DynArray (Batteries) or Array.t ref for the arena, while Rust uses a Vec.

Full Source

#![allow(clippy::all)]
// 974: Skip List (Simplified)
// Probabilistic sorted structure: O(log n) average search/insert
// Uses raw indices instead of pointers (safer than raw pointers in Rust)

use std::collections::VecDeque;

const MAX_LEVEL: usize = 8;
const P: f64 = 0.5;

// Simple deterministic PRNG for reproducible tests (xorshift)
struct Rng(u64);
impl Rng {
    fn new(seed: u64) -> Self {
        Rng(seed)
    }
    fn next_f64(&mut self) -> f64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        (self.0 & 0xFFFF) as f64 / 0x10000 as f64
    }
    fn random_level(&mut self) -> usize {
        let mut level = 1;
        while level < MAX_LEVEL && self.next_f64() < P {
            level += 1;
        }
        level
    }
}

// Arena-based skip list: nodes stored in Vec, referenced by index
// 0 = header sentinel
struct SkipListNode {
    value: i64,
    forward: Vec<usize>, // indices into node arena; 0 = None (header is sentinel)
}

pub struct SkipList {
    nodes: Vec<SkipListNode>,
    level: usize,
    rng: Rng,
}

impl SkipList {
    pub fn new() -> Self {
        let header = SkipListNode {
            value: i64::MIN,
            forward: vec![0; MAX_LEVEL], // 0 = nil (self-loop = nil for header)
        };
        SkipList {
            nodes: vec![header],
            level: 0,
            rng: Rng::new(12345),
        }
    }

    fn is_nil(&self, idx: usize) -> bool {
        idx == 0 && self.nodes[0].forward[0] == 0 || (idx == 0 && self.level == 0)
    }

    pub fn search(&self, target: i64) -> bool {
        let mut current = 0usize; // start at header
        for i in (0..self.level).rev() {
            loop {
                let next = self.nodes[current].forward[i];
                if next == 0 {
                    break;
                }
                if self.nodes[next].value < target {
                    current = next;
                } else {
                    break;
                }
            }
        }
        let next = self.nodes[current].forward[0];
        next != 0 && self.nodes[next].value == target
    }

    pub fn insert(&mut self, value: i64) {
        let mut update = vec![0usize; MAX_LEVEL];
        let mut current = 0usize;

        for i in (0..self.level).rev() {
            loop {
                let next = self.nodes[current].forward[i];
                if next == 0 || self.nodes[next].value >= value {
                    break;
                }
                current = next;
            }
            update[i] = current;
        }

        let new_level = self.rng.random_level();
        if new_level > self.level {
            for i in self.level..new_level {
                update[i] = 0; // header
            }
            self.level = new_level;
        }

        let new_idx = self.nodes.len();
        let mut new_node = SkipListNode {
            value,
            forward: vec![0; new_level],
        };

        for i in 0..new_level {
            new_node.forward[i] = self.nodes[update[i]].forward[i];
            self.nodes[update[i]].forward[i] = new_idx;
        }
        self.nodes.push(new_node);
    }

    pub fn to_vec(&self) -> Vec<i64> {
        let mut result = vec![];
        let mut current = self.nodes[0].forward[0];
        while current != 0 {
            result.push(self.nodes[current].value);
            current = self.nodes[current].forward[0];
        }
        result
    }
}

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

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

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

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

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

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert_eq!(sl.to_vec(), Vec::<i64>::new());
        assert!(!sl.search(1));
    }

    #[test]
    fn test_single() {
        let mut sl = SkipList::new();
        sl.insert(42);
        assert_eq!(sl.to_vec(), vec![42]);
        assert!(sl.search(42));
        assert!(!sl.search(43));
    }
}

(* 974: Skip List (Simplified) *)
(* Probabilistic sorted structure. O(log n) average search/insert *)
(* Simplified: fixed max levels, random promotion *)

let max_level = 8
let p = 0.5  (* probability of promoting to next level *)

(* Random level generator *)
let random_level () =
  let level = ref 1 in
  while !level < max_level && Random.float 1.0 < p do
    incr level
  done;
  !level

type 'a node = {
  value: 'a;
  mutable forward: 'a node option array;  (* forward pointers per level *)
}

type 'a skip_list = {
  header: 'a node;  (* sentinel head node *)
  mutable level: int;
}

let create_node value level =
  { value; forward = Array.make level None }

let create () =
  let header = { value = Obj.magic (); forward = Array.make max_level None } in
  { header; level = 0 }

let search sl target =
  let current = ref sl.header in
  for i = sl.level - 1 downto 0 do
    let continue_ = ref true in
    while !continue_ do
      match !current.forward.(i) with
      | Some next when next.value < target ->
        current := next
      | _ -> continue_ := false
    done
  done;
  match !current.forward.(0) with
  | Some node when node.value = target -> true
  | _ -> false

let insert sl value =
  let update = Array.make max_level sl.header in
  let current = ref sl.header in
  for i = sl.level - 1 downto 0 do
    let continue_ = ref true in
    while !continue_ do
      match !current.forward.(i) with
      | Some next when next.value < value ->
        current := next
      | _ -> continue_ := false
    done;
    update.(i) <- !current
  done;
  let new_level = random_level () in
  if new_level > sl.level then begin
    for i = sl.level to new_level - 1 do
      update.(i) <- sl.header
    done;
    sl.level <- new_level
  end;
  let new_node = create_node value new_level in
  for i = 0 to new_level - 1 do
    new_node.forward.(i) <- update.(i).forward.(i);
    update.(i).forward.(i) <- Some new_node
  done

let to_list sl =
  let result = ref [] in
  let current = ref sl.header.forward.(0) in
  while !current <> None do
    let node = Option.get !current in
    result := node.value :: !result;
    current := node.forward.(0)
  done;
  List.rev !result

let () =
  Random.self_init ();
  let sl = create () in

  List.iter (insert sl) [5; 3; 7; 1; 9; 4; 6; 2; 8];

  let lst = to_list sl in
  assert (lst = [1;2;3;4;5;6;7;8;9]);

  assert (search sl 5);
  assert (search sl 1);
  assert (search sl 9);
  assert (not (search sl 0));
  assert (not (search sl 10));

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

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

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

    #[test]
    fn test_empty() {
        let sl = SkipList::new();
        assert_eq!(sl.to_vec(), Vec::<i64>::new());
        assert!(!sl.search(1));
    }

    #[test]
    fn test_single() {
        let mut sl = SkipList::new();
        sl.insert(42);
        assert_eq!(sl.to_vec(), vec![42]);
        assert!(sl.search(42));
        assert!(!sl.search(43));
    }
}

Deep Comparison

Skip List — Comparison

Core Insight

A skip list is a sorted linked list with multiple levels of "skip" pointers. Inserting at a random height (O(log n) average) gives probabilistic O(log n) search. OCaml naturally models pointers as 'a node option (nullable reference); Rust avoids unsafe raw pointers by using an arena (Vec<Node>) and integer indices — safe, cache-friendly, and avoids lifetime complexity.

OCaml Approach

• mutable forward: 'a node option array — array of optional node pointers per level

• Obj.magic () for uninitiated header value (unsafe but practical)

• Mutable ref cells for traversal: let current = ref sl.header

• while !continue_ do ... done pattern for conditional loops

• Random.float 1.0 for probabilistic level generation

• Direct mutation: update.(i).forward.(i) <- Some new_node

Rust Approach

• Arena Vec<SkipListNode> with usize index references (no raw pointers)

• Index 0 = header sentinel (always exists); forward[i] == 0 means nil

• Custom Rng (xorshift) for deterministic testing

• for i in (0..self.level).rev() — iterate levels top to bottom

• self.nodes[idx] for node access by index

• No unsafe code needed — arena pattern solves the "many mutable pointers" problem

Comparison Table

Aspect	OCaml	Rust
Node pointers	`'a node option`	`usize` index into arena
Null/nil	`None`	Index `0` (header)
Arena	n/a (GC heap)	`Vec<SkipListNode>`
Mutation	`mutable` fields	`&mut self`
Traversal ptr	`let current = ref header`	`let mut current = 0usize`
RNG	`Random.float 1.0`	Custom xorshift Rng
Unsafe	`Obj.magic` for init	None required
Nil forward	`None` check	`next == 0` check

Exercises

Implement delete(value) -> bool using the same update array as insert.

Implement range_query(l, r) -> Vec<i64> that returns all values in [l, r] in sorted order.

Implement rank(value) -> Option<usize> that returns the position of value in sorted order.

Make the skip list generic: SkipList<T: Ord> rather than SkipList with i64.

Benchmark skip list vs BTreeSet for 100,000 random insertions and lookups.

Open Source Repos

functional-rust

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

Rust