A skip list is a hierarchy of linked lists that connect increasingly distant nodes in a sorted list as shown below:
The advantage of having such a hierarchy of lists is that it allows to jump
to a specified location without visiting all the nodes from the beginning.
If the lists are maintained in such a way that every succeeding level of list connects double the distance connected
by the preceding level, then order of search is comparable to that of a binary tree (logN).
For example, to reach element 7, the yellow highlighted path can be taken:
Skip lists were first described in 1990 by William Pugh who described them as:
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.
Got a thought to share or found a bug in the code? We'd love to hear from you: