In computer science, a skip list (or skiplist) is a probabilistic data structure that allows O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} average complexity for search as well as O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} average complexity for insertion within an ordered sequence of n {\displaystyle n} elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. 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). 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 or deterministically, with the former being more common.
Description
A skip list is built in layers. The bottom layer 1 {\displaystyle 1} is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i {\displaystyle i} appears in layer i + 1 {\displaystyle i+1} with some fixed probability p {\displaystyle p} (two commonly used values for p {\displaystyle p} are 1 / 2 {\displaystyle 1/2} or 1 / 4 {\displaystyle 1/4} ). On average, each element appears in 1 / ( 1 − p ) {\displaystyle 1/(1-p)} lists, and the tallest element (usually a special head element at the front of the skip list) appears in all the lists. The skip list contains log 1 / p n {\displaystyle \log _{1/p}n\,} (i.e. logarithm base 1 / p {\displaystyle 1/p} of n {\displaystyle n} ) lists. A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. 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 1 / p {\displaystyle 1/p} , 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. Therefore, the total expected cost of a search is 1 p log 1 / p n {\displaystyle {\tfrac {1}{p}}\log _{1/p}n} which is O ( log n ) {\displaystyle {\mathcal {O}}(\log n)\,} , when p {\displaystyle p} is a constant. By choosing different values of p {\displaystyle p} , it is possible to trade search costs against storage costs. For example, the value p = 1 / e {\displaystyle p=1/e} minimizes the average search time of skip lists, whereas the value p = 1 / 2 {\displaystyle p=1/2} simplifies their implementation.
Implementation details
The elements used for a skip list can contain more than one pointer since they can participate in more than one list. 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.
O ( n ) {\displaystyle {\mathcal {O}}(n)} 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 O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} search time. (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.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them. Alternatively, the level structure could be made quasi-random in the following way:
… excerpt ends here. Continue reading the full article.
