Module concurrent_skip_list

A safe, concurrent, reference-counted skip list

About

Skip list are sorted, probabalistic, list-based structures that provide O(log(n)) (expected) time complexity for search, insert, and removal operations. This provides a significant advantage over sorted array-based lists, which exhibit worst-case O(n) removal (average O(n/2)) temporal performance. Introduced in 1989 by William Pugh, skip lists also tend to be simpler to implement than self-balancing tree structures and generally provide an easier and finer-grained control when adapting these structures for concurrent operations.

This structure provides a basic list implementation used to back this library’s [SkipListMap<K, V>] implementation.

Design

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

[None, a, j, c, e, d, b, i, g, h, f, None] [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] [None, a, b, c, d, e, f, g, h, i, j, None]

// Towers forming sorted “express lanes”

S3: None ----------> [ 6 ] -------------------------------------------------------> [ 7 ] ----------> None
S2: None ----------> [ 6 ] -------------------------------------> [ 8 ] ----------> [ 7 ] ----------> None
S1: None ----------> [ 6 ] ----------> [ 5 ] -------------------> [ 8 ] ----------> [ 7 ] -> [ 2 ] -> None

//Unsorted backing structure

S0: None -> [ a ] -> [ j ] -> [ c ] -> [ e ] -> [ d ] -> [ b ] -> [ i ] -> [ g ] -> [ h ] -> [ f ] -> 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

Structs

ConcurrentSkipList