You've likely spent a lot of time with linked lists and binary search trees. Linked lists are simple but slow for searching; balanced trees are fast but a nightmare to rebalance (I still have nightmares about Red-Black tree rotations). That's where the Skip List comes in. It gives you the $O(\log n)$ search time of a tree but uses a probabilistic approach that's much easier to code. Think of it like a linked list with "express lanes."

How do I represent a node that has a variable number of forward pointers?

In a standard linked list, your node has one next pointer. In a skip list, a node needs a different number of pointers depending on its "level." If a node is at level 3, it needs pointers to skip over nodes at levels 0, 1, and 2.

I usually handle this by using a pointer to an array of pointers. It keeps the struct clean and allows us to allocate exactly as much memory as the node needs for its specific height. Here is how I'd set that up:

typedef struct Node {
    int key;
    int value;
    int level; 
    struct Node **forward; // Array of pointers to next nodes at different levels
} Node;

Node* create_node(int key, int value, int level) {
    Node *n = malloc(sizeof(Node));
    n->key = key;
    n->value = value;
    n->level = level;
    // Allocate memory for the forward pointers based on the node's level
    n->forward = malloc(sizeof(Node*) * (level + 1));
    for (int i = 0; i <= level; i++) {
        n->forward[i] = NULL;
    }
    return n;
}

Notice I used level + 1. In my implementation, level 0 is the base list that contains every single element. If a node is "level 2," it exists on levels 0, 1, and 2.

What's the trick to searching through the levels efficiently?

The "magic" of the skip list is starting at the highest possible level and moving forward as much as you can. When you hit a node that is larger than your target (or NULL), you drop down exactly one level and repeat the process.

Imagine you're looking for a specific page in a book. You look at the chapter headings first (top level), then the section headings (middle level), and finally the individual paragraphs (bottom level). You never have to go backward.

Node* search(Node *header, int key) {
    Node *current = header;

    // Start from the highest level of the skip list and move down
    for (int i = header->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    // Move to level 0 to see if the next node is actually our target
    current = current->forward[0];

    if (current != NULL && current->key == key) {
        return current;
    }
    return NULL; // Not found
}

The while loop handles the "express" movement, and the for loop handles the "drop down" movement. It's surprisingly elegant once you see it in action.

How do I implement the random level generation without making the list too tall?

You can't just pick a random number between 0 and 100; that would destroy the logarithmic performance. You want a geometric distribution. Essentially, you flip a coin: if it's heads, you increase the level. You keep flipping until you hit tails or reach a predefined maximum height.

I typically use a probability of 0.5. This means 50% of nodes are level 0, 25% are level 1, 12.5% are level 2, and so on. This mimics the structure of a binary tree.

int random_level(int max_level) {
    int level = 0;
    // rand() / RAND_MAX gives a float between 0 and 1
    while ((float)rand() / RAND_MAX < 0.5 && level < max_level) {
        level++;
    }
    return level;
}

One tip: don't set max_level too high. For most applications, a max level of 16 or 32 is plenty. A list with $2^{16}$ elements will still be very efficient with a max level of 16.

📋 Practical Task

Implementing a Skip List-Based Key-Value Store for Game Settings

Your task is to implement the insert function for a Skip List that stores game settings (where the key is a setting ID and the value is the setting value).

The insert function is the hardest part of the skip list. You must:

1. Create an array called update[] to keep track of the nodes where you "dropped down" during the search. You'll need these to rewire the pointers.
2. Generate a random level for the new node.
3. If the new level is higher than the current list level, update the update[] array to point to the header for those new levels.
4. Splice the new node into the list by updating the forward pointers of the nodes stored in your update[] array.

Ensure you handle memory allocation for the new node and its pointer array correctly. Test your implementation by inserting five keys in random order and verifying that search can find them all in $O(\log n)$ time.