Skip lists

Binary search halves an array at every step. Can a list skip ahead too? Stack sparser lists above it, and watch a search hop.

⋯36bool insert(struct skiplist *s, int key)37{38    struct snode *update[MAXLEVEL] = { NULL };39    struct snode *p = &s->head;40    for (int lv = s->level - 1; lv >= 0; lv--) {41        while (p->next[lv] != NULL && p->next[lv]->key < key)42            p = p->next[lv];43        update[lv] = p;44    }45    int h = random_height();46    for (int lv = s->level; lv < h; lv++)47        update[lv] = &s->head;48    if (h > s->level)49        s->level = h;⋯57    for (int lv = 0; lv < h; lv++) {58        n->next[lv] = update[lv]->next[lv];59        update[lv]->next[lv] = n;60    }61    return true;62}⋯64bool search(const struct skiplist *s, int key)65{66    const struct snode *p = &s->head;67    for (int lv = s->level - 1; lv >= 0; lv--) {68        while (p->next[lv] != NULL && p->next[lv]->key < key) {69            p = p->next[lv];70            moves++;71        }72    }73    p = p->next[0];74    return p != NULL && p->key == key;75}⋯79    struct skiplist s = { .level = 0 };80    for (int i = 1; i <= N; i++)81        if (!insert(&s, 10 * i))82            return 1;83    for (const struct snode *q = s.head.next[0]; q != NULL; q = q->next[0])84        printf("%d:%d ", q->key, q->height);85    printf("\nlevels %d\n", s.level);86    bool found = search(&s, 130);87    printf("130 found %d after %d moves\n", found, moves);88    struct snode *p = s.head.next[0];

Lists above a list

A sorted linked list can only be searched one node at a time: to reach the 13th key, a search follows 12 next pointers. Binary search skips half of a sorted array in one step, because it can jump to the middle. A list cannot jump. A skip list gives it somewhere to jump from.

Level 0 is the full sorted list. Level 1 is a second list, through about half of the nodes; level 2 goes through about half of those, and so on. A search starts on the top level, the sparsest, and runs along it while the next key is smaller than the one it wants. When the next key would be too big, or there is none, it drops a level and carries on from where it stands. The high levels are express lanes: they skip most of the list, and the lower ones finish the job.

Which nodes go up a level is decided by coin flips. Nothing is ever rebalanced.

The code and its cost

Nodes as towers

#define MAXLEVEL 8

struct snode {
    int key;
    int height;
    struct snode *next[MAXLEVEL];
};

struct skiplist {
    struct snode head;
    int level;
};

A node of height h is in the lists of levels 0 to h − 1: next[0] is its successor in the full list, next[1] its successor on level 1, and so on. Here every node has room for 8 pointers, the cap, even if it uses one: sizeof (struct snode) is 72 bytes. The list itself is a head node, which is on every level, and level, the number of levels in use. In main, the skip list s is a local; it starts as all zeros, so it has no levels and every head pointer is NULL.

A height from coin flips

static int coin(void)
{
    seed = seed * 1103515245u + 12345u;
    return (seed >> 16) & 1;
}

static int random_height(void)
{
    int h = 1;
    while (h < MAXLEVEL && coin())
        h++;
    return h;
}

coin is a small random number generator: each call works out the next number from the last and returns one of its bits, 1 for heads or 0 for tails. It starts from seed = 1, so every run of the program flips the same coins; Quicksort (17.6) uses the same line for its random pivots. A node’s height starts at 1 and grows by one for each head in a row, until the first tail or the cap of 8.

So half of all nodes stop at height 1, a quarter at 2, an eighth at 3. The chance that a node reaches height k or more is 1/2 multiplied by itself k − 1 times: 1/2 for 2, 1/4 for 3, 1/8 for 4. These are the rules of probability for independent flips.

This run gives the 16 keys, 10 to 160, the heights 1 1 5 2 1 3 1 6 1 1 4 3 1 1 2 1, and the list has 6 levels. Seven nodes reach level 1, five reach level 2, and only 80 reaches level 5.

Searching

bool search(const struct skiplist *s, int key)
{
    const struct snode *p = &s->head;
    for (int lv = s->level - 1; lv >= 0; lv--) {
        while (p->next[lv] != NULL && p->next[lv]->key < key) {
            p = p->next[lv];
            moves++;
        }
    }
    p = p->next[0];
    return p != NULL && p->key == key;
}

p starts on the head. On each level, from the top down, it moves right while the next key there is smaller than the key wanted, and then the level drops. When level 0 is done, p is on the last key smaller than the one wanted, and the key, if it is there at all, is the next one.

The search for 130 in the clip:

• Level 5: 80 is smaller, so p moves to 80. Then NULL: drop.
• Level 4: from 80, NULL: drop.
• Level 3: 110 is smaller: move. Then NULL: drop.
• Level 2: 120 is smaller: move. Then NULL: drop.
• Level 1: 150 is not smaller: drop.
• Level 0: 130 is not smaller: done. p’s next is 130, so the key is found.

That is 3 moves. On level 0 alone, the same loop would make 12, from the head to 120. The output is 130 found 1 after 3 moves.

The random heights make the time vary, never the answer. Whatever the coins say, every key is on level 0 in order, so a search always finds a key that is there and never finds one that is not. A different seed would change how many moves it takes.

Inserting

bool insert(struct skiplist *s, int key)
{
    struct snode *update[MAXLEVEL] = { NULL };
    struct snode *p = &s->head;
    for (int lv = s->level - 1; lv >= 0; lv--) {
        while (p->next[lv] != NULL && p->next[lv]->key < key)
            p = p->next[lv];
        update[lv] = p;
    }
    int h = random_height();
    for (int lv = s->level; lv < h; lv++)
        update[lv] = &s->head;
    if (h > s->level)
        s->level = h;
    …
    for (int lv = 0; lv < h; lv++) {
        n->next[lv] = update[lv]->next[lv];
        update[lv]->next[lv] = n;
    }
    return true;
}

An insertion searches first, and on each level it writes down where it dropped: update[lv] is the last node on level lv before the new key. Then it flips for the height. Levels the list does not have yet start at the head. Last, on each of its levels, the new node is linked in after update[lv], with the two writes of Singly linked lists: its own next first, then the one before it. The lines left out (…) allocate the node, set its key and height, and fill its eight next pointers with NULL.

Watch 30 in the clip. The list then holds 10 and 20, on one level. On level 0, 30 goes after 20. Four heads and a tail give it height 5, so the list grows to 5 levels and update holds the head on levels 1 to 4. Then 30 is linked on all five.

What it costs

The number of levels grows like log₂ n: each level holds about half of the one below, so after about log₂ n halvings few nodes are left. For 16 keys log₂ 16 is 4, but the tallest of 16 coin towers is expected to be a little over 5, so this run’s 6 is nothing unusual. On each level a search makes about one move on average before it drops, so a search takes about log₂ n moves, and an insertion the same plus its writes. These are averages over the coin flips, the expected value of the number of moves, not a promise for every run.

Keys inserted in sorted order, as here, do no harm: the heights come from the coins, not from the keys. A binary search tree fed sorted keys becomes a chain.

Memory: the average height is 2, so about 2n pointers are in use; this run uses 34 for its 16 nodes. This program reserves 8 per node, so every node takes 72 bytes, 80 with the C library’s spacing.

Running it yourself

The program is skip.c: the two structs, coin, random_height, insert, search and a main that inserts 10 to 160, prints each key with its height, searches for 130 and frees the nodes along level 0. Build and run it with:

gcc -std=c11 -Wall -Wextra -pedantic skip.c -o skip
./skip

It prints 10:1 20:1 30:5 40:2 50:1 60:3 70:1 80:6 90:1 100:1 110:4 120:3 130:1 140:1 150:2 160:1, then levels 6 and 130 found 1 after 3 moves.

Worked example

A search by hand. A skip list holds the keys 10 to 80 with heights 1 3 1 2 1 4 1 2, so it has 4 levels. Search for 50:

• Level 3: the only node is 60, which is too big: drop.
• Level 2: move to 20; next is 60, too big: drop.
• Level 1: move to 40; next is 60: drop.
• Level 0: next is 50, not smaller: done, and 50 is the next key. Found.

Two moves, against four on level 0 alone (10, 20, 30, 40). A search for 70 makes one: to 60 on level 3. From there it only drops: on level 2 the next is NULL, on level 1 it is 80, past 70, and on level 0 the next key is 70.

The chances for one node. Height at least 2: 1/2. At least 4: 1/8. At least 8, the cap: 1/128. Among 16 nodes, the expected number of height 3 or more is 16 × 1/4 = 4; this run has 5.

The memory. 16 nodes of 72 bytes, 80 apart on the heap. A version that allocates only height pointers for each node, with a flexible array member at the end of the struct (struct snode *next[];, its size chosen at malloc), needs on average 4 + 4 + 2 × 8 = 24 bytes per node.

Where it’s used

Databases. Some in-memory databases and key–value stores keep their ordered indexes as skip lists.

Sorted sets. A set that must answer “what comes next after this key?” or “everything between these two keys” can be a skip list: level 0 is already in order.

Concurrent maps. Several threads can update an ordered map built on a skip list at once more easily than a balanced tree, because an insertion changes only a few nearby pointers and nothing is rebalanced. Balanced trees such as AVL trees (13.3) do the same job with guaranteed, not average, costs.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.