Lesson 1 · Advanced structures and algorithms

Skip Lists

A standard linked list requires O(N) time to search because you must visit every node in order. A skip list solves this by adding multiple layers of 'express' pointers that skip over intermediate nodes, providing performance comparable to a balanced binary search tree.

The Express Lane Concept

Imagine a linked list representing subway stations. If you want to travel from station 1 to 100, stopping at every local station takes a long time. But if there is an 'express' train that stops only at stations 1, 20, 40, etc., you can skip most stops.

A skip list implements this by maintaining multiple hierarchical layers of linked lists. The bottom layer contains all elements. Higher layers contain fewer elements, acting as express lanes.

Layers are built hierarchically
Bottom layer is a standard sorted linked list
Searching starts at the highest layer and drops down

Searching a Skip List

To find a value, you start at the top-left (the highest layer's head). You move right as long as the next node's value is less than or equal to your target.

If the next node is greater than your target (or null), you drop down to the next layer and continue moving right. This rapidly narrows down the search space, achieving O(log N) time on average.

Start at top layer
Move right until next > target
Drop down a layer and repeat

Key reference

Terms, operations, and practical uses

Structure and layers

Express LanesHigher layers in the skip list that contain fewer nodes, allowing traversal to skip over large sections of the bottom layer.
Bottom LayerThe foundational layer (Layer 0) which is a standard sorted linked list containing every single inserted element.
TowerThe vertical column of nodes representing a single element across multiple layers.

Algorithms

Probabilistic BalancingFlipping a virtual coin to decide if a newly inserted node should be promoted to the next higher layer.
Drop DownThe action of moving to a lower layer during a search when the next node in the current layer is greater than the target.
Update ArrayAn array used during insertion to remember the right-most nodes visited at each layer so the new node can be spliced in correctly.

Comparisons and uses

O(log N) ExpectedSkip lists guarantee O(log N) time mathematically on average, but could theoretically degrade to O(N) if the coin flips are extremely unlucky.
ConcurrencySkip lists are easier to make thread-safe than balanced trees because updates are highly localized and don't require global rotations.
Redis Sorted SetsThe most famous real-world implementation of a skip list, used to rank elements quickly by score.

Code example

Searching in a Skip List

class SkipNode:
    def __init__(self, value, levels):
        self.value = value
        self.next = [None] * levels

def search_skip_list(head, target):
    current = head
    for level in range(len(head.next) - 1, -1, -1):
        while current.next[level] and current.next[level].value < target:
            current = current.next[level]
    candidate = current.next[0]
    return candidate is not None and candidate.value == target
# three layers; the express lanes skip over 50
head = SkipNode(None, 3)
n50, n70 = SkipNode(50, 3), SkipNode(70, 3)
head.next = [n50, n50, n70]
n50.next = [n70, n70, None]
print('Found', 70 if search_skip_list(head, 70) else 'nothing')

struct SkipNode {
    int value;
    vector<SkipNode*> next;
    SkipNode(int value, int levels) : value(value), next(levels, nullptr) {}
};

bool searchSkipList(SkipNode* head, int target) {
    SkipNode* current = head;
    for (int level = static_cast<int>(head->next.size()) - 1; level >= 0; --level) {
        while (current->next[level] != nullptr && current->next[level]->value < target) {
            current = current->next[level];
        }
    }
    SkipNode* candidate = current->next[0];
    return candidate != nullptr && candidate->value == target;
}

static class SkipNode {
    int value;
    SkipNode[] next;
    SkipNode(int value, int levels) {
        this.value = value;
        this.next = new SkipNode[levels];
    }
}

static boolean searchSkipList(SkipNode head, int target) {
    SkipNode current = head;
    for (int level = head.next.length - 1; level >= 0; --level) {
        while (current.next[level] != null && current.next[level].value < target) {
            current = current.next[level];
        }
    }
    SkipNode candidate = current.next[0];
    return candidate != null && candidate.value == target;
}

InputFind 70 in a 3-layer skip list

OutputFound 70

Example

Run the example step by step

Output

Probabilistic Balancing

Unlike trees which require strict rotations to stay balanced, skip lists balance themselves using probability. When a new node is inserted, a virtual 'coin' is flipped.

If it's heads, the node is added to the next layer up, and the coin is flipped again. If it's tails, the promotion stops. This guarantees that roughly half the nodes are on layer 1, a quarter on layer 2, etc.

Uses a random number generator for balancing
No complex tree rotations required
Expected height is O(log N)

Practical Applications

Because they avoid the complex locking mechanisms required by tree rotations, skip lists are extremely popular in concurrent (multi-threaded) environments.

They are used as the primary indexing structure in Redis (for Sorted Sets) and LevelDB, where simple implementation and high concurrent performance are critical.

Highly concurrent data structure
Used in Redis Sorted Sets
Excellent alternative to Red-Black Trees