An ordered linked structure built from several layers of linked lists, each skipping over more elements than the one below it, giving expected logarithmic-time search and insertion without the rebalancing logic a balanced tree needs.
Facts
Core PrincipleLayers a linked list with several levels of forward pointers chosen at random, so search, insertion and deletion each run in expected logarithmic time without the rebalancing a tree needs. 1 Connections
Sources
1. Wikipedia: Skip List
Wikimedia FoundationHistory section, first sentence
Skip lists were first described in 1989 by William Pugh.
History section, quoting William Pugh
Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.
In Group: Hashing and Probabilistic Structures, Lead
a skip list (or skiplist) is a probabilistic data structure
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.