Data Structures
Skip List
Difficulty: Intermediate
Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a ConcurrentSkipListMap in its standard library because lock-free skip lists are dramatically easier to implement than lock-free...
Skip List
Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a ConcurrentSkipListMap in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a Skip List: a sorted linked list with a few extra express-lane pointers that turn O(n) search into O(log n) expected.
This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution.
In Linked Lists (Singly), a search was O(n) because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on.
Next, Balanced BST (AVL / Red-Black) is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.
Prerequisites:
Linked Lists (Singly)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain why a sorted linked list has O(n) search and how express lanes achieve O(log n) expected search time.
Describe the skip list structure: multiple levels of sorted linked lists with probabilistic promotion.
Implement search, insert, and delete operations on a skip list in both JavaScript and Python.
Analyze the expected O(log n) time complexity using the coin-flip promotion argument.
Compare skip lists with balanced BSTs (AVL, Red-Black) in terms of simplicity, performance, and concurrency.
Identify real-world applications of skip lists including Redis sorted sets and LevelDB.
Why This Matters
01
A sorted linked list supports O(n) search at best. Skip lists solve this by adding 'express lane' levels that let you skip ahead, achieving O(log n) expected time for search, insert, and delete -- all without complex tree rotations or rebalancing.
02
Skip lists are used in production systems you interact with daily: Redis uses skip lists for its sorted set (ZSET) data type, LevelDB and RocksDB use them for in-memory memtables, and Java's ConcurrentSkipListMap provides a lock-free concurrent sorted map.
03
Understanding skip lists deepens your grasp of randomized algorithms and probabilistic analysis. The coin-flip level promotion is an elegant example of how randomness can replace deterministic balancing while maintaining expected O(log n) performance.
Key Terms
7 terms you'll encounter in this lesson
Skip List
A probabilistic data structure consisting of multiple layers of sorted linked lists, where higher levels act as 'express lanes' that skip over elements, enabling O(log n) expected search, insert, and delete.
Level (Layer)
One horizontal sorted linked list within the skip list. Level 0 (the bottom) contains all elements. Higher levels contain progressively fewer elements, chosen by random promotion.
Promotion (Coin Flip)
The randomized process of deciding whether a newly inserted node should appear on the next higher level. Typically a fair coin flip (probability 0.5) is used, so on average half the nodes at each level are promoted.
Express Lane
An analogy for higher levels of a skip list. Just as a subway express train skips local stops, higher levels skip over elements, letting search traverse fewer nodes.
Sentinel (Header Node)
A special node at the far left of every level with value negative infinity. It serves as the starting point for all traversals and simplifies edge-case handling.
Update Array
An array used during insert and delete that records the last node visited at each level before the target position. These are the nodes whose forward pointers must be updated.
Max Level
The upper bound on the number of levels in the skip list. Commonly set to log2(n) or a fixed constant (e.g., 16 or 32). Prevents degenerate cases from consuming too much memory.
Heads Up
Common misconceptions to watch out for
"Skip lists are always O(log n)"
Skip lists provide O(log n) *expected* time, not worst-case. In the worst case (extremely unlucky coin flips), performance degrades to O(n). However, the probability of this happening is astronomically small -- similar to how quicksort is O(n^2) worst case but practically always O(n log n).
"Higher levels are copies of lower levels"
Higher levels contain a *subset* of the elements from lower levels, not copies. A single node exists in the skip list and has forward pointers at multiple levels. Think of it as a tower: the node at level 0 can have additional pointers at levels 1, 2, etc.
"Skip lists use more memory than balanced BSTs"
On average, a skip list with promotion probability p = 0.5 uses 2n total pointers (each node has on average 1/(1-p) = 2 forward pointers). A red-black tree node uses 3 pointers (left, right, parent) plus a color bit. So skip lists are comparable in memory usage.
"Balanced BSTs are always better in practice"
Skip lists have practical advantages: they are simpler to implement correctly, their operations are naturally suited for concurrent access (lock-free insertions), and they have good cache locality in the bottom level. Redis, LevelDB, and Java's ConcurrentSkipListMap all chose skip lists over balanced BSTs.