Module skip_list

A naive attempt at implementing a skip list

About

The idea of a skip list is to implement sorted structures with expected O(log(n)) time complexity for search, insert, and removal operations. This provides a significant advantage over sorted array-based lists, which have worst-case O(n) removal (average O(n/2)) temporal performance. Skip lists are also simpler than self-balancing tree structures and provide an easier and finer-grained control when adapting these structures for concurrent operations. There is a reason Java’s concurrentSkipListMap is so popular.

This structure specifically implements the [SkipListMap<K, V>] structure which provides a map implementation, as the name suggests. See the [SkipListSet] module for a set implementation.

Design

At it’s root is the logic behind the doubly-linked list which squarely places this list into “advanced Rust” territory. Later, when we implement concurrency, this will propel the skip list map to “expert Rust” territory.

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 list does not rebuild any towers (besides the head node) at insert, but simply changes the maximum potential height for those towers to grow. 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: None -> 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: None ---------> None
S0: None -> [ 5] -> None

Each subsequent addition may add more tower levels up to log(n) where n is the number of elements in the list. This example illustrates a fully built skip list:

S3: None ---------> [*2] ---------------------------------------------> [*9] ----------> None
S2: None ---------> [*2] ------------------------------> [*7] --------> [*9] ----------> None
S1: None ---------> [*2] --------> [*4] ---------------> [*7] --------> [*9] -> [*10] -> None
S0: None -> [ 1] -> [ 2] -> [3] -> [ 4] -> [5] -> [6] -> [ 7] -> [8] -> [ 9] -> [ 10] -> None

For example, at level 2 you could traverse the list as pointers to [2, 7, 9]. The distinction here is that all of the node data is stored in one location, with only pointers being duplicated and populating tower lists.

Example code

Structs

SkipList