A skip list is a sorted linked list with extra 'express lane' layers stacked on top. The bottom layer holds every element; each higher layer holds a sparse, random subset, so a search can skip long distances up high and refine as it descends. It gives O(log n) expected search, insert and delete using only linked-list operations and coin flips — no tree rotations.

How does searching a skip list work?

Start at the top-left. Move right while the next node's value is less than or equal to your target; when the next value would overshoot, drop down one level and continue. You keep skipping far on the sparse upper lanes and refining on the denser lower ones, landing on the target (or where it would be) after O(log n) steps.

Why use a skip list instead of a balanced tree?

Both give O(log n) operations, but skip lists are dramatically simpler to implement — there are no rotations or rebalancing cases, just linked-list splicing and a coin flip to decide a new node's height. They're also naturally easy to make concurrent (lock-free variants exist), which is why systems like Redis's sorted sets and several databases use them.

How are the levels chosen?

Randomly. When inserting a node, flip a coin: with probability 1/2 it gets promoted to the next level up, and you keep flipping until you fail. So about half the nodes reach level 1, a quarter reach level 2, and so on — giving the sparse-on-top, dense-on-bottom shape that makes search logarithmic, in expectation, without any explicit balancing.

Algorithms · Probabilistic Structures

The Skip List.

A sorted linked list is honest but slow: to find a value you walk every node, O(n). The skip list adds express lanes — sparse extra layers stacked on top — so search rides far up high and drops down to refine. The payoff is O(log n) search, insert and delete, matching a balanced tree, but built from coin flips instead of rotations.

O(log n) expected · probabilistic · no rotations

express lane

A sparse upper layer that skips over many nodes at once.

right then down

Search moves right while it can, drops a level when it would overshoot.

coin-flip levels

Each node’s height is random: ~½ reach level 1, ¼ level 2…

tree rival

Same O(log n) as a balanced tree — far simpler code, easy to make concurrent.

skiplist.js — right while you can, else drop

search for: 19 7 25 12

Ready

A sorted set stored as a skip list — sparse express lanes on top, every value on the bottom. Pick a target and press Step: from the top-left, move right while the next value ≤ target, else drop a level.

level

hops

–

vs linear

How it works

Picture a highway map. The bottom lane is a local road stopping at every town (every value). Above it are express lanes that skip most towns. To reach a destination you get on the highest express lane, drive right until the next exit would overshoot, drop to a lower lane, and repeat — refining as the lanes get denser. That’s a skip-list search.

Start top-left

Begin at the head node on the highest express lane.

Go right while you can

While the next node’s value is ≤ your target, move to it. Each hop skips everything between.

Overshoot → drop a level

When the next value would exceed the target, drop to the lane below and keep going right.

✓

Land at level 0

At the bottom lane you arrive exactly at the target, or at the gap where it would be. ~log₂(n) hops total.

O(log n) exp.

Insert / delete

O(log n) exp.

Space

O(n) expected

Rotations

none

The code

# search a skip list: right while you can, else drop def search(head, target): node = head for level in reversed(range(head.height)): while node.next[level] and node.next[level].val <= target: node = node.next[level] # skip right return node if node.val == target else None # insert: search for position, then flip a coin for height — # promote to the next level with probability 1/2, splice in.

Insert and delete reuse the same search to find the position, then splice the node into every level it reaches. The height comes from a coin flip loop — no rebalancing logic at all. That simplicity, plus easy concurrency, is why Redis sorted sets and several databases pick skip lists over balanced trees.

Quick check

1. Why do the express lanes make search O(log n)?

2. What’s the big advantage over a balanced tree?

FAQ

What is a skip list?

A sorted linked list with sparse express-lane layers stacked on top, giving O(log n) expected search, insert and delete from linked-list operations plus coin-flip node heights.

How does search work?

From the top-left, move right while the next value ≤ target, drop a level when it would overshoot, and repeat down to the bottom lane — landing on the target or its gap.

Where are skip lists used?

Redis sorted sets, LevelDB/RocksDB memtables, Apache Lucene, and various concurrent maps — anywhere an ordered structure with simple, concurrent-friendly O(log n) ops is wanted.

Are the O(log n) bounds guaranteed?

They're expected, not worst-case — a run of unlucky coin flips could skew the levels. In practice the probability of bad behavior is astronomically small, and the simplicity usually wins over a tree's hard guarantee.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

The Skip List.

How it works

Start top-left

Go right while you can

Overshoot → drop a level

Land at level 0

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Start top-left

Go right while you can

Overshoot → drop a level

Land at level 0

The code

Quick check

FAQ

Keep going

Binary Search →

Linked Lists →

Redis (sorted sets) →

AVL Trees →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.