Skip List

From InfoAnarchy
Jump to: navigation, search

See also: Programming | Data structure | List

A quickly searchable type of list, that rivals a binary tree in efficiency (O = log(N)). Skip lists are linked lists where items have multiple links to subsequent items, rather than just one link.

Each item in the list is pseudo randomly assigned a "height", which determines number of links for that item. An item's link at a particular height links to the next item with at least that height. Graphically, this looks like:

<pre>

_

4 | | -------------_----> nil

3 | | -----_----> | | --> nil

2 | | --> | | --> | | --> nil

1 | | --> | | --> | | --> nil


height 4

2

3 </pre>

Where the leftmost item has a height of 4, the middle item a height of 2, and the rightmost item a height of 3. The 4th (top) link of the leftmost item points to null, the 3rd link points to the rightmost item, and the 2nd and 1st links both point to the middle item.

Searching

The reason for all the links is specifically to enhance the searching capabilities of the list. There is a "start node" which has a height equal to that of the "tallest" item in the list. Its pointers work exactly the same as any other node's.

The search algorithm is as follows. Start at the highest level of the start node.

  1. Follow the link from the current node at the current height.
  2. Let "this item" be the item that the link points to.
  3. Compare the value of "this item" with the value of the search item.
  4. If "this item" is smaller than the search item, let the current node be "this item" and go to 1.
  5. Else descend down one height on the current node and go to 1.

The search is complete when either the search item matches "this item" (successful search), or the link from the lowest level of the current node points to null (failed search).