A skip list container class in Python |  |
A skip list container class in Python | |
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.
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.
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”.
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.
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.
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.