What is a Skip List?
Learn what a skip list is, how randomized layered pointers give O(log n) search, and how to answer this data structures interview question.
Expected Interview Answer
A skip list is a probabilistic, layered linked-list structure that keeps elements sorted and adds multiple levels of 'express lane' pointers above the base list, giving expected O(log n) search, insert, and delete without the rebalancing logic a balanced binary search tree requires.
The bottom level is an ordinary sorted linked list containing every element. Each element is also randomly promoted to higher levels with some fixed probability (commonly 1/2), and higher levels contain progressively fewer elements, each with pointers that skip over many base-level nodes. A search starts at the topmost, sparsest level and moves right until the next node would overshoot the target, then drops down a level and repeats, effectively skipping over large stretches of the list at each level. Insertion picks a random height for the new node using repeated coin flips, splices it into every level up to that height, and deletion simply removes it from every level it appears in. Because the structure relies on randomization rather than strict invariants, its logic is dramatically simpler to implement correctly than a red-black tree while achieving the same expected O(log n) bounds, which is why it backs structures like Redis sorted sets.
- Expected O(log n) search, insert, and delete
- Simpler to implement correctly than balanced BSTs
- No complex rotations or rebalancing logic
- Naturally supports ordered range queries
AI Mentor Explanation
A skip list is like a stadium's tiered walkway system: the ground-level concourse touches every seat row in order, but there are also elevated express bridges that skip over many rows at once, and fewer, sparser bridges even higher up. A steward finds a seat by starting on the highest bridge, walking until the next bridge stop would overshoot the seat number, then dropping down one bridge level and repeating, until reaching the ground concourse for the final rows. New seat rows are randomly given a chance to also connect to a bridge level, so the structure stays roughly balanced without any manual rebalancing. This tiered shortcut system is exactly how a skip list gets logarithmic search without needing a strictly balanced tree.
Step-by-Step Explanation
Step 1
Build the base sorted list
Level 0 is an ordinary sorted linked list containing every element.
Step 2
Randomly promote nodes to higher levels
Each node gets a random height via repeated coin flips (e.g. p=1/2 per extra level), forming sparser upper levels.
Step 3
Search top-down
Start at the highest level, move right while the next node is smaller than the target, then drop a level when it would overshoot, repeating to level 0.
Step 4
Insert/delete by splicing at each level
Insert the new node at every level up to its random height; delete by unlinking it from every level it appears in.
What Interviewer Expects
- Explain the multi-level linked-list structure and how upper levels skip over lower ones
- State the expected O(log n) time and why it comes from randomization
- Compare it favorably to balanced BSTs for implementation simplicity
- Name a real use case, e.g. Redis sorted sets
Common Mistakes
- Claiming skip lists guarantee O(log n) worst case (it is expected, probabilistic)
- Confusing a skip list with a simple multi-level array index
- Forgetting that insert/delete must update pointers at every level the node occupies
- Not mentioning the randomized coin-flip height assignment
Best Answer (HR Friendly)
“A skip list is a sorted linked list with extra express lanes stacked on top of it, so you can skip over many elements at once instead of walking one by one. I like it because it gets the same logarithmic speed as a balanced tree but with much simpler code, since it relies on randomness instead of rotation logic to stay balanced.”
Code Example
import random
class Node:
def __init__(self, value, level):
self.value = value
self.forward = [None] * (level + 1)
class SkipList:
MAX_LEVEL = 16
P = 0.5
def __init__(self):
self.head = Node(None, self.MAX_LEVEL)
self.level = 0
def _random_level(self):
lvl = 0
while random.random() < self.P and lvl < self.MAX_LEVEL:
lvl += 1
return lvl
def insert(self, value):
update = [self.head] * (self.MAX_LEVEL + 1)
current = self.head
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].value < value:
current = current.forward[i]
update[i] = current
new_level = self._random_level()
if new_level > self.level:
self.level = new_level
node = Node(value, new_level)
for i in range(new_level + 1):
node.forward[i] = update[i].forward[i]
update[i].forward[i] = node
def search(self, value):
current = self.head
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].value < value:
current = current.forward[i]
current = current.forward[0]
return current is not None and current.value == valueFollow-up Questions
- Why is a skip list's O(log n) bound expected rather than guaranteed?
- How does a skip list compare to a balanced BST like a red-black tree in practice?
- How would you support range queries efficiently using a skip list?
- What promotion probability would you choose and why does it matter?
MCQ Practice
1. What determines how many levels a node appears in within a skip list?
Each node's height is chosen randomly, typically via repeated coin flips with a fixed promotion probability, which is what gives the structure its expected balance.
2. What is the expected time complexity of search in a skip list?
A well-tuned skip list achieves expected O(log n) search by skipping over large portions of the list at higher levels.
3. What is a key implementation advantage of a skip list over a balanced binary search tree?
Skip lists rely on randomization instead of rotations, making insert/delete logic considerably simpler to implement correctly than a balanced BST.
Flash Cards
What is the base level of a skip list? — An ordinary sorted linked list containing every element.
How is a node's height decided in a skip list? — Randomly, via repeated coin flips with a fixed promotion probability (commonly 1/2).
Is a skip list's O(log n) bound guaranteed or expected? — Expected (probabilistic) — it relies on randomization, not strict invariants.
Name a real system that uses skip lists. — Redis sorted sets use a skip list internally for ordered range queries.