⏭️ Skip List
Probabilistic balanced search
Insert a key to begin
Last search: —
Insert / search a key
Stats
Levels
1
Nodes
0
Expected hops
0
Actual hops
0
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.

About Skip List

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

A skip list, introduced by William Pugh in 1990, is a probabilistic data structure that maintains a sorted sequence of elements across multiple linked-list layers. The bottom layer is a complete sorted list; each higher layer acts as an "express lane" by retaining only a random subset of the layer below, with each element independently promoted with probability p (typically 0.5). Search, insertion, and deletion all achieve expected O(log n) time — matching a balanced BST — without the deterministic rebalancing overhead of AVL or red-black trees.

This simulation lets you insert and delete integer keys while watching each node's tower grow to a random height. The highlighted traversal path during search shows how the algorithm descends through express lanes before dropping to the next layer, illustrating why the average number of comparisons is approximately log1/p n.

Frequently Asked Questions

How does a skip list achieve O(log n) search without deterministic balancing?

Each node's height is drawn independently from a geometric distribution with success probability p, so the expected number of nodes at level k is n·pk. A search starts at the highest level, advances as far as possible, then drops down — the expected total comparisons is log1/p n + 1/p, which is O(log n). Randomness effectively balances the structure in expectation without any explicit rotations.

What is the worst-case time complexity of a skip list?

The worst-case time is O(n) — for instance if every node happens to be promoted to every level — but this occurs with exponentially small probability. In practice, skip lists are used where probabilistic guarantees are acceptable (e.g., Redis's sorted sets use a skip list internally), since worst-case guarantees from balanced trees are rarely needed in those contexts.

How much memory does a skip list use compared to a balanced BST?

With promotion probability p = 0.5, the expected total number of pointers across all levels is 2n (each node contributes one pointer per level, expected height 1/(1−p) = 2). A standard red-black tree node also stores two child pointers plus a parent pointer and a colour bit, so the memory usage is comparable; skip lists often have slightly higher constant factors due to the variable-length tower allocations.

How does skip list insertion maintain sorted order?

Insertion first searches for the position where the new key belongs (recording the rightmost node visited at each level in an update array), then generates a random height h for the new node, and finally splices it into each level from 0 to h−1 by updating the forward pointers recorded during the search. This is analogous to insertion into a linked list but repeated for each active level.

What value of promotion probability p gives the best performance?

p = 0.5 balances expected search time and space: lowering p reduces memory but increases expected comparisons per level; raising p increases memory. Pugh's original analysis showed p = 0.25 gives nearly the same expected time with 25% fewer pointers, and Redis uses p = 0.25 for its skip list implementation. The optimal choice depends on the read/write ratio and memory constraints of the application.

How does a skip list compare to a binary search tree for concurrent use?

Skip lists are often preferred in concurrent settings because lock-free and wait-free variants are much simpler to implement than concurrent balanced BSTs. Lock-free skip lists (e.g., the Harris-Fraser-Shavit algorithm) require only atomic compare-and-swap on individual pointers, whereas concurrent AVL or red-black trees must lock or carefully version entire rotation chains. Java's ConcurrentSkipListMap uses this approach.

Is there a deterministic version of a skip list?

Yes. Deterministic skip lists (also called 1–2 skip lists or B-skip lists) enforce exact structural rules rather than relying on randomisation, guaranteeing O(log n) worst-case time. However, they require more complex insertion and deletion logic that is closer to a B-tree than the elegant coin-flip simplicity that makes probabilistic skip lists popular.

What real-world systems use skip lists?

Redis uses a skip list to back its Sorted Set data type, enabling O(log n) rank queries and range scans by score. Apache Cassandra previously used skip lists for its Memtable in-memory store. LevelDB and RocksDB use a variant for their in-memory write buffer. The Java standard library's ConcurrentSkipListMap and ConcurrentSkipListSet are also backed by a skip list.

How are skip lists deleted from?

Deletion locates the node and, for each level where it appears, updates the forward pointer of the predecessor to skip over it. After unlinking, the tower of the deleted node can be freed. If the deletion reduces the effective height of the list (i.e., the top levels become empty), the maximum level counter is decremented. The expected time is O(log n), matching search.

Can a skip list support range queries efficiently?

Yes — this is one of skip lists' practical advantages over hash tables. After a O(log n) search to find the start of the range, the bottom-level linked list provides O(k) traversal to collect all k elements in the range. Redis exploits this for ZRANGEBYSCORE and ZRANGEBYLEX commands, which are central to leaderboard and time-series use cases.