Make delicious recipes!

Skip lists

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.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal