Skip List
Layered linked lists where higher levels skip ahead, giving expected O(log n) search.
Skip List: Search skips along the express lanes
Level 3 at the head: the next key on this lane is nothing, the end of the lane. It is not below 44, so drop to level 2 and keep looking from here.
Cost
- Search
- O(log n) expected
- Insert
- O(log n) expected
- Delete
- O(log n) expected
- Space
- O(n) expected
Randomized level assignment. Bounds are expected not worst case.