Skip list
|
|
A skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations).
Basically, a skip list is an augmentation of an ordered linked list with additional forward links, added in a randomized way, so that a search in the list may quickly skip parts of the list (hence the name). All operations are performed in logarithmic randomized time.
Description
A skip list is built in layers. The bottom layer is an ordinary sorted linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p. On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) appears in O(log1/p n) lists.
1 1-----4---6 1---3-4---6-----9 1-2-3-4-5-6-7-8-9-10
To search for a target element, start with the head element and the top list and scan along each linked list until you reach the last element in it that is less than or equal to the target. The expected number of steps in each linked list is easily seen to be 1/p, by tracing the search path backwards from the target until reaching an element that appears in the next higher list. So the total cost of a search is O(log1/p n / p), which is O(log n) when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.
Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list.
Skip lists do 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) that the coin-flips used to build the skip list will produce a badly unbalanced structure. However, they work well in practice, and the randomized balancing scheme is easier to implement than the deterministic balancing schemes used in balanced binary search trees. 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.
History
Skip lists were invented by William Pugh. He details how they work in Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676. See also citations (http://citeseer.ist.psu.edu/pugh90skip.html) and downloadable documents (ftp://ftp.cs.umd.edu/pub/skipLists/).
To quote the inventor:
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.
External links
- Description (http://nist.gov/dads/HTML/skiplist.html) from the Dictionary of Algorithms and Data Structures