Unlocking the Secrets of Skip Lists: Theory, Implementation, and Performance Analysis

1. Overview

Skip lists are probabilistic data structures that can replace balanced trees in many applications. They achieve the same expected time bounds as balanced trees while being simpler, faster, and using less space. This article gives a systematic introduction and formal analysis of skip lists.

2. Data Structure

Each element in a skip list is represented by a node. A node has a random level (independent of the total number of elements) and a set of forward pointers equal to its level. The head node has the maximum level (MaxLevel). The level of a node is never larger than MaxLevel, and an empty list has level 0.

<code>#define SKIP_LIST_KEY_TYPE int
#define SKIP_LIST_VALUE_TYPE int
#define SKIP_LIST_MAX_LEVEL 32
#define SKIP_LIST_P 0.5

struct Node {
    SKIP_LIST_KEY_TYPE key;
    SKIP_LIST_VALUE_TYPE value;
    struct Node *forwards[]; // flexible array of forward pointers
};

struct SkipList {
    struct Node *head;
    int level;
};
</code>

Node creation and list initialization allocate space for the maximum level and set all forward pointers to

NULL

.

<code>struct Node *CreateNode(int level) {
    struct Node *node;
    assert(level > 0);
    node = malloc(sizeof(struct Node) + sizeof(struct Node *) * level);
    return node;
}

struct SkipList *CreateSkipList(void) {
    struct SkipList *list = malloc(sizeof(struct SkipList));
    struct Node *head = CreateNode(SKIP_LIST_MAX_LEVEL);
    for (int i = 0; i < SKIP_LIST_MAX_LEVEL; i++) {
        head->forwards[i] = NULL;
    }
    list->head = head;
    list->level = 1;
    return list;
}
</code>

3. Algorithms

Search

The search starts from the highest level of the head node and moves forward while the next node’s key is less than the target. When no forward pointer can advance, the algorithm drops to the next lower level. The process stops when the target is found or the list ends.

<code>struct Node *SkipListSearch(struct SkipList *list, SKIP_LIST_KEY_TYPE target) {
    struct Node *current = list->head;
    for (int i = list->level - 1; i >= 0; i--) {
        while (current->forwards[i] && current->forwards[i]->key < target) {
            current = current->forwards[i];
        }
    }
    current = current->forwards[0];
    if (current && current->key == target) return current;
    return NULL;
}
</code>

Insertion and Deletion

Both operations reuse the search logic and maintain an

update

array that stores the last visited node at each level. Insertion may increase the list’s level if the new node’s random level is higher.

<code>struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) {
    struct Node *update[SKIP_LIST_MAX_LEVEL];
    struct Node *current = list->head;
    for (int i = list->level - 1; i >= 0; i--) {
        while (current->forwards[i] && current->forwards[i]->key < key) {
            current = current->forwards[i];
        }
        update[i] = current;
    }
    current = current->forwards[0];
    if (current && current->key == key) {
        current->value = value;
        return current;
    }
    int level = SkipListRandomLevel();
    if (level > list->level) {
        for (int i = list->level; i < level; i++) {
            update[i] = list->head;
        }
        list->level = level;
    }
    struct Node *newNode = CreateNode(level);
    newNode->key = key;
    newNode->value = value;
    for (int i = 0; i < level; i++) {
        newNode->forwards[i] = update[i]->forwards[i];
        update[i]->forwards[i] = newNode;
    }
    return newNode;
}

struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) {
    struct Node *update[SKIP_LIST_MAX_LEVEL];
    struct Node *current = list->head;
    for (int i = list->level - 1; i >= 0; i--) {
        while (current->forwards[i] && current->forwards[i]->key < key) {
            current = current->forwards[i];
        }
        update[i] = current;
    }
    current = current->forwards[0];
    if (!current || current->key != key) return NULL;
    for (int i = 0; i < list->level; i++) {
        if (update[i]->forwards[i] != current) break;
        update[i]->forwards[i] = current->forwards[i];
    }
    while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) {
        list->level--;
    }
    return current;
}
</code>

Random Level Generation

The level of a new node is generated by repeatedly flipping a biased coin with probability

SKIP_LIST_P

until the first failure or the maximum level is reached.

<code>int SkipListRandomLevel(void) {
    int level = 1;
    while (random() < RAND_MAX * SKIP_LIST_P && level < SKIP_LIST_MAX_LEVEL) {
        level++;
    }
    return level;
}
</code>

4. Choosing MaxLevel

For a list of

n

elements, the expected number of nodes at level

i

is

n * (SKIP_LIST_P)^{i-1}

. Setting

MaxLevel = ceil(log_{1/SKIP_LIST_P}(n))

guarantees that the highest level contains a constant number of nodes, which balances space and search cost.

5. Analysis

Space Complexity

The total number of forward pointers is the sum of a geometric series, yielding an expected space usage of

O(n)

because the probability

p

is a constant.

Time Complexity

Search, insertion, and deletion each traverse at most one node per level, giving an expected time of

O(log_{1/p} n)

. Since

p = 0.5

in most implementations, the expected time is

O(log n)

.

Formal Analysis

Using negative‑binomial distribution, the expected number of forward‑pointer traversals when climbing from level

i

to

i+1

is constant. Summing over all levels yields the same logarithmic bound for all operations.

6. Extensions – Fast Random Access

By augmenting each forward pointer with a

span

field that records the number of elements skipped, the skip list can support O(log n) random access and range queries. The extended node definition is:

<code>struct Forward {
    struct Node *forward;
    int span;
};

struct Node {
    SKIP_LIST_KEY_TYPE key;
    SKIP_LIST_VALUE_TYPE value;
    struct Forward forwards[]; // flexible array with span
};

struct SkipList {
    struct Node *head;
    int level;
    int length; // total number of elements
};
</code>

Insertion and deletion are modified to update the

span

values using an

indices

array that tracks the cumulative distance traversed at each level.

7. References

Pugh, W. (1989). A skip list cookbook. Tech. Rep. CS‑TR‑2286.1, Univ. of Maryland.

Pugh, W. (1989). Skip lists: A probabilistic alternative to balanced trees. Lecture Notes in Computer Science, 437–449.

Weiss, M. A. (1996). Data Structures and Algorithm Analysis in C (2nd ed.). Pearson.

Aragon, C., & Seidel, R. (1989). Randomized Search Trees.

Wikipedia contributors. (2022). Finger search.

Wikipedia contributors. (2022). Threaded binary tree.

Wikipedia contributors. (2023). Negative binomial distribution.

Redis contributors. Redis ordered set implementation.