Skip Lists

Probabilistic Express Lanes

1:00

How skip lists achieve expected O(log n) search, insert, and delete on a sorted collection by stacking sparser express lanes and assigning tower heights with random coin flips.

By the end, you can

Explain why a plain sorted linked list requires O(n) search and how express lanes reduce that cost.
Describe the coin-flip rule that assigns tower heights and explain why it produces expected O(log n) structure without rebalancing.
Calculate the expected tower height and expected total pointer count for p = 1/2.
Trace a skip-list search step by step: start at the top, move right while smaller, drop when overshooting.
Describe the insert and delete algorithms and explain why each is expected O(log n).
State the expected and worst-case complexities for search, insert, delete, and space.
Distinguish "expected O(log n)" from a worst-case guarantee, and quantify how unlikely the bad case is.
Compare skip lists to AVL/red-black trees and explain why systems like Redis and RocksDB prefer skip lists.

Up next in Advanced Data Structures