Editing Skip list (section)

== Description ==
[[File:Skip list.svg|thumb|400px|A schematic picture of the skip list data structure. Each box with an arrow represents a pointer and a row is a [[linked list]] giving a sparse subsequence; the numbered boxes (in yellow) at the bottom represent the ordered data sequence. Searching proceeds downwards from the sparsest subsequence at the top until consecutive elements bracketing the search element are found.]]

A skip list is built in layers.  The bottom layer <math>1</math> is an ordinary ordered [[linked list]].  Each higher layer acts as an "express lane" for the lists below, where an element in layer <math>i</math> appears in layer <math>i+1</math> with some fixed probability <math>p</math> (two commonly used values for <math>p</math> are <math>1/2</math> or <math>1/4</math>).  On average, each element appears in <math>1/(1-p)</math> 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 <math>\log_{1/p}n\,</math> (i.e. logarithm base <math>1/p</math> of <math>n</math>) 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 <math>1/p</math>, 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 <math>\tfrac{1}{p}\log_{1/p}n</math> which is <math>O(\log n)\,</math>, when <math>p</math> is a constant. By choosing different values of <math>p</math>, it is possible to trade search costs against storage costs.

=== Implementation details ===
[[File:Skip list add element-en.gif|thumb|400px|Inserting elements into a skip list]]
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.

<math>O(n)</math> 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 <math>O(\log n)</math> 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:

 make all nodes level 1
 j ← 1
 '''while''' the number of nodes at level j > 1 '''do'''
     '''for''' each i'th node at level j '''do'''
         '''if''' i is odd '''and''' i is not the last node at level j
             randomly choose whether to promote it to level j+1
         '''else if''' i is even '''and''' node i-1 was not promoted
             promote it to level j+1
         '''end if'''
     '''repeat'''
     j ← j + 1
 '''repeat'''

Like the derandomized version, quasi-randomization is only done when there is some other reason to be running an <math>O(n)</math> operation (which visits every node).

The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an [[Adversary (online algorithm)|adversarial user]] as the de-randomized one.  This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. (Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.<ref>{{cite conference |first1=Darrell |last1=Bethea |first2=Michael K. |last2=Reiter |title=Data Structures with Unpredictable Timing |url=https://www.cs.unc.edu/~djb/papers/2009-ESORICS.pdf#page=5 |at=pp. 456–471, §4 "Skip Lists" |doi=10.1007/978-3-642-04444-1_28 |conference=ESORICS 2009, 14th European Symposium on Research in Computer Security |location=Saint-Malo, France |date=September 21–23, 2009 |isbn=978-3-642-04443-4}}</ref>) The search performance is still guaranteed to be logarithmic.

It would be tempting to make the following "optimization":  In the part which says "Next, for each ''i''th...", 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.  Instead of <math>O(n \log n)</math> coin flips, there would only be <math>O(\log n)</math> of them.  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<ref>{{cite journal |last1=Sen |first1=Sandeep |title=Some observations on skip lists |journal=Information Processing Letters |date=1991 |volume=39 |issue=4 |pages=173–176 |doi=10.1016/0020-0190(91)90175-H }}</ref>) that the coin-flips used to build the skip list will produce a badly balanced structure.  However, they work well in practice, and the randomized balancing scheme has been argued to be 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. 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.<ref>{{cite thesis |type=Ph.D. thesis | last=Shah | first=Gauri | title=Distributed Data Structures for Peer-to-Peer Systems | year=2003 | url=http://www.cs.yale.edu/homes/shah/pubs/thesis.pdf |publisher=Yale University}}</ref>

=== Indexable skiplist ===
As described above, a skip list is capable of fast <math>O(\log n)</math> insertion and removal of values from a sorted sequence, but it has only slow <math>O(n)</math> 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  <math>O(\log n)</math>.

For every link, also store the width of the link.  The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.

For example, here are the widths of the links in the example at the top of the page:

    1                               10
  o---> o---------------------------------------------------------> o    Top level
    1           3              2                    5
  o---> o---------------> o---------> o---------------------------> o    Level 3
    1        2        1        2              3              2
  o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
    1     1     1     1     1     1     1     1     1     1     1 
  o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level
 Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
       Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it).  Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link.  Descend a level whenever the upcoming width would be too large.

For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level.  Now four more steps are needed but the next width on this level is ten which is too large, so drop one level.  Traverse one link of width 3.  Since another step of width 2 would be too far, drop down to the bottom level.  Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1). 
  
 '''function''' lookupByPositionIndex(i)
     node ← head
     i ← i + 1                           ''# don't count the head as a step''
     '''for''' level '''from''' top '''to''' bottom '''do'''
         '''while''' i ≥ node.width[level] '''do''' ''# if next step is not too far''
             i ← i - node.width[level]  ''# subtract the current width''
             node ← node.next[level]    ''# traverse forward at the current level''
         '''repeat'''
     '''repeat'''
     '''return''' node.value
 '''end function'''

This method of implementing indexing is detailed in ''"A skip list cookbook"'' by William Pugh<ref>
William Pugh.
''"A skip list cookbook"''.
1990.
[https://drum.lib.umd.edu/items/56c44671-3973-46b6-9e52-f71dc95af178 Section 3.4 Linear List Operations ].
</ref>