Skip lists are linked lists that allow you to skip to the correct node. The performance bottleneck inherent in a sequential scan is avoided while insertion and deletion remain relatively efficient. Average search time is O(lg n). Worst-case search time is O(n) but is extremely unlikely. An excellent reference for skip lists is Pugh .
The indexing scheme employed in skip lists is similar in nature to the method used to lookup names in an address book. To lookup a name you index to the tab representing the first character of the desired entry. In Figure 3-8 for example the top-most list represents a simple linked list with no tabs. Adding tabs (middle figure) facilitates the search. In this case level-1 pointers are traversed. Once the correct segment of the list is found level-0 pointers are traversed to find the specific entry.
Figure 3-8: Skip List Construction
The indexing scheme may be extended as shown in the bottom figure where we now have an index to the index. To locate an item level-2 pointers are traversed until the correct segment of the list is identified. Subsequently level-1 and level-0 pointers are traversed.
During insertion the number of pointers required for a new node must be determined. This is easily resolved using a probabilistic technique. A random number generator is used to toss a computer coin. When inserting a new node the coin is tossed to determine if it should be level-1. If you lose the coin is tossed again to determine if the node should be level-2. Another loss and the coin is tossed to determine if the node should be level-3. This process repeats until you win. If only one level (level-0) is implemented the data structure is a simple linked-list with O(n) search time. However if sufficient levels are implemented the skip list may be viewed as a tree with the root at the highest level and search time is O(lg n).
The skip list algorithm has a probabilistic component and thus a probabilistic bounds on the time required to execute. However these bounds are quite tight in normal circumstances. For example to search a list containing 1000 items the probability that search time will be 5 times the average is about 1 in 1 000 000 000 000 000 000.
An ANSI-C implementation for skip lists is included. Typedefs
and comparison operators
should be altered to reflect the data stored in the list. In addition
should be set based on the maximum size of the dataset.
initList is called. The list header is allocated and initialized.
To indicate an empty list
all levels are set to point to the header. Function
allocates a new node
searches for the correct insertion point
and inserts it in the list.
update array maintains pointers to the upper-level nodes
encountered. This information is subsequently used to establish correct links for the newly
inserted node. The
newLevel is determined using a random number generator
the node allocated. The forward links are then established using information from the
delete deletes and frees a node
and is implemented in a similar
find searches the list for a particular value.
Each node in a skip list varies in size depending on a random number generated at time of insertion. Instantiating a class with dynamic size is a bit of a sticky wicket in Visual Basic.