Build a Skip List

randomized express lanes

Challenge 4 of Indexes & StructuresAdvanced~55 min

Get O(log n) search, insert, and delete on an ordered set using stacked linked lists and a coin flip instead of tree rotations. Build randomized levels, express-lane insertion that keeps the list sorted, fast search, and deletion. The structure behind Redis sorted sets and LevelDB memtables.

4 steps

1. 1Randomized Levels
2. 2Sorted Insertion
3. 3Search
4. 4Deletion