In computer science, a skip list (or skiplist) is a probabilistic data structure that allows

average complexity for insertion within an ordered sequence of

Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right).

Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for.

Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence.

The elements that are skipped over may be chosen probabilistically[2] or deterministically,[3] with the former being more common.

If the current element is equal to the target, it has been found.

If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list.

The expected number of steps in each linked list is at most

, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list.

operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to

(Choose the level of the i'th finite node to be 1 plus the number of times it is possible to repeatedly divide i by 2 before it becomes odd.

Also, i=0 for the negative infinity header as there is the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.)

The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an adversarial user as the de-randomized one.

(Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.

It would be tempting to make the following "optimization": In the part which says "Next, for each ith...", forget about doing a coin-flip for each even-odd pair.

Just flip a coin once to decide whether to promote only the even ones or only the odd ones.

Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one.

This is despite the property that there is a very low probability of guessing that a particular node is at level N for some integer N. A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability[5]) that the coin-flips used to build the skip list will produce a badly balanced structure.

Skip lists are also useful in parallel computing, where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure.

Such parallelism can be especially advantageous for resource discovery in an ad-hoc wireless network because a randomized skip list can be made robust to the loss of any single node.

insertion and removal of values from a sorted sequence, but it has only slow

lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to

The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.

To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link.

Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1).

This method of implementing indexing is detailed in "A skip list cookbook" by William Pugh[7] Skip lists were first described in 1989 by William Pugh.

[8] 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.List of applications and frameworks that use skip lists: Skip lists are also used in distributed applications (where the nodes represent physical computers, and pointers represent network connections) and for implementing highly scalable concurrent priority queues with less lock contention,[17] or even without locking,[18][19][20] as well as lock-free concurrent dictionaries.

[21] There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries.