History
Skip lists were first described in 1990 by William Pugh. He details how they work in Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676. doi:10.1145/78973.78977.
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.
Read more about this topic: Skip List
Famous quotes containing the word history:
“The history of men’s opposition to women’s emancipation is more interesting perhaps than the story of that emancipation itself.”
—Virginia Woolf (1882–1941)
“Gossip is charming! History is merely gossip. But scandal is gossip made tedious by morality.”
—Oscar Wilde (1854–1900)
“The foregoing generations beheld God and nature face to face; we, through their eyes. Why should not we also enjoy an original relation to the universe? Why should not we have a poetry and philosophy of insight and not of tradition, and a religion by revelation to us, and not the history of theirs?”
—Ralph Waldo Emerson (1803–1882)