Skip List
Randomized express lanes over an ordered linked list
Move right, then descend
The bottom level contains every value in sorted order. Each higher level promotes a random subset, creating increasingly sparse express lanes. Search moves right while the next value is still below the target, then descends one level.
Try it
Search for a value and watch upper express lanes skip over intermediate nodes.
With independent promotion probability, the expected height and expected search, insertion, and deletion time are O(log n). The worst case is O(n), but it is unlikely with a good random source.
Why use one: skip lists offer ordered iteration and logarithmic expected updates without tree rotations. Their pointer-heavy layout trades away some cache locality.