Skip Lists: Fast Logarithmic Search via Probabilistic Forward Express Lanes

A standard singly linked list requires linear O(N) time to search, even if the elements are maintained in sorted order, because binary search cannot be performed without random memory access. Invented by William Pugh in 1989, the Skip List solves this limitation by overlaying a hierarchy of linked lists where higher levels act as 'express lanes' skipping over sequences of intermediate elements.

Unlike deterministic self-balancing binary search trees (such as AVL or Red-Black trees) that enforce complex rotational invariants, Skip Lists maintain balance probabilistically using randomized level generation. This makes them significantly simpler to implement and far more amenable to lock-free concurrent synchronization.

Layered Multi-Level Architecture

A Skip List consists of multiple linked list levels arranged from level 0 (bottom) up to level MaxLevel - 1:

Base Layer (Level 0): A standard sorted linked list containing every single element inserted into the data structure.
Express Layers (Level 1 to L): Subsets of the elements below them. Each node is promoted to the next higher level with a fixed probability p (typically p = 0.5 or 0.25).
Head Sentinel: A multi-level node storing an array of forward pointers spanning across all active heights in the structure.
Expected Height: The overall height of a Skip List with N elements is bounded by O(log_{1/p} N), requiring an average of only 1 / (1 - p) pointers per element (1.33 to 2 pointers per node).

Core Operations and Complexity Analysis

1. Search Operation

Start at the highest active level of the head sentinel. Move forward horizontally as long as the next key is strictly less than the target value. When the next key is greater than or equal to the target, step down one level vertically and resume the horizontal traversal. Repeat until reaching Level 0. Expected Time Complexity: O(log N).

2. Insertion & Randomized Tower Building

To insert a new key:

Traverse the list while maintaining an `update[]` array that records the rightmost node visited at each level.
Determine the new node's height by repeatedly simulating a coin flip (while random() < p, increment height).
Splice the new node into the list at each level up to its assigned height by adjusting the forward pointers recorded in the `update[]` array.

Expected Time Complexity: O(log N). No global tree rebalancing or rotations are required.

3. Deletion

Locate the target key using the search path while filling the `update[]` tracking array. At every level where the target node exists, rewire the preceding node's forward pointer to skip over the target. Finally, free the node's memory and shrink the active list height if top levels become empty. Expected Time Complexity: O(log N).

Skip List vs. Red-Black Tree: Practical Trade-offs

Implementation Simplicity: Skip Lists require no complex rotation state machines or double-black deletion handling.
Concurrent Performance: Modifying a balanced tree often locks the root or wide subtrees during rotations. In contrast, Skip List updates only modify localized forward pointers, enabling fine-grained lock striping and lock-free implementations using atomic compare-and-swap (CAS) primitives.
Sequential Range Traversal: Once the starting key is located in O(log N), traversing a range is a flat linear linked-list traversal on Level 0.
Memory Footprint: Red-Black trees require 2 child pointers + 1 color bit per node; Skip Lists with p = 0.5 average 2 forward pointers per node, yielding comparable space overhead.

C++ Implementation Blueprint

#include <vector>
#include <cstdlib>

struct SkipNode {
    int key;
    std::vector<SkipNode*> forward;
    SkipNode(int k, int level) : key(k), forward(level, nullptr) {}
};

class SkipList {
private:
    static constexpr int MAX_LEVEL = 16;
    static constexpr float P = 0.5f;
    int level;
    SkipNode* head;

    int randomLevel() {
        int lvl = 1;
        while ((static_cast<float>(std::rand()) / RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

public:
    SkipList() : level(1) {
        head = new SkipNode(-1, MAX_LEVEL);
    }

    bool search(int target) {
        SkipNode* curr = head;
        for (int i = level - 1; i >= 0; --i) {
            while (curr->forward[i] && curr->forward[i]->key < target) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        return (curr && curr->key == target);
    }

    void insert(int key) {
        std::vector<SkipNode*> update(MAX_LEVEL, nullptr);
        SkipNode* curr = head;

        for (int i = level - 1; i >= 0; --i) {
            while (curr->forward[i] && curr->forward[i]->key < key) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];

        if (!curr || curr->key != key) {
            int new_level = randomLevel();
            if (new_level > level) {
                for (int i = level; i < new_level; ++i) update[i] = head;
                level = new_level;
            }
            SkipNode* new_node = new SkipNode(key, new_level);
            for (int i = 0; i < new_level; ++i) {
                new_node->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = new_node;
            }
        }
    }
};

Real-World Systems Applications

Redis Sorted Sets (ZSET): Redis implements sorted sets using a combination of a hash table (for O(1) score lookups) and a custom Skip List (to support high-throughput rank and range operations like ZRANGEBYSCORE).
LSM Storage Engine MemTables (RocksDB, LevelDB): In-memory write buffers utilize lock-free concurrent Skip Lists to handle millions of simultaneous key-value writes and sorted flushes without thread contention.
Apache Lucene / Search Inverted Indexes: Fast term-skipping across multi-million-document posting lists during Boolean conjunction queries (AND/OR).
Distributed Memory Stores (Apache Ignite, Hazelcast): Maintaining sorted concurrent partition indices across multi-core compute nodes.