Skip Lists - A ubiquitous probabilistic data structure

Introduction

I truly love learning new data structures and implementing them. Skiplist is a data structure that I've learnt about a long time ago and have been meaning to implement for some time. Recently, I've joined Stripe as an Engineering Manager of a team that writes most of its code in Golang. Given that it's been years since I wrote Go code, I decided to use the opportunity to hit two birds with one stone. Implement a Skiplist in Golang.
The code for this blog can be found here

Why Skiplist

Skip lists offer a simple yet powerful alternative to balanced trees for ordered data structures. They provide fast search, insertion, and deletion—typically in O(logn) time by using multiple levels of linked lists to "skip" over large portions of data. Unlike trees, skip lists are easier to implement, require less complex balancing logic, and are highly adaptable for concurrent environments. Their probabilistic nature ensures good average-case performance, making them a popular choice in databases, caching systems, and applications where simplicity and speed are both important.

When is a Skiplist better than a Red-Black Tree or a Splay Tree?

Short answer: when you want simple code, predictable latency without rotations, and great concurrency with ordered iteration.

• Simpler implementation and maintenance

  • Red-black trees require rotations and strict invariants; splay trees continuously restructure on access. Skiplists use a handful of pointer updates with no rotations, so they’re easier to implement, review, and debug.
  • Augmentations (like keeping widths for rank/select, or attaching metadata) are often simpler to bolt onto skiplists than rebalancing tree variants.

• Concurrency friendliness

  • Rotations make fine-grained locking in trees tricky and can invalidate iterators mid-operation. Skiplists can use per-node/level locks or lock-free techniques with localized changes that don’t ripple through the structure.
  • This is why highly concurrent, ordered maps often choose skiplists (e.g., ConcurrentSkipListMap in Java; Redis uses a skiplist for sorted sets alongside a hash table).

• Stable latencies vs. splay behavior

  • Splay trees optimize for locality but can produce large single-operation spikes (amortized O(log n), but worst-case O(n)). Skiplists deliver more consistent O(log n)-ish latencies without big rotations, which is helpful for tail-latency-sensitive systems.

• Natural range queries and ordered iteration

  • Both trees and skiplists support O(log n + k) range scans. In practice, skiplists make “start at key and scan forward” ergonomically simple and cache-friendly once you’re on the bottom level.

• Tunable memory/perf trade-off

  • With probability p (commonly 0.5), the expected number of forward pointers per node is ~1/(1-p) (≈2 when p = 0.5). You can adjust p and max level to trade memory for speed.
  • Trees have more rigid pointer overhead (2 child pointers, often a parent pointer, plus color/metadata), while skiplists let you dial the overhead to your workload.

• Easier joins/merges in practice

  • Joining two ordered structures or bulk-building from sorted data tends to be simpler with skiplists; tree joins/rebalances are more intricate and error-prone.

When not to use a skiplist

• Hard real-time worst-case guarantees: red-black trees provide strict O(log n) worst case; skiplists are probabilistic (though capping the max level can bound the worst case in practice).
• Single-threaded workloads with strong temporal locality: splay trees can shine thanks to self-adjustment.

Rule of thumb

• If you need an ordered map/set with simple code, great concurrent behavior, easy iteration and range scans, and solid average-case performance, a skiplist is an excellent default.
• If you must have strict worst-case guarantees, pick a red-black tree. If your access pattern is extremely skewed and single-threaded, consider a splay tree.

Design Details

This is a language-agnostic view of how a skip list is structured and implemented.

Building blocks

• Total order: keys must have a strict total order (comparator that is transitive, antisymmetric, and total).
• Nodes with multiple forward pointers: each node participates in one or more “levels,” storing an array of forward references (next pointers) one per level it appears in.
• Levels: level 0 is a regular sorted linked list containing all elements; each higher level contains a sparser subset, enabling long forward “skips.”
• Sentinels: a head (sentinel) node with the maximum level simplifies edge cases; an optional tail sentinel can be used or you can terminate with null.

Height distribution (probabilistic balancing)

• On insertion, a node’s height is chosen randomly using a geometric distribution: promote the node to the next level with probability p (commonly p = 1/2 or 1/4) until a cap (maxLevel).
• Expected node height is 1/(1−p); expected maximum level among n elements is about log(1/p)(n).
• Result: expected O(log n) search, insert, and delete time without explicit rotations or complex rebalancing.

Core operations

Search (find key k)

1. Start at the head on the highest current level L.
2. While the next node on this level exists and next.key < k, move forward.
3. If next is missing or next.key ≥ k, drop down one level and repeat.
4. At level 0, either next.key == k (found) or next.key > k / none (not found).

Insert (key k, value v)

1. Perform a search while recording, for each level i, the last node visited before k (the “predecessor” at level i). Often stored in an array update[i].
2. If key k already exists at level 0, update its value and stop (upsert behavior) or reject duplicates depending on your policy.
3. Randomly choose a height h for the new node. If h exceeds the current top level, increase the top level and initialize new entries in update.
4. For each level i ∈ [0..h], splice the new node between update[i] and update[i].next: new.next[i] = update[i].next[i]; update[i].next[i] = new.

Delete (key k)

1. Compute update[] by doing a search as above.
2. If the node x with key k exists, for each level i where x appears, bypass it: update[i].next[i] = x.next[i].
3. If the highest level becomes empty (head.next[top] is null), decrease the top level.

Range iteration and finger search

• Range [lo, hi]: search for lo, then iterate forward along level 0 until passing hi. Cost: O(log n + m) for m outputs.

Complexity and space

• Expected time: search/insert/delete are O(log n); iteration of k items is O(k) once you’re positioned.
• Space: O(n) nodes with an expected number of forward pointers per node of ~1/(1−p). With p = 1/2, that’s about 2 pointers per node on average.

Tuning parameters

• Probability p: smaller p (e.g., 1/4) creates taller structures (faster searches, more pointers); larger p (e.g., 1/2 or 2/3) creates shorter structures (less memory, slightly slower).
• Max level: set as a function of an expected capacity, roughly ceil(log_{1/p}(Nmax)), or choose a fixed cap like 32 or 64.

Correctness invariants

• Order: at every level, forward pointers maintain strictly increasing keys.
• Level monotonicity: a node present at level i is also present at all levels < i.
• Sentinel: the head has the maximum level; all level chains eventually terminate.
• Comparator consistency: must impose a strict total order; violations break the structure.

Variants and extensions

• Indexable skip list: store “widths” (number of base-level steps) on forward pointers to support rank/select (find by index) in O(log n).
• Deterministic skiplists: instead of randomness, rebalance using deterministic promotions to retain logarithmic behavior.
• Concurrency: fine-grained locking or lock-free techniques are practical because updates are localized; iterators can be designed to remain valid across many operations.

Edge cases and policies

• Duplicates: either disallow, coalesce values, or store duplicates as a multiset (e.g., by tiebreaking on insertion order).
• Empty structure: all head forward pointers are null at start.
• Tail behavior: use an explicit tail sentinel or null terminators consistently across levels.

In short: a skip list is a stack of increasingly sparse sorted lists with probabilistic heights. Searches skip ahead on higher levels and drop down to refine, while inserts and deletes splice nodes at only the levels they occupy—yielding simple code and reliable expected performance.

Diagram: how skipping works

The picture below shows four levels (3 down to 0). Level 0 contains all elements; higher levels contain sparser shortcuts. We search for 33.

Levels top → bottom (3..0)

L3:  [HEAD] ───────────────────────────────► [50] ─────────► nil
L2:  [HEAD] ─────► [20] ───────────────────► [50] ─────────► nil
L1:  [HEAD] ───► [10] ─► [20] ─────────► [35] ─► [50] ─► nil
L0:  [HEAD] ─► [5] ► [10] ► [15] ► [20] ► [30] ► [35] ► [40] ► [50] ► nil
						   │
Search for 33:             ▼
L3: move right? next=50 > 33 → drop to L2
L2: move right to 20; next=50 > 33 → drop to L1
L1: move right to 20; next=35 > 33 → drop to L0
L0: move right to 30; next=35 ≥ 33 → stop
Result: not found; insertion point is between 30 and 35 at level 0.

Diagram: inserting by splicing

If the random height of key 33 is 2 (so it appears on levels 0 and 1), we splice it between its predecessors and successors on those levels.

Before
L1:  [HEAD] ───► [10] ─────────►   [20] ───►     [35] ───►     [50] ─► nil
L0:  [HEAD] ─► [5] ► [10] ► [15] ► [20] ► [30] ► [35] ► [40] ► [50] ► nil

After inserting 33 with height=2 (levels {0,1})
L1:  [HEAD]─────────►[10]─────────►  [20]─────────►[33] ─►[35]─────────►[50] ─► nil
L0:  [HEAD] ─► [5] ► [10] ► [15] ► 	 [20] ► [30] ► [33] ► [35] ► [40] ► [50] ► nil

Legend

• HEAD: sentinel node with maximum level.
• Horizontal arrows: forward pointers on each level.
• Drops between levels: when you can’t advance on a higher level, you “drop down” to continue the search more precisely.

Golang implementation

This project includes a Go implementation that follows the design above and uses generics for type safety.

Core types

• node[K, V]: holds key, value, and a slice of forward pointers (one per level it participates in).
• SkipList[K, V]: holds the head sentinel, current top level, probability p, maxLevel cap, comparator, size, and an RNG for height generation.

Minimal shape:

type node[K any, V any] struct {
	key     K
	value   V
	forward []*node[K, V]
}

type SkipList[K any, V any] struct {
	head     *node[K, V]
	level    int
	maxLevel int
	p        float64
	cmp      func(a, b K) int
	size     int
	rng      *rand.Rand
}

API surface (typical)

• New(cmp, options...): create a list with a comparator and optional p/maxLevel/seed.
• Put(k, v): insert or update (upsert) a key.
• Get(k) (v, ok): look up a key.
• Delete(k) bool: remove a key if present.
• Contains(k) bool: membership test.
• Len() int: number of items.
• Range(from, to, inclusive bool, fn func(k K, v V) bool): in-order iteration with early stop.
• IteratorFrom(k): returns an iterator starting at the first key ≥ k.

Random height

Heights follow a geometric distribution with probability p (default 0.5) up to maxLevel. An injected/seeded RNG gives deterministic tests when needed.

func (s *SkipList[K, V]) randomLevel() int {
	lvl := 0
	for lvl+1 < s.maxLevel && s.rng.Float64() < s.p {
		lvl++
	}
	return lvl
}

Design choices

• Upsert semantics: inserting an existing key replaces its value.
• Comparator-driven ordering: works with any key type as long as you provide a strict total order.
• Not synchronized by default: wrap with sync.RWMutex externally if you need concurrent writes.
• Range scans are first-class: search to the start key, then iterate on level 0.

Usage example

sl := skiplist.New[int, string](func(a, b int) int { return a - b })
sl.Put(10, "ten")
sl.Put(5, "five")
sl.Put(7, "seven")

if v, ok := sl.Get(7); ok {
	fmt.Println("found:", v)
}

sl.Range(5, 10, true, func(k int, v string) bool {
	fmt.Println(k, v)
	return true // continue
})

Performance is the expected O(log n) for lookups/updates and O(k) for scanning k items once positioned. The implementation keeps pointer updates localized and avoids rotations entirely.

Conclusion

While the math behind the runtime analysis is slightly more complicated due to the probabilistic nature of the Skiplist the implementation itself is relatively straighforward once you understand the concepts. Skiplists are used in many libraries and frameworks and due to their relatively easier implementation, make a great choice anytime you would need an ordered data structure. Hopefully, this post has made them more accessible for everyone interested in using them.