Home → Magazine Archive → June 1990 (Vol. 33, No. 6) → Skip lists: a probabilistic alternative to balanced... → Abstract

Skip lists: a probabilistic alternative to balanced trees

By William Pugh

Communications of the ACM, Vol. 33 No. 6, Pages 668-676
10.1145/78973.78977



Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

The full text of this article is premium content

0 Comments

No entries found