Simple one-way linked lists might, in general, be built with a data structure something like this:
struct node { char *key; int data; struct node *next; };It might not be readily apparent that the following is exactly equivalent:
struct node { char *key; int data; struct node *next[1]; };Turning things on their heads, you could describe the one-way linked list as a specialized skip list with MAXLEVEL of 1 and PARTITION of 0, where all nodes have pointers at the same level. Therefore searching in the list never leapfrogs over any node. In fact, any skip list where every node has the same level pointer is an expensive approximation to a linear list. Keep this in mind when setting MAXLEVEL. Too small a figure will deform the list and degrade performance significantly.You might be unfortunate enough to build a replica of Figure 2. It also emulates a linear list, even though the distribution of levels throughout the list is the same as in Figure 1. You might intuitively guess that degradation to a linear list is the limit on how bad things could get. Pugh, himself, described worst-case performance as the list where all nodes are level 1. But, consider the case of Figure 3. Clams with legs, indeed.
Nobody would throw out quicksort because it might degrade to the performance of bubblesort. With a little thought, that possibility becomes manageable. The same applies here.
Pugh's analysis is elegant and sophisticated. Using his methods, it is possible to show that even for relatively short skip lists of around 250 or so elements, the chances that a search path will exceed the expected length (about 15-16 comparisons in this case) by a factor of three can be about one in one million. The probability that the path length will actually resemble the list length is calculable but negligible, and grows even more remote as the length of the list grows longer.