⏭️ Skip List
Probabilistic sorted data structure with O(log n) expected-time operations
Overview
A randomized data structure that provides O(log n) expected-time search, insert, and delete in a sorted sequence. Elements are promoted to higher "express lane" levels with probability 1/2, creating a hierarchy that enables binary-search-like traversal without requiring strict balancing.
Concepts Demonstrated
- Probabilistic algorithms — randomized level promotion
- Multi-level indexing — express lanes for fast traversal
- Imperative nodes — mutable forward pointers for authentic behavior
- Comparison functions — custom ordering via
~compare - Range queries — efficient extraction of sorted sub-ranges
Key Functions
| Function | Description |
|---|---|
create | Create empty skip list with optional comparator |
insert | Add an element |
mem | Test membership |
find | Look up an element |
remove | Delete an element |
range_query | All elements in [lo, hi] range |
floor / ceil | Nearest element ≤ or ≥ a value |
min_elt / max_elt | Smallest/largest element |
Structure
(* Level 3: H ──────────────────→ 6 ──────→ nil
Level 2: H ────→ 3 ──────→ 6 ──→ 9 → nil
Level 1: H → 1 → 3 → 4 → 6 → 7 → 9 → nil *)
(* Each node has forward pointers at multiple levels *)
(* Higher levels skip more elements — like express lanes *)
(* Search starts at top level, drops down on overshoot *)Why Skip Lists?
Skip lists provide the same O(log n) performance as balanced trees (AVL, red-black) but with simpler implementation and no complex rotation logic. The trade-off: performance is expected rather than worst-case guaranteed, depending on random coin flips. In practice, they work beautifully — Redis uses skip lists for sorted sets.