Skip List
1. Overview
A. Definition
A Skip List is a probabilistic data structure that stacks multiple layers of sparse express-lane pointers on top of a sorted linked list in a randomized manner, performing search, insertion, and deletion in average O(log n) without the complex rotations and rebalancing of a balanced binary search tree.
The skip list was proposed by William Pugh in 1990 as "A Probabilistic Alternative to Balanced Trees." The basic idea is simple. A sorted singly linked list is easy to implement but slow to search at O(n). If you add a higher-level list that skips entries one at a time, you can narrow the search range by half at each step, and repeating this across several layers achieves an effect similar to binary search using only linked lists. How many levels each node rises to is decided by a coin toss (probability p), so unlike a tree the structure does not skew with insertion order and always stays balanced in the expected-value sense.
The key insight is that it does not force balance but expects it probabilistically. AVL and red-black trees perform rotations and recoloring to restore their invariants on every insertion and deletion, and this logic is tricky to implement and, in particular, induces wide-ranging locks in concurrent environments. A skip list has no rebalancing operation at all, so its code is short, and since each node changes only a few local pointers, its narrow lock scope is favorable to concurrency. Thanks to this property, many production systems such as Redis, LevelDB, and HBase have adopted it as a core index.
B. Background and Necessity
Situations that simultaneously require search, range queries, and order maintenance over sorted data are common in database indexes, in-memory stores, and priority queues. The traditional solution, the balanced binary search tree (B-Tree, red-black tree), guarantees O(log n) even in the worst case, but its rebalancing (rotation, split, merge) logic during insertion and deletion is complex. This complexity is not only a breeding ground for bugs but also increases lock contention in multicore environments as structural changes propagate up to ancestor nodes. In other words, "exact balance" is paid for with "implementation and concurrency cost."
The skip list targets exactly this point. By choosing probabilistic balance instead of perfect balance, it obtains average O(log n) while removing rebalancing code entirely. In particular, since insertion and deletion modify only a small number of adjacent pointers, fine-grained locking or lock-free implementation is far easier than with a tree. Whereas a hash table does not preserve order and is thus unsuitable for range queries, the lower level of a skip list is a fully sorted list, making range scan and sequential access natural. The skip list emerged as a practical choice precisely where the three demands of "implementation simplicity + range queries + concurrency" overlap.
2. Structure and Search Principle
A skip list is a multi-level linked list that places a complete sorted linked list containing all elements at the bottom (level 1) and stacks upper levels containing only a subset of elements on top. Each node has an array of forward pointers equal to its level count, and the leftmost head node holds pointers up to the maximum level, serving as the entry point of the search.
flowchart LR
subgraph L3["Level 3 (sparsest express lane)"]
H3["HEAD"] --> N6_3["30"] --> NIL3["NIL"]
end
subgraph L2["Level 2"]
H2["HEAD"] --> N2_2["10"] --> N6_2["30"] --> N9_2["60"] --> NIL2["NIL"]
end
subgraph L1["Level 1 (contains all elements)"]
H1["HEAD"] --> A["5"] --> B["10"] --> C["20"] --> D["30"] --> E["45"] --> F["60"] --> G["75"] --> NIL1["NIL"]
end
In the figure above, the values 10, 30, and 60 are promoted up to higher levels and act as express lanes. The upper levels include more elements as you go down, forming a pyramid shape, and ideally the structure is designed so that the number of nodes at level k is about p times that of level k−1 (half when p=1/2 as is typical). This "halving at each layer" structure produces the logarithmic depth of binary search.
Search starts from the head of the topmost level, advances to the right as long as it does not pass the target value at the current level, and descends one level at the point where going further would overshoot the target. Repeating this process until reaching level 1 narrows the search space stepwise via the express lanes (skipping), reaching the target in average O(log n).
flowchart TB
S["Search start: HEAD topmost level"] --> C1{"right node key < sought key?"}
C1 -->|"Yes"| R["advance right (use express lane)"]
R --> C1
C1 -->|"No (overshoot)"| C2{"current level > 1?"}
C2 -->|"Yes"| DN["descend one level"]
DN --> C1
C2 -->|"No (reached level 1)"| CHK{"next node key == sought key?"}
CHK -->|"Yes"| FOUND["search succeeds"]
CHK -->|"No"| NOT["search fails (does not exist)"]
For example, suppose we search for the value 45. At level 3 the node after the head is 30, and since 30<45 we advance to 30, but the level-3 successor of 30 is NIL so we cannot go further and descend to level 2. At level 2 the successor of 30 is 60, and since 60>45 we descend to level 1. At level 1 we advance one step from 30→45 and find 45. With a singly linked list we would need five comparisons through 5, 10, 20, 30, 45, but thanks to the express lanes the number of comparisons is reduced.
3. Insertion, Deletion, and the Probabilistic Level Model
The common premise of insertion and deletion is to first perform a search while recording "the node just before descending" at each level in the update[] array. This array becomes the list of neighbors whose pointers will be updated when a new node is inserted or removed.
Insert proceeds in three steps. First, it searches for the target position while recording update[] for each level. Second, it decides the new node's level probabilistically — starting at level 1, it tosses a coin and raises the level by 1 while heads (probability p) comes up, stopping on tails. Third, for as many levels as were decided, it links the forward pointer of update[i] to the new node and links the new node's pointers to the node that update[i] originally pointed to. Thus insertion modifies only as many pointers as the decided level count (a constant in expectation), with no wide-scope operation like rotation.
Delete likewise fills update[] via a search and then finishes by redirecting, at each level in which the target node participates, the preceding node's pointer to the target's successor. Once the target is detached at all levels, the list's current maximum level can be lowered if the upper levels become empty. The pointers touched by deletion are also proportional to the target's level count (a constant in expectation).
As a concrete insertion example, consider inserting the value 50 as a level-3 node. First, searching for the place of 50 from the head, at each of levels 3, 2, and 1 we record "the last node smaller than 50" in update[3], update[2], and update[1]. If the new node's level is decided to be 3 by coin tosses, then across the three layers levels 1, 2, and 3 we change the forward pointer of update[i] to 50 and connect 50's three pointers to the nodes that update[i] originally pointed to. In a tree, rotations might propagate upward to restore balance, but here the fact that it ends by rewiring exactly three pairs of pointers clearly shows the locality of structural change.
The probabilistic level model is the basis of skip-list performance. The probability that a node rises to level k or above is p^(k−1), so when p=1/2, about 1/2 of nodes exist only at level 1, 1/4 at level 2 or above, and 1/8 at level 3 or above. The expected level count (number of pointers) of one node is 1/(1−p), which is only 2 on average when p=1/2. In other words, the extra memory is about one pointer per element on average, so the space complexity is still O(n). The list's expected maximum level is log_(1/p) n, and the expected number of comparisons in a search is analyzed to be on the order of (log_(1/p) n)/p, yielding average O(log n). However, this is an expectation, and with bad luck a single node may draw an excessively high level and shake performance, so implementations impose an upper bound on the maximum level (MaxLevel).
| Operation | Average time complexity | Worst-case time complexity | Note |
|---|---|---|---|
| Search | O(log n) | O(n) | worst case when all nodes are level 1 |
| Insert | O(log n) | O(n) | search + constant pointer modifications |
| Delete | O(log n) | O(n) | search + constant pointer modifications |
| Range query | O(log n + k) | O(n) | k is the number of result elements, sequential scan at lower level |
| Space | O(n) | O(n log n) | expected n/(1−p) pointers |
As the table shows, the worst-case complexity is O(n), but this is a probabilistically extremely rare event in which all nodes happen to draw only level 1, and since levels are set by random numbers independent of input values, the fact that the worst case cannot be forced by malicious input contrasts with a tree's vulnerability to skewed input.
4. Comparison with Balanced Trees and Application Cases
Comparing the skip list with balanced binary search trees (especially red-black trees and AVL) clarifies the selection criteria. Both provide average O(log n), but the difference arises in "how balance is guaranteed," and that difference leads to practical implications. A tree strictly keeps its invariants to guarantee O(log n) even in the worst case, at the cost of complex rebalancing logic and structural changes propagating upward. A skip list leaves balance to probability and gives up the worst-case guarantee, in exchange for simple code and local changes.
| Category | Skip List | Red-Black Tree | B+Tree |
|---|---|---|---|
| Balancing method | probabilistic (random level) | deterministic (color, rotation) | deterministic (split, merge) |
| Average search | O(log n) | O(log n) | O(log n) |
| Worst-case search | O(n) (rare) | O(log n) guaranteed | O(log n) guaranteed |
| Implementation difficulty | low | high | high |
| Concurrency | favorable (local modification) | unfavorable (wide locks) | medium (node locks) |
| Range query | excellent (lower-level scan) | requires in-order traversal | excellent (leaf links) |
| Cache locality | low due to pointer chasing | low | high (block units) |
This comparison reveals practical implications. A disk-based database index must read many keys in a single I/O, so the B+Tree with excellent block-level cache locality is dominant. In contrast, in an in-memory environment the cost of pointer chasing is relatively small and the advantages of implementation simplicity and concurrency grow, giving the skip list competitiveness. In other words, "where you store it (disk vs. memory)" is the key variable that divides the choice.
To grasp it numerically, the power of express lanes becomes clear. Suppose we look up a specific user's rank in a game leaderboard with 10 million (n=10⁷) participants. A single sorted list would need 5 million comparisons on average, but a skip list with p=1/2 has an expected level of only log₂(10⁷)≈23 layers, reaching the target in a few dozen comparisons. A range query for the top 100 by score (ZRANGE) also descends to the entry point in O(log n) and then sequentially scans 100 cells at the lower level, finishing in O(log n + k). Thus, for workloads that simultaneously require "order maintenance + rank/range," the skip list provides a combination that hashes and arrays cannot.
Application cases back up this principle. First, Redis's Sorted Set (ZSET) uses a skip list in parallel with a hash table for score-based sorting, rank queries, and range queries — the hash finds member→score in O(1), and the skip list handles score-ordered ranges and ranks (ZRANGE, ZRANK) in O(log n). Leaderboard rank lookup is a representative use. Second, the MemTable of LevelDB and RocksDB uses a skip list as a structure that collects writes in memory before flushing to disk, because even when many writer threads insert concurrently the lock contention is small and it stays sorted, making it suitable for subsequent sequential flush to an SSTable. Third, Apache HBase's MemStore and the Java standard library's ConcurrentSkipListMap/ConcurrentSkipListSet also provide skip-list-based concurrent sorted data structures for the same reason. They all share the common demand of "order maintenance + high concurrent writes."
5. Advanced: Lock-Free / Concurrent Skip Lists and Design Variants
The decisive reason the skip list is spotlighted in modern systems is its concurrency friendliness. A tree's rebalancing propagates rotations toward the root and must lock a wide range, but a skip list's insertion and deletion change only the pointers of adjacent preceding nodes, enabling fine-grained locking or lock-free implementation. Java's ConcurrentSkipListMap adopts a lock-free algorithm that updates pointers using only CAS (Compare-And-Swap) operations, providing a linearizable sorted map without locks. On deletion, instead of removing a node immediately, it places a logical deletion marker and later physically cleans it up, thereby preserving the consistency of concurrent access. The point that "locality of structural change" directly leads to "scalability of concurrency" is the essential differentiator versus trees.
Design variants are also diverse. Lowering the probability p to 1/4 reduces the average pointers per node to 1/(1−p)=4/3, saving memory but making levels shallower so search comparisons increase somewhat, while setting p to 1/2 makes search faster but uses more space as pointers increase — that is, p is the tuning knob for the time-space trade-off. In environments requiring determinism, a Deterministic Skip List that assigns levels by rule instead of random numbers to guarantee worst-case O(log n) has been proposed, and to raise cache efficiency, unrolled / B-skip-list variants that pack multiple elements into one node are also studied. Recently, as demand for in-memory and real-time analytics grows, the skip list's standing as the standard data structure for the memory tier of log-structured storage (LSM-Tree) has become ever more solid.
6. Considerations and Implications
When applying and evaluating the skip list from a professional engineer's perspective, the following should be considered comprehensively.
A selection strategy based on the storage medium must come first. Since pointer chasing induces cache misses, the B+Tree for disk indexes, where block-unit I/O dominates, and the skip list for in-memory structures, where pointer cost is small and implementation/concurrency advantages are large, are appropriate. Choosing a data structure while ignoring medium characteristics can reverse performance.
One must be cautious in domains where a worst-case complexity guarantee is essential. A skip list is average O(log n) but worst-case O(n). Even if probabilistically rare, in domains that must contract a worst-case latency bound, such as hard real-time and safety-critical systems, it is safer to consider a deterministic balanced tree or a deterministic skip list.
Tune the probability parameter p and MaxLevel to the data scale. p determines the time-space trade-off, and MaxLevel must be set to at least log_(1/p) n for the expected maximum number of elements n to guarantee the express-lane effect. Since a biased random source breaks the theoretical balance, a high-quality random number generator must be used.
The higher the concurrency demand, the greater the relative advantage of the skip list. In in-memory stores, caches, and message queues where concurrent insertions and deletions from many threads are frequent, a lock-free skip list is more favorable in scalability than a tree. Conversely, for a single-threaded, read-dominant workload, a data structure with good cache locality may be better, so the workload characteristics (read/write ratio, concurrency level) should be the selection criteria.
Design range-query and rank operations together. A hash table is strong for membership and point lookups but weak for order and range. For workloads where order is central, such as leaderboards and time-series range lookups, a hybrid design that places a hash and a skip list in parallel like Redis ZSET to handle each operation with the optimal data structure is effective.
In sum, the skip list is a typical example of engineering compromise that replaces perfect balance with probabilistic balance to gain the practical benefits of implementation simplicity, concurrency, and range queries. In the disk domain it yields its place to the B+Tree, but as modern data-infrastructure demands for in-memory, high-concurrency, and order maintenance grow, its value is in fact expanding, and the core of design is to compare it against the tree family along the axes of storage medium, worst-case guarantee needs, concurrency level, and query pattern, and place it in the right spot.
References
- William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, 1990. https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
- Redis Documentation, "Redis sorted sets". https://redis.io/docs/latest/develop/data-types/sorted-sets/
- Java Platform SE, "ConcurrentSkipListMap". https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html
- Google LevelDB source, "skiplist.h". https://github.com/google/leveldb/blob/main/db/skiplist.h
In one line: A skip list stacks express-lane pointers probabilistically on a sorted linked list to achieve average O(log n) search, insertion, and deletion without rebalancing; thanks to its implementation simplicity and concurrency/range-query advantages, it serves as the core index of in-memory high-concurrency systems such as Redis ZSET and LevelDB MemTables.