Skip Lists and Probabilistic Linking

Standard linked lists present us with a serious limitation when we want to search the collection for a specific element. They require us to traverse the list from start to end: a slow, $O(N)$ process. If we have 100,000 elements, finding one might require 100,000 checks.

When we covered logarithmic algorithms , we saw how binary search solves this problem when the collection is sorted. By checking the middle element, we instantly discard half the dataset. We then check the middle element of what remains, and we cut the problem in half again. This divide-and-conquer approach means searching a sorted array is a $O(\text{log }N)$ process. Finding any record in a collection of 100 takes no more than 7 steps; finding a record in a collection of 10 million takes just 24 steps.

But binary search can't be used with a typical linked list, even when it is sorted. Linked lists do not support index-based access - we can't "check the middle element".

If we want fast search speed in a node-based architecture, the standard answer is to use a binary search tree (BST), which underpins containers like std::map and std::set.

We'll cover trees later in the course, but in this lesson, we will look at a lightweight, list-based alternative. Skip lists provide the same $O(\text{log }N)$ search performance as binary search, with a simpler architecture and some key advantages when it comes to concurrency.

The key idea that unlocks $O(\text{log }N)$ searching of a sorted linked list is that we need to provide our traversal algorithms with a way to skip over many nodes in a single jump. We do this by providing it with some express lanes.

Instead of each node having a single Next pointer, it has an array of Next pointers - one pointer for each lane the node is in. These lanes are usually described in terms of levels.

Level 0 is the standard, slow lane we're accustomed to. Every node gets a Level 0 pointer to the next node in the list, and if we want to traverse through every node, we use the Level 0 lane by jumping through those pointers as usual.

Level 1 is a faster lane that skips over a few nodes to speed up traversal. Level 2 is an even faster lane that skips even more nodes:

This allows us to implement the "jump to the middle, then discard half of the elements" algorithm of binary search in a slightly different way. In our 8-element example above, we can jump around the middle of the collection in a single jump using our level 2 lane. We can then jump to around the middle of what remains using our level 1 lane.

As our list gets bigger, we can add more levels to maintain this divide-and-conquer ability. We could have a level 5 lane that skips over dozens of nodes on an average jump; a level 10 lane that skips over thousands; a level 20 lane that skips over millions.

Designing the Node

Later in the lesson, we'll cover the strategy we use to set up our lanes to achieve this divide-and-conquer distribution, but let's first cover our basic Node structure and the search algorithm.

Again, we could use pool-allocated nodes with index-based links here, but we'll stick to simple, globally-allocated nodes linked together using pointers to reduce the complexity of this lesson.

We will use a std::array to hold up to 16 pointers within the node, meaning we support up to 16 lanes (Level 0 to Level 15):

1#pragma once
2#include <array>
3#include <iostream>
4
5template <typename T>
6class SkipList {
7private:
8  static constexpr int MAX_LEVEL = 16; 
9
10  struct Node {
11    T Payload;
12
13    // An array of pointers, one for each lane
14    std::array<Node*, MAX_LEVEL> Next{}; 
15
16    // Construct a node with zeroed-out pointers
17    Node(T val) : Payload{val} {
18      Next.fill(nullptr);
19    }
20  };
21
22  // The entry point
23  Node* Head;
24
25  // Track the highest level currently in use across the whole list
26  int CurrentMaxLevel{0};
27
28public:
29  SkipList() {
30    // The Head node contains no useful payload,
31    // it just anchors the start of the pointer chains.
32    Head = new Node(T{});
33  }
34
35  ~SkipList() {
36    // Standard linked list cleanup via Level 0
37    Node* Current = Head;
38    while (Current != nullptr) {
39      Node* ToDelete = Current;
40      Current = Current->Next[0]; 
41      delete ToDelete;
42    }
43  }
44};

To find a value, we start at the Head node on the CurrentMaxLevel. We look at the pointer in that lane. If it leads to a node smaller than our target, we jump to it. We keep jumping forward on that level until we hit a nullptr (the end of the list) or a value greater than our target.

When we overshoot, we drop our "vision" down one level and look at the pointer in the slower lane, repeating the process until we reach Level 0.

1// ...
2
3template <typename T>
4class SkipList {
5  // ...
6
7public:
8  // ...
9
10  bool Contains(const T& Value) const {
11    Node* Current = Head;
12
13    // Start at the top of the tower and work downwards
14    for (int i = CurrentMaxLevel; i >= 0; i--) { 
15
16      // Glide forward on the current level as long as the
17      // next node's payload is less than what we are looking for.
18      while (Current->Next[i] != nullptr && 
19             Current->Next[i]->Payload < Value) { 
20
21        // Execute the jump
22        Current = Current->Next[i]; 
23      }
24    }
25
26    // We have bottomed out at Level 0.
27    // 'Current' is the largest node strictly less than our Value.
28    // The node immediately to the right MUST be our target, or
29    // the target does not exist in the list.
30    Current = Current->Next[0]; 
31
32    return Current != nullptr && Current->Payload == Value;
33  }
34};

How do we decide which nodes get to be on Level 1, Level 2, or Level 15?

If we tried to mandate a strict mathematical rule like "every 4th node must have a Level 2 pointer", our performance would collapse on insertion and deletion. If we insert a new node at the front of the list, we would have to walk the entire rest of the list, demoting and promoting pointers to satisfy the "every 4th node" rule. This would slow our insertions and deletions to a crawl, removing the key advantage of linked lists.

If we look at our Contains() algorithm above, it doesn't care if our links are perfectly distributed. We could have five Level 3 nodes right next to each other, and then a gap of twenty nodes before the next one. The algorithm will still work.

So, instead of mandating a perfect distribution, we can rely on probability. When we insert a new node, we give it a Level 0 pointer by default. Then, we flip a coin. If it lands on Heads, we give it a Level 1 pointer and flip again. If it lands on Heads again, it gets a Level 2 pointer. The moment we roll Tails, we stop growing the tower.

This probabilistic model can create some weird distributions at small scales, but in the real world, skip lists are used for collections containing thousands or millions of elements, spanning across dozens of lanes. At that scale, the probability naturally evens out, creating a nearly perfect $O(\text{log }N)$ structure where:

• 100% of nodes will have a level 0 pointer
• Approximately 50% will have a level 1 pointer
• Approximately 25% will have a level 2 pointer
• Approximately 12.5% will have a level 3 pointer

This halving pattern continues until we reach the MAX_LEVEL we decided upon when designing our node. If our nodes had capacity for 16 pointers (from Level 0 to Level 15) this halving pattern would result in around 0.003% of nodes getting a Level 15 pointer.

This means our level 15 fast lane would skip around 32,000 nodes on each jump, enabling "jump to the middle" binary search performance for sorted collections up to around 64,000 elements. If we bumped our nodes up to 32 pointers, our Level 31 pointers would skip around 2 billion nodes, giving us $O(\text{log }N)$ searching of sorted lists containing up to 4 billion elements.

Let's implement our probabilistic level generator:

1#include <random> 
2
3template <typename T>
4class SkipList {
5  // ...
6private:
7  // Random number generator setup
8  std::mt19937 RNG{std::random_device{}()}; 
9  std::uniform_int_distribution<int> CoinFlip{0, 1}; 
10
11  // Generate a height using a geometric distribution (coin flips)
12  int GenerateRandomLevel() {
13    int Level = 0;
14
15    // 50% chance to grow a level, capped at our MAX_LEVEL - 1
16    while (CoinFlip(RNG) == 1 && Level < MAX_LEVEL - 1) { 
17      Level++; 
18    }
19
20    return Level;
21  }
22
23  // ...
24};

Inserting a node into a skip list requires us to slice the new pointer tower into the existing express lanes.

When we search for the insertion spot, we have to drop down from Level N to Level 0. Every time we drop down a level, the node we are standing on is the exact node that needs its Next pointer updated to point to our newly inserted node.

To keep track of this, we create an array called Update. As we walk down the tower, we record the node we were standing on right before we dropped down.

1// ...
2
3template <typename T>
4class SkipList {
5  // ...
6
7public:
8  // ...
9
10  void Insert(const T& Value) {
11    // An array to remember the nodes that need
12    // their pointers rewired
13    std::array<Node*, MAX_LEVEL> Update{}; 
14
15    Node* Current = Head;
16
17    // Search for the insertion point, tracking
18    // our path downwards
19    for (int i = CurrentMaxLevel; i >= 0; i--) {
20      while (Current->Next[i] != nullptr &&
21             Current->Next[i]->Payload < Value) {
22        Current = Current->Next[i];
23      }
24      // Record the node right before we drop down
25      Update[i] = Current; 
26    }
27
28    // Move to the exact insertion gap on Level 0
29    Current = Current->Next[0];
30
31    // If the value already exists, do nothing
32    // (assuming a set-like structure with no duplicates)
33    if (Current != nullptr && Current->Payload == Value) {
34      return;
35    }
36
37    // Flip the coin to determine the new node's height
38    int NewLevel = GenerateRandomLevel(); 
39
40    // If the new node is taller than any node currently
41    // in the list, we need to update the Head to anchor
42    // these new express lanes.
43    if (NewLevel > CurrentMaxLevel) { 
44      for (int i = CurrentMaxLevel + 1; i <= NewLevel; i++) { 
45        Update[i] = Head; 
46      } 
47      CurrentMaxLevel = NewLevel; 
48    }
49
50    // Create the node and splice it into the lanes
51    Node* NewNode = new Node(Value);
52
53    for (int i = 0; i <= NewLevel; i++) { 
54      // The new node points to whatever the Update
55      // node used to point to
56      NewNode->Next[i] = Update[i]->Next[i]; 
57
58      // The Update node now points to our new node
59      Update[i]->Next[i] = NewNode; 
60    } 
61  }
62};

We execute a standard search, flip a coin, and do some basic pointer reassignment. The entire insertion process operates locally. We do not look at, touch, or modify any nodes beyond the immediate neighbors we recorded in the Update array.

Implementing Deletion

Deletion is mechanically identical to insertion. We construct the Update array to find all the pointers that lead to our victim node. We then bypass the victim by making the Update nodes point to whatever the victim was pointing to, and finally, we delete the victim.

1// ...
2
3template <typename T>
4class SkipList {
5  // ...
6
7public:
8  // ...
9
10  void Remove(const T& Value) {
11    std::array<Node*, MAX_LEVEL> Update{};
12    Node* Current = Head;
13
14    for (int i = CurrentMaxLevel; i >= 0; i--) {
15      while (Current->Next[i] != nullptr &&
16             Current->Next[i]->Payload < Value) {
17        Current = Current->Next[i];
18      }
19      Update[i] = Current;
20    }
21
22    Current = Current->Next[0];
23
24    // If the target doesn't exist, there is nothing to remove
25    if (Current == nullptr || Current->Payload != Value) {
26      return;
27    }
28
29    // Rewire the pointers to bridge over the dying node
30    for (int i = 0; i <= CurrentMaxLevel; i++) { 
31      // If this level doesn't even point to our victim,
32      // we can stop
33      if (Update[i]->Next[i] != Current) { 
34        break; 
35      }
36
37      // Splice the victim out of this lane
38      Update[i]->Next[i] = Current->Next[i]; 
39    }
40
41    delete Current;
42
43    // If we just deleted the tallest node in the list,
44    // we should shrink the CurrentMaxLevel to optimize
45    // future searches.
46    while (
47      CurrentMaxLevel > 0 &&
48      Head->Next[CurrentMaxLevel] == nullptr
49    ) {
50      CurrentMaxLevel--;
51    }
52  }
53};

Let's pit our custom SkipList against std::list - a flat $O(N)$ pointer chain, and std::set - a $O(\text{log }N)$ binary search tree.

We will populate all three structures with 100,000 randomized integers, and then benchmark how long it takes to find a target value.

1#include <benchmark/benchmark.h>
2#include <list>
3#include <set>
4#include <algorithm>
5#include <dsa/SkipList.h>
6
7// Generate randomized data
8std::vector<int> GetRandomData(int size) {
9  std::vector<int> data(size);
10  for (int i = 0; i < size; ++i) data[i] = i;
11  std::mt19937 g(42);
12  std::ranges::shuffle(data, g);
13  return data;
14}
15
16static void BM_StdList_Search(benchmark::State& state) {
17  std::vector<int> data = GetRandomData(100000);
18  std::list<int> l;
19  for (int v : data) l.push_back(v);
20
21  for (auto _ : state) {
22    // O(N) Linear pointer chasing
23    auto it = std::find(l.begin(), l.end(), 99999); 
24    benchmark::DoNotOptimize(it);
25  }
26}
27BENCHMARK(BM_StdList_Search);
28
29static void BM_StdSet_Search(benchmark::State& state) {
30  std::vector<int> data = GetRandomData(100000);
31  std::set<int> s;
32  for (int v : data) s.insert(v);
33
34  for (auto _ : state) {
35    // O(log N) Red-Black tree search
36    auto it = s.find(99999); 
37    benchmark::DoNotOptimize(it);
38  }
39}
40BENCHMARK(BM_StdSet_Search);
41
42static void BM_SkipList_Search(benchmark::State& state) {
43  std::vector<int> data = GetRandomData(100000);
44  SkipList<int> sl;
45  for (int v : data) sl.Insert(v);
46
47  for (auto _ : state) {
48    // O(log N) Skip list search
49    bool found = sl.Contains(99999); 
50    benchmark::DoNotOptimize(found);
51  }
52}
53BENCHMARK(BM_SkipList_Search);

1----------------------------
2Benchmark                CPU
3----------------------------
4BM_StdList_Search    2888 ns
5BM_StdSet_Search     13.8 ns
6BM_SkipList_Search   17.3 ns

As expected, the $O(N)$ search performance of std::list struggles at this scale.

Our custom SkipList performs comparably to the highly optimized std::set in these tests. The primary advantage a binary search tree like std::set has are its physically smaller nodes. Each node holds only 3 pointers instead of the 16 of our SkipList, resulting in better cache utilization.

The pointer overhead of a skip list is particularly egregious when the payload itself is relatively small. Each node in our SkipList<int> has only 4 bytes of core data (the int payload) surrounded by 128 bytes of pointers.

However, the skip list achieves logarithmic search performance with significantly less architectural complexity than a tree, and it has particular advantages when we need to implement concurrency.

Advanced: The Concurrency Advantage

One of the main advantages of skip lists over alternatives that provide similar performance comes when we want to implement multithreading.

As we learned in our chapter on atomics , locking a data structure can be catastrophic for throughput. If 16 cores are constantly fighting over a std::mutex to read from our structure, 15 cores will be asleep while 1 core does the work.

If we use a binary search tree like std::set, inserting a single node might trigger a cascade of tree rotations to keep the structure balanced, which forces massive portions of the data structure to become locked.

We cover binary search trees and their balancing mechanism in more detail later in the course, but with a skip list, the balancing of the lanes is an elegant, natural side-effect of the probabilistic assignments. Major structural adjustments are never required - when we insert a node, the only memory addresses we modify are the immediate neighbors in the Update array. The rest of the 100,000 nodes are completely untouched.

This means a skip list is incredibly easy to make lock-free or highly concurrent using fine-grained locks. We can have 16 threads inserting and searching a skip list at the same time, and as long as they aren't trying to modify the same local neighborhood of pointers, they will never block each other.

Here is the complete implementation of our probabilistic SkipList:

In this lesson, we engineered our way out of the $O(N)$ linear search trap.

1. We constructed a skip list by adding an array of Next pointers to our nodes, creating algorithmic express lanes that skip vast portions of the data.
2. We achieved perfect mathematical balancing without complex tree rotations by using probabilistic coin flipping to determine the height of our pointer towers.
3. We explored the concurrency advantage of skip lists over Red-Black trees. By avoiding structural rotations, skip lists allow for highly localized, thread-safe memory updates, making them the architecture of choice for many high-performance concurrent systems.