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:
“Indeed, the Englishman’s history of New England commences only when it ceases to be New France.”
—Henry David Thoreau (1817–1862)
“The history of mankind interests us only as it exhibits a steady gain of truth and right, in the incessant conflict which it records between the material and the moral nature.”
—Ralph Waldo Emerson (1803–1882)
“We said that the history of mankind depicts man; in the same way one can maintain that the history of science is science itself.”
—Johann Wolfgang Von Goethe (1749–1832)