Skip List
A sorted linked list with extra "express lane" layers built by chance: each node is promoted to the next level up with probability ½. Search drops down a level whenever the next node would overshoot, giving expected O(log n) search, insert, and delete without any tree rotations.
A skip list is a hierarchy of sorted linked lists. The bottom level holds every element; each level above holds a random subset of the level below, decided independently per element by a coin flip (promote with probability ½, again with probability ¼, and so on). Higher levels act as express lanes that skip over many elements at once.
Searching starts at the top-left. At each level, it moves right while the next node's value is still ≤ the target, then drops down a level when it would overshoot. Each drop halves (in expectation) the remaining elements to scan, giving O(log n) expected search — matching a balanced tree's guarantee, without ever rebalancing anything.
Insert performs the same search to find each level's insertion point, picks a random height for the new node the same coin-flip way, and splices it in at every level up to that height. There are no rotations, no colour bits, no parent pointers — just probability doing the balancing work, which is why skip lists are popular wherever a simple, lock-friendly concurrent ordered structure is needed (Redis sorted sets, LevelDB, some LSM-tree memtables).
Operations
| Operation | Complexity |
|---|---|
| search | O(log n) expected |
| insert | O(log n) expected |
| delete | O(log n) expected |
| space | O(n) expected |
Where it's used
Redis sorted sets, LevelDB/RocksDB memtables, lock-free concurrent ordered maps — anywhere a simpler alternative to balanced trees is wanted.