A skip list container class in Python |  |
A skip list container class in Python | |
A skip list is a data structure for representing an ordered set of objects so that insertion and retrieval take minimal time.
This ingenious data structure was described in:
Pugh, William. Skip lists: a probabilistic alternative to balanced trees. In: Communications of the ACM, June 1990, 33(6)668-676.
Like balanced tree structures, skip lists support search whose time complexity varies as the log of the number of elements. However, compared to 2-3 trees and other tree-oriented techniques, skip lists require much simpler algorithms and much less storage overhead within the data structure.
There is also a probabilistic element in the construction of a skip list that makes it an interesting example of the useful of randomness in algorithms.