Next / Previous / Contents / TCC Help System / NM Tech homepage

3. Internals of SkipList

Before examining the actual code, let's discuss the data structure and some other implementation considerations.

3.1. The skip list data structure

To implement the functionality of this ordered set container, we could just keep all the objects in an ordinary linked list. However, searching a linked list has a time complexity that varies linearly with the number of elements. To be competitive with balanced tree approaches such as 2-3 trees, we need to be able to search in log time.

Pugh's idea was to set up a number of linked lists, numbered starting at 0, such that:

  • Every object is in list 0, ordered from lowest to highest key.

  • List i visits a subset of the objects in list (i-1), but still in order by key.

In practice, when each new element is inserted, it is always added to list 0, and it is also added to a random number of higher-numbered lists, where each higher level is less likely.

With this structure, the higher-numbered linked lists are more and more sparse. Therefore, the algorithm for searching a skip list is:

  1. Search the highest-numbered list until you find either the desired item or one that is beyond the desired item.

  2. If the desired item is not in the highest-numbered list, back up to the preceding item, move down one list, and search that list.

  3. Repeat until either the desired item is found or it is not found in list 0.

So the search begins by “skipping” rapidly down the list using the highest-level, sparse linked list, then zeroes in on the desired item by moving down to denser and denser linked lists.

Here is an example of a small skip list containing some short character strings in lexical order. This list has a maximum of 8 levels:

This picture shows five strings, "a", "c", two copies of "d", and "f".

The field names refer to members of the SkipList object. The item labeled .__heads contains the heads of all the lists. Each list terminates with a pointer to the item labeled .__terminator. Field .__maxLevels is the maximum number of linked lists (8 in the figure), and .__nLevels is the number of lists that are currently in use.