Skip Lists - A Probabilistic Alternative to Balanced Trees
March 29, 2025
Skip Lists #
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
Skip lists were first described in 1989 by William Pugh.
To quote the author:
Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.
William Pugh, Concurrent Maintenance of Skip Lists (1989)
PDF Documents #
- A Skip List Cookbook - William Pugh
- Skip Lists: A Probabilistic Alternative to Balanced Trees - William Pugh
- Lecture Notes on Skip Lists - Erik Demaine