Data Structures -> Skip Lists¶

Probabilistically balanced ordered dictionary with random-height towers, forward pointers, and one update-array search path for expected-logarithmic search / insert / erase.

Topic slug: data-structures/skip-lists
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 1

Microtopics¶

random-height
forward-pointer-towers
update-array
expected-logarithmic
ordered-dictionary
probabilistic-balancing

Learning Sources¶

Source	Type
Open Data Structures - 4.1 Basic Structure	`Reference`
Pugh - Skip Lists: A Probabilistic Alternative to Balanced Trees	`Reference`

Repo Companion Material¶

Material	Type
Skiplist hot sheet	`quick reference`
Template Library exact starter route	`starter route`
Skiplist Dictionary note	`anchor note`
PBDS / Order Statistics Tree tutorial	`compare point`
Treap / Implicit Treap tutorial	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Skiplist Dictionary Benchmark	`Open Data Structures`	`Medium`	Skiplist, Textbook Breadth	Data-Structure-Heavy; Implementation-Heavy	Random Height; Update Array; Tower Search Path	Random Heights; Expected Logarithmic	A clean breadth benchmark where the whole lesson is probabilistic balancing through forward-pointer towers and one update[] search path, not contest-first rank queries or split/merge.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`SKIPLISTDICTIONARY`	Skiplist Dictionary	`primary`	`medium`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py