skiplist

Skip lists were first described in 1989 by William Pugh.

It is a probabilistic data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements.

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)

References

• https://en.wikipedia.org/wiki/Skip_list
• Papadakis, Thomas (1993). Skip Lists and Probabilistic Analysis of Algorithms. University of Waterloo.
• William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .
• Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.