Module indexed_skip_list

A safe, indexed skip list

About

Skip lists are sorted, probabalistic structures made up of stacked lists of varying length to allow for truncated O(log(n)) navigation. Canonically linked lists are built from doubly-linked lists, but this is not a defining characteristic of the ADT. Regardless of the base list representation used, the navigational algorithm results in what is essentially a logical linked list.

Properly implemented skip lists provide O(log(n)) expected time complexity for search, insert, and removal operations. This provides a significant advantage over keeping sorted array- or link-based list invariants, which have worst-case O(n) removal (average O(n/2)) temporal performance. Skip lists are also simpler than self-balancing tree structures, which are commonly used for sorted list and map structures. Skip lists also generally provide easier and finer-grained control when adapted for concurrent operations. There is a reason Java’s concurrentSkipListMap is so popular.

Design

This design uses Vec-backed storage for [SkipNode]s that contain a list (tower) of “next” values, and a single “previous” value that represent indexes within the backing vector.

The list features a dynamic max height h that is logarithmically proportional to the number of elements in the list n such that h = log(n) in the expected case. The logarithmic growth ensures that the average search, insertion, and deletion operations remain efficient, typically with expected O(log(n)) time complexity.

The Search Algorithm

The point of the search algorithm is to find the first node (or handle/position) p in skip list S that represents the largest comparable value <= to the search key k. This algorithm can be broken into two steps: Step 1) looplet candidate = p.peek(), if candidate >= k, return p, otherwise move to p.next(). Repeat until p.peek() >= k. Step 2) Drop down a level: If S.below(p) == 0 you’re at the lowest level and the search terminates.

Visual Examples

An initial, empty skip list with one level and no data:

S0: HEAD -> None

Inserting the first node triggers an automatic tower level, even if it ends up empty. This provides the algorithm with a starting point:

S1: HEAD ----------> None
S0: HEAD -> [ 5 ] -> None

After inserting ['a', 'c', 'e', 'd', 'b', 'i', 'g', 'h', 'f'], the list’s SkipNodes might contain the following towers. Notice that its always possible to tell the last item in the list because its tower is empty. This makes sense, because inserting the last element can only point to None. As you can see by the index notation on the left-hand side of the table, the backing structure retains the insertion order; the backing structure remains unsorted.

HEAD[0]: [1, 2, 9, 7]
a[1]: [5]
c[2]: [4, 4]
e[3]: [9]
d[4]: [3, 9]
b[5]: [2]
i[6]: []
g[7]: [8, 6, 6]
h[8]: [6]
f[9]: [7, 7, 7]

The towers appear to contain rather nonsensical values when printed as they exist in memory, which represents insertion order. However, if you follow the indexes from the HEAD node, and re-arrange the nodes into lexicographically sorted order, which is what the navigational algorithms in the skiplist achieve, you’d get the following towers.

HEAD[0]: [1, 2, 9, 7]
a[1]: [5]
b[5]: [2]
c[2]: [4, 4]
d[4]: [3, 9]
e[3]: [9]
f[9]: [7, 7, 7]
h[8]: [6]
i[6]: []
g[7]: [8, 6, 6]

When you rotate the mapping 90 degrees you can start to visualize the skip list layers as logically linked lists formed by tower index placement. Notice that the towers roughly mirror the raw tower output from the previous output.

L3: [ g[7] ] -> None
L2: [ f[9] ] -> [ g[7] ] -> [ i[6] ] -> None
L1: [ c[2] ] -> [ d[4] ] -> [ f[9] ] -> [ g[7] ] -> [ i[6] ] -> None
L0: [ a[1] ] -> [ b[5] ] -> [ c[2] ] -> [ d[4] ] -> [ e[3] ] -> [ f[9] ] -> [ g[7] ] -> [ h[8] ] -> [ i[6] ] -> None

Finally, if you extend each index reference to align with its sorted position within the list, a classical skip list diagram emerges.

L3: HEAD -------------------------------------------------------------------------> [ g[7] ] -------------------------> None
L2: HEAD -------------------------------------------------------------> [ f[9] ] -> [ g[7] ] -------------> [ i[6] ] -> None
L1: HEAD -------------------------> [ c[2] ] -> [ d[4] ] -------------> [ f[9] ] -> [ g[7] ] -------------> [ i[6] ] -> None
L0: HEAD -> [ a[1] ] -> [ b[5] ] -> [ c[2] ] -> [ d[4] ] -> [ e[3] ] -> [ f[9] ] -> [ g[7] ] -> [ h[8] ] -> [ i[6] ] -> None

Example code

    let mut list = SkipList::<char>::new();

    // Inserts 9 values into the skip list
    // with a consuming iterator, moving values
    // into the list
    let values = ['a', 'c', 'e', 'd', 'b', 'i', 'g', 'h', 'f'];
    for e in l1.into_iter() {
        list.insert(e)
    }

    // Illustrates that the list exists as a sorted invariant
    let sorted = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];
    for (i, e) in list.iter().enumerate() {
        assert_eq!(e, &sorted[i]);
    }

    // Illustrates the Kth function in a 0-indexed list
    assert_eq!(list.get_kth(6).unwrap(), &'g');

    // Query by range using Rust's RangeBounds semantics
    let val = ['c', 'd', 'e', 'f'];
    for (i, e) in list.range('c'..='f').enumerate() {
        assert_eq!(e, &val[i])
    }

Structs

Iter

RangeIter

SkipList