What Is a Skip List?

A skip list is a linked, ordered data structure that adds multiple layers of “express lane” pointers on top of a regular linked list, letting search, insertion, and deletion all run in expected O(log n) time — comparable to a balanced binary search tree, but built from simple linked nodes and randomness instead of rotations and rebalancing logic.

The problem with a plain linked list

A sorted linked list keeps elements in order, but searching it means walking node by node from the head until you find (or pass) the target — O(n) in the worst case, no better than an unsorted array. Binary search would fix that, but binary search needs random access to the middle element, which a linked list can’t provide in constant time. Balanced trees like red-black or AVL trees solve the same problem, but they do it with rotation logic that’s notoriously fiddly to implement correctly.

How the layers work

A skip list solves this by giving some nodes extra pointers that skip ahead multiple positions, forming several layers:

• Layer 0 is the full sorted linked list — every element, in order, exactly like a normal linked list.
• Layer 1 contains a subset of those elements (roughly every other one), each with a pointer that skips past the elements not included in this layer.
• Layer 2 contains a smaller subset still, skipping even further ahead.
• This continues for however many layers the structure has, with the top layer typically containing just a handful of elements.

A search starts at the top layer and moves right until the next node’s value would overshoot the target, then drops down a layer and continues from there — repeating until it reaches layer 0, where the exact element (or its correct insertion point) is found. Each layer eliminates a large fraction of the remaining search space, the same logarithmic-reduction idea behind binary search trees, just implemented with pointers instead of a tree shape.

Why the layers are randomized

Rather than carefully maintaining perfect layer structure (which is what makes balanced trees complex), a skip list decides each node’s height randomly at insertion time — typically by flipping a coin repeatedly and adding another layer for each “heads,” so roughly half of nodes reach layer 1, a quarter reach layer 2, an eighth reach layer 3, and so on. This produces layer counts close to what a perfectly balanced structure would need, on average, without any explicit rebalancing step. Insertions and deletions only touch the layers a given node participates in, and there’s no cascading rotation logic to get right — which is the main appeal over trees: expected O(log n) performance with substantially simpler code.

Tuning the probability factor

The “flip a coin” description is the common case, where each node has roughly a 1-in-2 chance of being promoted to the next layer up. That fraction — the probability factor — doesn’t have to be one-half. Some implementations use a lower probability, such as one-in-four, which produces fewer layers with more elements skipped per hop. Lowering the promotion probability trades a small amount of extra work per layer traversal for fewer layers overall to maintain, which can reduce memory overhead from all those extra pointers at the cost of slightly more comparisons during a search. In practice, one-half is the default most implementations ship with, since it balances search speed against pointer overhead reasonably well without needing to tune anything.

Skip lists vs balanced trees

	Skip list	Balanced BST (red-black, AVL)
Average time complexity	O(log n)	O(log n)
Worst-case complexity	O(n) (rare, due to randomness)	O(log n) guaranteed
Implementation complexity	Simple — no rotations	Complex — rotation/rebalancing rules
Underlying structure	Layered linked list	Tree with parent/child pointers
Concurrency-friendliness	Easier to implement lock-free variants	Harder — rebalancing touches multiple nodes
Ordered range queries	Natural (walk layer 0)	Natural (in-order traversal)

The worst case for a skip list is technically unbounded — pure bad luck in the random coin flips could produce a degenerate structure — but the probability shrinks so fast with each additional layer that it’s not a practical concern, similar to how hash table worst-case collisions are a theoretical rather than practical risk with a decent hash function.

Where skip lists actually get used

Skip lists show up less often in application code than in the internals of infrastructure you already use. Redis’s sorted set data type is implemented as a skip list paired with a hash table, which is what lets Redis support both O(log n) ranked insertion and O(1) direct lookups on the same structure. Several database engines and concurrent data structure libraries favor skip lists over trees specifically because the layer-based design is easier to make thread-safe without heavyweight locking.

The takeaway

A skip list gets tree-like O(log n) search, insert, and delete out of a linked list by layering shortcut pointers on top, with each node’s height decided by a random coin flip instead of an explicit balancing algorithm. The tradeoff for that simplicity is a worst case that’s technically unbounded rather than guaranteed — in practice a non-issue — which is why skip lists show up as the backing structure for ordered data in real systems like Redis, wherever “simple to implement correctly” wins out over the tighter guarantees of a balanced tree.