Rust-Skiplist

A skiplist is a way of storing elements in such a way that elements can be efficiently accessed, inserted and removed, all in \(O(\log(n))\) on average. Rust-SkipList is an implementation of skiplists inside Rust.

Conceptually, a skiplist resembles something like:

1
2
3
4
<head> ----------> [2] --------------------------------------------------> [9] ---------->
<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->

where we each node [x] has references to nodes further down the list, allowing the algorithm to effectively skip ahead.

When accessing elements, the algorithm begins with the head node on the first (top-most) level and moves as far right without exceeding the element desired. The algorithm then moves down a level and repeats the process until it finds the desired node.

The bottom-most level is simply a linked list (i.e. each link always goes to the next node in the list), and each level up, the links become progressively longer skipping more and more elements. The height of each node is determined randomly; typically with a geometric distribution with \(p = 0.5\). This way the number of nodes of height \(n\) is approximately twice the number of nodes of height \(n+1\) and provides a good trade-off between memory usage and speed.

In order to use this crate, just add the following to your project's Cargo.toml:

1
2
3
[dependencies]

skiplist = "*"

and the documentation can be accessed here.