rs-skiplist

A real, dependency-free skip list implementing an ordered map in Rust: SkipList<K, V> with insert, get, remove, and ordered range iteration.

A skip list is a linked structure built from several "levels" of linked lists stacked on top of a normal sorted linked list. Higher levels contain progressively fewer nodes, chosen by an independent coin flip on every insert, so that walking a search from the top level down "skips" over large chunks of the list — giving expected O(log n) search, insert and remove without the rebalancing logic a balanced tree needs.

Skip lists aren't just a textbook curiosity — they're used in real production systems:

• Redis implements its sorted set type (ZSET) with a skip list, giving O(log n) insert/remove/rank lookups and fast ordered range scans by score.
• LevelDB and RocksDB use a skip list for their in-memory "memtable", the structure that buffers recent writes in sorted order before they're flushed to disk as an SSTable.

This crate has zero dependencies — everything, including the PRNG used for level generation, is implemented from scratch on top of the standard library.

Usage

use rs_skiplist::SkipList;

fn main() {
    let mut list = SkipList::new();

    list.insert(5, "five");
    list.insert(1, "one");
    list.insert(3, "three");
    list.insert(9, "nine");

    // Point lookups.
    assert_eq!(list.get(&3), Some(&"three"));
    assert_eq!(list.get(&42), None);

    // Overwriting a key returns the previous value, like BTreeMap::insert.
    assert_eq!(list.insert(3, "THREE"), Some("three"));

    // Ordered range iteration — supports the standard Rust range syntax.
    let in_range: Vec<_> = list.range(1..9).map(|(k, v)| (*k, *v)).collect();
    assert_eq!(in_range, vec![(1, "one"), (3, "THREE"), (5, "five")]);

    let all: Vec<_> = list.range(..).map(|(k, _)| *k).collect();
    assert_eq!(all, vec![1, 3, 5, 9]);

    // Removal.
    assert_eq!(list.remove(&1), Some("one"));
    assert_eq!(list.get(&1), None);
    assert_eq!(list.len(), 3);
}

Add it to a project from a local path or Git checkout (this crate is not published to crates.io):

[dependencies]
rs-skiplist = { git = "https://github.com/kasapdev/rs-skiplist" }

How it works

Multi-level structure. Conceptually, level 0 is an ordinary sorted singly linked list containing every key. Level 1 contains roughly half of those keys, level 2 roughly half of those, and so on up to a fixed MAX_LEVEL (16 in this implementation). A search starts at the highest active level from a head sentinel and walks forward, dropping down a level each time the next node's key would overshoot the target — this is what gives the expected O(log n) bound: at each level the search advances past roughly half of the remaining candidates before dropping down, the same halving behavior a balanced binary search gets from tree structure, but achieved here with plain forward pointers and no rotations.

Level generation via coin flips. Every new node's level is chosen independently at insert time by repeated coin flips: start at level 1, and for each "heads" result, promote the node one more level (capped at MAX_LEVEL). With a fair coin this produces P(level = k) = 2^-k — a geometric distribution where about half of nodes stay at level 1, a quarter reach level 2, an eighth reach level 3, and so on. This crate implements its own minimal PRNG for this (XorShiftRng, an xorshift64 generator with the classic 13/7/17 shift triple) rather than depending on the rand crate. It self-seeds from a mix of the current time (SystemTime), a 64-bit hash produced by the standard library's own OS-seeded RandomState hasher, and a monotonically increasing atomic counter — so two lists created back to back don't start from the same state (this is exercised directly by the rng_self_seeds_differently_across_instances test). This PRNG is explicitly not cryptographically secure; it only needs to be fast and well distributed enough to drive level selection.

Node representation: index-based arena, no unsafe. Rather than the classic pointer-based skip list (raw pointers threaded through heap-allocated nodes, which safe Rust ownership can't express directly for a multi-forward-pointer structure), this implementation stores every node in a single backing Vec<Slot<K, V>> and refers to nodes by usize index instead of by pointer. A node's per-level "forward pointer" is just Option<usize> — the index of the next node at that level, or None. Removal doesn't shift or deallocate anything: a removed node's slot is tombstoned (Slot::Free) and threaded onto an intrusive free list, and the next insert that needs a new slot pops from that free list before growing the Vec. This keeps the whole implementation in safe Rust with no unsafe blocks at all, at the cost of one extra layer of indirection (index lookups into the arena Vec instead of direct pointer dereferences) and holding onto slot capacity for the lifetime of the list rather than returning it to the allocator. For a data structure whose whole purpose is a multi-forward-pointer linked list, this trade was judged clearly worth it — the safe version is exactly as fast asymptotically and is not at any real risk of the aliasing/use-after-free bugs a raw-pointer version has to get right by hand.

Complexity. Point operations (get, insert, remove) are expected O(log n) — not worst-case, since an adversarial (or simply unlucky) sequence of coin flips could in principle produce a degenerate list where every node stops at level 1 (making every operation O(n), identical to a plain linked list). This is exponentially unlikely with a real random source and is the reason the level-distribution test below exists — to make sure the PRNG is actually well distributed rather than silently degenerate. range locates its starting point in expected O(log n) the same way get does, then yields each subsequent element in O(1) by following level-0 pointers, so a bounded range scan of k results out of n total costs expected O(log n + k).

Testing

Run the full suite with:

cargo test

Beyond ordinary unit tests, two tests specifically stress the probabilistic and comparative correctness properties that matter most for a data structure like this:

• cross_check_against_btreemap runs 8,000 randomized insert / get / remove operations (keys drawn from a deliberately small range of 400 possible values, so overwrites, duplicate removals and lookups/removals of nonexistent keys all occur constantly) against both a SkipList and a std::collections::BTreeMap used as a reference implementation, using the crate's own seeded SplitMix64 generator so the sequence is reproducible. Every single operation's return value is asserted equal between the two structures, len() is checked after every step, and at the end the full ascending key/value iteration order (range(..)) and a bounded range query are both asserted to match BTreeMap exactly.
• level_distribution_is_roughly_geometric inserts 20,000 keys and records the level assigned to each one, then checks the resulting histogram against generous tolerance bands around the expected geometric distribution (~50% at level 1, ~50% reaching level ≥2, a small fraction reaching level ≥4, and a near-zero fraction reaching the max level). The bounds are intentionally loose — this is a sanity check, not a strict statistical test — but they are tight enough to fail hard against a degenerate PRNG that always returns the same coin flip result (which would silently collapse the skip list into a plain O(n) linked list): an "always false" generator would put ~100% of nodes at level 1 and 0% at level ≥2, failing multiple assertions at once, and an "always true" generator would put ~100% of nodes at the max level, also failing. A companion test, rng_self_seeds_differently_across_instances, further checks that two independently constructed lists don't produce identical level sequences.
• range_explicit_cases hand-checks range against known inserted keys across every standard bound combination (.., a..b, a..=b, ..b, ..=b, a.., and an explicit (Excluded, Included) pair), plus empty-result cases (an out-of-bounds range and a zero-width range) and an empty list.

Scope and limitations

• No persistence. This is a purely in-memory structure; there is no serialization or on-disk format.
• Not thread-safe. SkipList implements neither internal locking nor any concurrent-access guarantees — exactly like std::collections::BTreeMap, it is meant to be owned and accessed from a single logical owner at a time (&mut self for mutation), not shared across threads without external synchronization.
• Not a strict worst-case guarantee. As explained above, O(log n) is an expected bound from the probabilistic level generation, not a worst-case guarantee the way a balanced tree provides.

License

MIT. See LICENSE.