codaBack to Academy
advanced
Skip List
A Skip List is a probabilistic data structure that uses multiple layers of linked lists to allow fast search, insertion, and deletion. Each layer is a subset of the layer below it, and elements are promoted to higher layers randomly. This creates express lanes that enable O(log n) average-case operations, serving as a simpler alternative to balanced trees.
Use Cases
- •In-memory ordered key-value stores (used in Redis)
- •Concurrent data structures where lock-free operations are needed
- •Alternative to balanced BSTs with simpler implementation
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(log n) | O(log n) | O(n) |
| Space | O(n log n) | ||
Visualization
HEADNULL
3
•
6
•
9
•
12
•
15
•
18
∅
Implementation
Output
Click "Run Code" to see output...