Expert · Module 24 · Lesson 4 of 4
Skip lists
A skip list keeps keys in one sorted list and gives each node extra forward lanes picked by coin flips at insert time. Search starts on the top lane and drops a lane whenever it runs out of room, giving O(log n) expected time with no rotations; deleting unlinks the node and stops.
By the end you can
- Walk the top-down search and explain why it drops lanes instead of backtracking
- Predict a node's height from the coin-flip rule and read the pyramid an insert sequence builds
- Cost inserts, searches, and deletes, including the flattened worst case
- Recognize skip lists in Redis sorted sets and in standard-library concurrency
Builds on Binary search trees, Randomized algorithms.
01 · A question first
A red-black tree spends most of its code staying balanced. A skip list reaches the same expected O(log n) by flipping coins while inserting and never balancing anything afterward — worst case it flattens into a plain linked list and stays correct, only slower. Redis and the Java standard library both shipped it: how does a coin flip build a search structure, and why can it never produce a wrong answer?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- When balance needs a coin flip
- How a skip list is built
- Inserting: the walk, then the splices
- Searching from the top
- Deletes, and randomness that never lies
- Skip lists in production
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem