Skip Lists

They're easy to implement and they work

Bruce is the author of Applied Cryptography (John Wiley & Sons) and can be reached at 730 Fair Oaks Ave., Oak Park, IL 60302.

A linked list is a dynamic data structure in which every node points to the node after it. It's easy to implement, but to find a particular node, you have to look at every node before it in the list; see Figure 1(a). If, however, every other node had an additional pointer that skipped to the node two ahead of it, you would only have to look at every other node in the list before you found the node you were looking for, and then maybe one more; see Figure 1(b). If, in addition, every fourth node had yet another pointer to the node four ahead of it, you would only have to look at about every fourth node plus another two before you found the one you wanted; see Figure 1(c). And so on. This would be great for searching--as efficient as a balanced binary tree--but insertion and deletion would be a nightmare. With every insertion and deletion, every node would have to have its pointers rearranged to conform to the skip structure.

Skip Lists

Pugh's skip lists get around this problem by taking a probabilistic approach to the skip pointers; see Figure 1(d). Instead of demanding that every second node have two pointers, every fourth node have three pointers, and so on, the number of pointers in a particular node is determined probabilistically. On the average, half the nodes only have pointers to the node directly in front of them. The other half also have pointers to the node two ahead of them. Half of those nodes also have pointers to the node four ahead of them, half of those nodes also have pointers to the node eight ahead of them, and so on. This means that half the nodes have one pointer, a quarter have two pointers, an eighth have three pointers, and so forth. The addition of randomness means that insertions and deletions won't require modifications to the whole list. Sure, the random dice might degenerate into a normal linked list with lousy performance characteristics, but the odds of that happening are minuscule for a list of reasonable size.

Skip-list algorithms are substantially simpler than balanced tree algorithms. C code for searching, inserting, and deleting nodes in skip lists is given in Listing One (page 88). Pascal code is available electronically; see "Availability," page 3.

The function search() implements the searching algorithm. Searches start at the top level of pointers, those that cover the most ground. Simply search until the node's value is greater than the value you are looking for, and then drop down to the next level of pointers. Eventually you will either find the node or overshoot the value on the bottom pointer level. Figure 2(d) shows an example search path through a skip list.

Skip-list insertion is implemented in the function insert(), which is nothing more than searching and splicing. Depending on the number of pointers the new node has, determined randomly by the function randomlevel(), different pointers will have to be updated. In the example source code, the array update[] contains the list of pointers that must be updated.

Deleting is also easy: Search for the correct node, pull it out of the list, and reconnect a few pointers. The function delete() implements skip-list deletion.

More with Skip Lists

Conclusion

Bibliography

Figure 1: (a) Finding a particular node; (b) looking at every other node in the list; (c) looking at about every fourth node plus another two; (d) taking a probabilistic approach to skip pointers.

Figure 2: Search path through a skip list.

[LISTING ONE]


/* This file contains source code to implement a dictionary using
skip lists and a test driver to test the routines. A couple of comments
about this implementation: The routine randomLevel has been hard-coded to
generate random levels using p=0.25. It can be easily changed. The insertion
routine has been implemented so as to use the dirty hack described in the CACM
paper: if a random level is generated that is more than the current maximum
level, the current maximum level plus one is used instead. Levels start at
zero and go up to MaxLevel (which is equal to (MaxNumberOfLevels-1).
The compile flag allowDuplicates determines whether or not duplicates
are allowed. If defined, duplicates are allowed and act in a FIFO manner.
If not defined, an insertion of a value already in the file updates the
previously existing binding. BitsInRandom is defined to be the number of bits
returned by a call to random(). For most all machines with 32-bit integers,
this is 31 bits as currently set. The routines defined in this file are:
  init: defines NIL and initializes the random bit source
  newList: returns a new, empty list
  freeList(l): deallocates the list l (along with any elements in l)
  randomLevel: Returns a random level
  insert(l,key,value): inserts the binding (key,value) into l. If
    allowDuplicates is undefined, returns true if key was newly
    inserted into the list, false if key already existed
  delete(l,key): deletes any binding of key from the l. Returns
    false if key was not defined.
  search(l,key,&value): Searches for key in l and returns true if found.
    If found, the value associated with key is stored in the
    location pointed to by &value
*/

#define false 0
#define true 1
typedef char boolean;
#define BitsInRandom 31
#define allowDuplicates
#define MaxNumberOfLevels 16
#define MaxLevel (MaxNumberOfLevels-1)
#define newNodeOfLevel(l) (node)malloc(sizeof(struct
nodeStructure)+(l)*sizeof(node *))

typedef int keyType;
typedef int valueType;

#ifdef allowDuplicates
boolean delete(), search();
void insert();
#else
boolean insert(), delete(), search();
#endif

typedef struct nodeStructure *node;
typedef struct nodeStructure{
    keyType key;
    valueType value;
    node forward[1]; /* variable sized array of forward pointers */
    };
typedef struct listStructure{
   int level;     /* Maximum level of the list
            (1 more than the number of levels in the list) */
   struct nodeStructure * header; /* pointer to header */
   } * list;
node NIL;
int randomsLeft;
int randomBits;
init() {
  NIL = newNodeOfLevel(0);
  NIL->key = 0x7fffffff;
  randomBits = random();
  randomsLeft = BitsInRandom/2;
};
list newList() {
  list l;
  int i;
  l = (list)malloc(sizeof(struct listStructure));
  l->level = 0;
  l->header = newNodeOfLevel(MaxNumberOfLevels);
  for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL;
  return(l);
  };
freeList(l)
  list l;
  {
  register node p,q;
  p = l->header;
  do {
    q = p->forward[0];
    free(p);
    p = q; }
    while (p!=NIL);
  free(l);
  };
int randomLevel()
  {register int level = 0;
   register int b;
   do {
    b = randomBits&3;
    if (!b) level++;
    randomBits>>=2;
    if (--randomsLeft == 0) {
    randomBits = random();
    randomsLeft = BitsInRandom/2;
    };
    } while (!b);
    return(level>MaxLevel ? MaxLevel : level);
    };
#ifdef allowDuplicates
void insert(l,key,value)
#else
boolean insert(l,key,value)
#endif

register list l;
register keyType key;
register valueType value;
  {
  register int k;
  node update[MaxNumberOfLevels];
  register node p,q;
  p = l->header;
  k = l->level;
  do {
    while (q = p->forward[k], q->key < key) p = q;
    update[k] = p;
    } while(--k>=0);
#ifndef allowDuplicates
  if (q->key == key) {
    q->value = value;
    return(false);
    };
#endif
    k = randomLevel();
    if (k>l->level) {
    k = ++l->level;
    update[k] = l->header;
    };
    q = newNodeOfLevel(k);
    q->key = key;
    q->value = value;
    do {
    p = update[k];
    q->forward[k] = p->forward[k];
    p->forward[k] = q;
    } while(--k>=0);
#ifndef allowDuplicates
    return(true);
#endif
    }
boolean delete(l,key)
register list l;
register keyType key;
  {
  register int k,m;
  node update[MaxNumberOfLevels];
  register node p,q;
  p = l->header;
  k = m = l->level;
  do {
    while (q = p->forward[k], q->key < key) p = q;
    update[k] = p;
    } while(--k>=0);
  if (q->key == key) {
    for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
      p->forward[k] = q->forward[k];
    free(q);
    while( l->header->forward[m] == NIL && m > 0 )
         m--;
    l->level = m;
    return(true);
    }
    else return(false);
    }
boolean search(l,key,valuePointer)
register list l;
register keyType key;
valueType * valuePointer;
  {
  register int k;
  register node p,q;
  p = l->header;
  k = l->level;
  do while (q = p->forward[k], q->key < key) p = q;
      while (--k>=0);
  if (q->key != key) return(false);
  *valuePointer = q->value;
  return(true);
  };
#define sampleSize 65536
main() {
  list l;
  register int i,k;
  keyType keys[sampleSize];
  valueType v;
  init();
  l= newList();
  for(k=0;k<sampleSize;k++) {
    keys[k]=random();
    insert(l,keys[k],keys[k]);
    };
  for(i=0;i<4;i++) {
    for(k=0;k<sampleSize;k++) {
        if (!search(l,keys[k],&v)) printf("error in search #%d,#%d\n",i,k);
        if (v != keys[k]) printf("search returned wrong value\n");
        };
    for(k=0;k<sampleSize;k++) {
        if (! delete(l,keys[k])) printf("error in delete\n");
        keys[k] = random();
        insert(l,keys[k],keys[k]);
        };
    };
  freeList(l);
  };
End Listing