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

3.2. Skip list algorithms

Now that we've seen the static structure of a skip list, let's move on to the basic operations: inserting a new child, finding a child, and deleting a child.

3.2.1. The insertion algorithm

Here is a figure showing the insertion of a new element into a skip list.

The dashed lines show links that need to be updated.

3.2.1.1. The insertion cut list

In the figure above, note the structure labeled “insertion-cut-list” is a list of pointers to the predecessors of the new element at each level. The first element of this list points to the item preceding the insertion in the level-0 list, which visits every element of the list. The second element in the insertion cut list points to the predecessor in the level-1 list, and so on.

This insertion cut list shows the position of a child element relative to each of the stacked linked lists. It tells us which links have to be repaired to include the newly inserted child.

We call it the insertion cut list to distinguish it from the search cut list; for the reasons behind this distinction, see Section 3.2.2, “The search algorithm”.

3.2.1.2. Picking a level count

When we insert a new element, how many of the stacked linked lists should contain the new element? Pugh recommended using a random process based on a probability value p, where the number of levels used for each new element is given by this table:

1 1-p
2 p(1-p)
3 p2(1-p)
......
n pn-1(1-p)

For example, for p=0.25, an element has a 3 in 4 probability of being linked into only level 0, a 3/16 probability of being in levels 0 and 1, a 3/64 probability of being in levels 0 through 2, and so forth.

The algorithm for deciding the number of levels is straightforward. For p=0.25, it's like throwing a 4-sided die. If it comes up 1, 2, or 3, use one level. If it comes up 4, roll again. If the second roll comes up 1, 2, or 3, use two levels. If it comes up 4, roll again, and so forth.

We will incorporate the “dirty hack” described in Pugh's article, limiting the growth in the total number of levels in use to one per insertion. This prevents the pathological case where a series of “bad rolls” might create many new levels at once for only a single insertion. Otherwise we might get silly behavior like a 6-level skip list to store ten elements.

3.2.2. The search algorithm

The process of searching for a given key value is nearly identical to the process of building the insert cut list (see Section 3.2.1.1, “The insertion cut list”).

The only difference between the search cut list and the insert cut list is in the case where we have elements with duplicate keys (that is, when the constructor was called with allowDups=1).

If we're inserting a new child whose key is a duplicate of a key already in the list, we want the new child to go after any duplicates. This is required for stability; see Section 2.1.3, “Stability”.

However, if we're searching for an element (or deleting an element—see Section 3.2.3, “Deleting a child”), we want to position before any duplicate elements.

3.2.3. Deleting a child

Deletion of a child starts by finding the search cut list. For a discussion of the search cut list, see Section 3.2.2, “The search algorithm”.

The search cut list contains all the predecessors whose links need to be updated when a child element is deleted. To delete a child, we work through the search cut list, repairing each predecessor link to point to the successor of the deleted child.