Level k: each element promoted with probability p (0.5)
SEARCH(target):
Start at top-left (highest level, leftmost node)
while not found:
if next.key == target: return found
elif next.key < target: move right
else: move down one level
return not found
Section 2 -- The Idea, Step by Step
Start here. Think about finding a word in a thick paper dictionary. You never read every page. You jump to the thumb-tab for the right letter, land close, then flip page by page the rest of the way. A skip list is just a linked list that grows its own thumb-tabs, so a search can leap most of the way instead of crawling.
Why a plain list is slow. In an ordinary sorted linked list every node points only to the next one, so to reach the 50th item you must step through all 50. A skip list stacks several lists on top of each other. The bottom list, level 0, still holds every element. Above it sit sparse "express lanes" that contain only some of the elements. To search, you start on the top express lane and run right until the next node would overshoot your target; then you drop down one level and keep going. With $n=8$ items and express lanes that each keep about half, the work falls from up to 8 hops to roughly $\log_2 8 = 3$ hops.
Make it precise. Which elements get promoted to the lane above is decided by a coin flip. An element climbs one more level with probability $p$ (usually $p=0.5$), reaches the next level with probability $p^2$, and so on. So the expected count of elements at level $k$ is $np^k$, the tower of lanes tops out near level $\log_{1/p} n$, and search, insert, and delete each run in $O(\log n)$ expected time. The total number of nodes is $\sum_{k\ge 0} np^k = \dfrac{n}{1-p} = 2n$ when $p=0.5$, so all the express lanes together only double the memory. The randomness is the whole point: there are no rotations or rebalancing like in a balanced tree, just coin flips, which is exactly why concurrent skip lists are so much easier to get right.
Try this in the sim above. This page's panel is a generic trace stepper rather than a live skip-list view, but it still makes the cost story visible. Drag the $n$ slider up and watch the Step counter in the stat panel climb: that rising amount of work as $n$ grows is precisely what a skip list's express lanes are built to flatten from linear down toward $\log n$. Press the >| button to advance one comparison at a time and watch the Comparisons counter, then hit Reset to reshuffle and compare a new run.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity
V,E
Vertices and Edges
W
Weight or capacity
Step 1 -- Randomized Structure. Skip list is a randomized alternative to balanced trees. Each element exists at level 0. Each element is independently promoted to level k+1 with probability p (typically 0.5). Expected height of skip list: O(log_{1/p} n).
Step 2 -- Search O(log n) Expected. Start at top-left. Move right if next key < target. Drop down one level if next key >= target (overshot). Reach level 0 -- either found or not in list. Expected O(log n) pointer traversals.
Step 3 -- Insert O(log n) Expected. Search for insertion position. At each level where the element will be promoted, update forward pointers. Coin flip determines how many levels. Expected O(log n) levels per element.
Step 4 -- Delete O(log n) Expected. Search from top, record predecessors at each level. Update forward pointers to bypass deleted node. Expected O(log n).
Step 5 -- Space O(n) Expected. Expected number of nodes: sum over levels k of n*p^k = n * (1/(1-p)). For p=0.5: expected 2n total nodes across all levels. O(n) expected space.
Step 6 -- Concurrent-Friendly Property. Lock-free and lock-based concurrent skip lists are simpler to implement correctly than concurrent balanced trees (which need complex rotation protocols). Java's ConcurrentSkipListMap uses skip lists for this reason.
Section 4 -- FAQ
Why use a skip list instead of a balanced tree? concept+
Skip list: simpler implementation, naturally supports concurrent access (compare-and-swap for lock-free version), similar O(log n) expected performance. Balanced trees (AVL, RB): deterministic O(log n) worst case, more complex rotations, harder to make concurrent. Redis uses skip lists for sorted sets.
What happens if coin flips are adversarial? concept+
Skip list uses randomization for expected O(log n). With adversarial coin flips: could degrade to O(n). In practice, random generator is internal -- adversary cannot influence coin flips. Unlike deterministic structures, skip list's O(log n) is EXPECTED, not worst-case.
Where are skip lists used in real systems? applied+
Redis sorted sets (ZSET). LevelDB and RocksDB use skip lists for in-memory memtable. Java ConcurrentSkipListMap and ConcurrentSkipListSet. Apache Cassandra memtable. Useful when concurrent sorted access is needed without complex locking.
What is the expected height of a skip list? complex+
Each element reaches level k with probability p^k. Total elements at level k: np^k. Last level with at least 1 element: k = log_{1/p}(n). Expected height = O(log_{1/p}(n)). For p=0.5: O(log_2 n) = O(log n). Choosing p affects space-time tradeoff.
Why is skip list O(log n) and not O(log n) worst case? nonobv+
The randomized levels give O(log n) EXPECTED. The analysis shows that with high probability (probability >= 1 - 1/n), the height is O(log n). Worst case is technically O(n) (all elements at level 0 only -- all coin flips tails). But this happens with probability (1/2)^n -- negligible.
What is a deterministic skip list? deep+
1-2-3 skip lists use deterministic promotion rules (based on rank in the list, not random). These give O(log n) worst-case but are more complex to implement. Alternatively: a B-tree IS a deterministic skip list. The connection between skip lists, treaps, and B-trees shows they are all expressions of the same underlying structure.
Section 5 -- Misconceptions
Conceptual
X Skip list is O(log n) worst case.
O O(log n) EXPECTED. Worst case is O(n) (adversarial or very unlucky coin flips). For guaranteed O(log n), use AVL or Red-Black tree.
X Skip list uses more memory than a sorted array.
O Skip list: O(n) expected pointers (about 2n for p=0.5). Sorted array: O(n). Skip list has higher constant but supports O(log n) insert/delete vs O(n) for sorted array.
X Higher promotion probability p gives better performance.
O Higher p: more levels, more pointers per node (more memory), slightly faster search (fewer hops per level). Lower p: fewer levels, less memory, slightly more hops. p=0.5 is typically optimal. p=0.25 reduces space with slightly worse performance.
Implementation
X Forgetting to set max level cap.
O Without cap, a single element could theoretically have infinite levels (infinite consecutive heads). Cap at ceil(log_{1/p}(MAXN)) levels. Typical: maxLevel = 16 or 32.
X Using a single sentinel node at head.
O Must set head.key = -infinity and tail.key = +infinity as sentinels. Without sentinels, boundary conditions (search past end, insert at beginning) require special cases.
X Not updating ALL level pointers during insert/delete.
O Must update forward pointers at EVERY level where the node exists (up to its random height). Missing upper-level pointers makes those levels incorrect.