Info & Theory
A skip list is a sorted linked list with stacked express lanes. Higher lanes hold fewer nodes, so a search can leap far ahead, then drop down for precision.
Building levels by coin flip
Every node starts at level 1. We flip a fair coin: with
probability ½ the node is promoted one level
higher, repeating until tails. So ~half the nodes reach level 2,
~a quarter level 3, and so on.
The search pattern
- Start at the head of the top level.
- Move forward while the next key is smaller than the target.
- When the next key would overshoot, drop down a level.
- Repeat to level 1, then check the final node.
Why O(log n)
With about log₂(n) levels and a constant number of
forward steps expected per level, the expected search cost is
O(log n) — matching a balanced tree, but reached by
randomness instead of rotations.
Where it is used
Skip lists power Redis sorted sets, LevelDB
memtables, and concurrent ordered maps such as Java's
ConcurrentSkipListMap.
How this simulation works
This is a real skip list. When you insert a key it is placed in sorted
order at level 1, then a seeded coin is flipped repeatedly: each
heads promotes the new node one level higher, so its tower of
forward pointers grows with probability ½ per level. When
you press Search, the animated cursor starts at the head of the
top express lane and moves forward while the next key is smaller than
the target, dropping down a level whenever the next step would
overshoot — the classic skip-then-drop walk that visits expected
O(log n) nodes.
Reading the canvas
Each horizontal row is one level; the bottom row is the
complete sorted list and every row above is an express lane holding
the promoted subset, joined by forward pointers. During a search the
visited nodes are highlighted so you can trace the route. The stats
panel shows the current level count, node count, the
theoretical expected hops (about log₂(n)) and the
actual hops the last search really took, letting you compare
theory against a single run.
Frequently asked questions
What is a skip list?
A skip list is a randomised data structure built from a sorted linked list with extra "express lane" layers stacked on top. Higher layers contain fewer nodes, so a search can skip ahead quickly on the top lanes and drop down to find a key in expected O(log n) time.
How are the levels chosen?
When a node is inserted it starts at level 1, then a coin is flipped: with probability one-half it is promoted to the next level up, and the flips continue until one comes up tails. So about half the nodes reach level 2, a quarter reach level 3, and so on.
How does search work?
Search starts at the head of the highest level and moves forward while the next key is smaller than the target. When the next key would overshoot, it drops down one level and continues. This skip-then-drop pattern repeats until level 1, where it either lands on the key or steps past it.
Why is search O(log n) on average?
Because each level holds about half the nodes of the one below, there are roughly log2(n) levels, and the expected number of forward steps on each level is constant. Together that gives an expected search cost of O(log n) hops.
How is a skip list different from a balanced tree?
Both achieve O(log n) search, but a skip list reaches its balance through randomness rather than rotations or recolouring. It is simpler to implement and very friendly to concurrent access, which is why it appears in systems such as Redis sorted sets and LevelDB memtables.
What does "expected vs actual hops" mean here?
The expected hop count is the theoretical estimate, roughly log2(n), for searching the current list. The actual hops are the real forward-and-down moves the animated cursor made on the last search, so you can compare theory with one concrete run.
What happens if I search for a key that is not present?
The cursor follows exactly the same skip-then-drop path and stops at level 1 just before where the key would sit. The simulation reports a miss, and the visited nodes are still highlighted so you can see the route taken.
Is the randomness fixed or different each run?
Each insertion uses a seeded pseudo-random generator for its coin flips, so the level pattern is reproducible within a session. Clearing the list reseeds it, and you can rebuild the same shape by inserting the same keys in the same order.
Where are skip lists used in practice?
They back the sorted-set type in Redis, the in-memory memtables of LevelDB and similar key-value stores, and several concurrent ordered-map implementations, including Java's ConcurrentSkipListMap.
What are the express lanes in the drawing?
Each horizontal row is a level. The bottom row is the full sorted list; each row above is an express lane holding the subset of nodes promoted to that height, with forward pointers letting a search leap over many bottom-level nodes at once.