← Back to the linked lists page
Skip List
A sorted linked list with express lanes: each node is promoted to higher levels by coin flips, giving O(log n) expected search without rotations.
What to know
- Level-i lanes skip ~2^i nodes; search drops down a level when the next node overshoots.
- Simpler to implement lock-free than balanced trees — why Redis chose it.
- Expected O(log n) holds with high probability; worst case is O(n) but vanishingly rare.
In the wild: Redis sorted sets (ZSET), LevelDB/RocksDB memtables, concurrent ordered maps.
Algorithms to reach for
Skip list search/insert/delete
O(log n) expectedSorted-set operations with simple code
Range iteration
O(log n + k)Walk bottom lane between two bounds
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.