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:
“You that would judge me do not judge alone
This book or that, come to this hallowed place
Where my friends’ portraits hang and look thereon;
Ireland’s history in their lineaments trace;
Think where man’s glory most begins and ends
And say my glory was I had such friends.”
—William Butler Yeats (1865–1939)
“In nature, all is useful, all is beautiful. It is therefore beautiful, because it is alive, moving, reproductive; it is therefore useful, because it is symmetrical and fair. Beauty will not come at the call of a legislature, nor will it repeat in England or America its history in Greece. It will come, as always, unannounced, and spring up between the feet of brave and earnest men.”
—Ralph Waldo Emerson (1803–1882)
“The true theater of history is therefore the temperate zone.”
—Georg Wilhelm Friedrich Hegel (1770–1831)