Skip Lists: A Probabilistic Alternative to…

Skip Lists asks whether a sorted linked list can search like a balanced tree without rotations or global rebalancing. Read it to see how random node heights create sparse express lanes, how an advance-or-drop search finds a key in expected logarithmic time, and why the result trades a strict worst-case guarantee for simpler local updates and a tunable pointer budget.

Reading focus: How randomly promoted node towers turn one sorted base list into progressively sparser express levels. Why search advances while the next pointer stays below the target, then drops a level when the next jump would overshoot. How promotion probability trades pointer space, constant factors, and run-time variability without creating a worst-case guarantee.

Communications of the ACM 1990. William Pugh. 30 min read, easy difficulty.