Skip Lists in C++

Creating a SkipList Object

While SkipNode objects represent the individual nodes in a skip list, the SkipList class manages their insertion, deletion, and retrieval (see Listing Four, SkipList.h). SkipList has one constructor, which takes three values: the probability and maximum node height (which are used to instantiate RandomHeight), and a parameter representing the maximum key value. The maximum key value is stored in the tail of the skip list, preventing the search algorithm from attempting to look beyond that point. This sentinel operation could be implemented differently; for example, by comparing a SkipNode's forward pointer to the address of the tail node.

Listing Four

#ifndef SKIP_LIST
#define SKIP_LIST
#include <iostream.h>
#include <fstream.h>
#include "SkipNode.h"
#include "RandomHeight.h"

template <class Key, class Obj>
  class SkipList
  {
  public:
    SkipList(float,int,Key*);
    ~SkipList();

    bool insert(Key*, Obj*);
    bool remove(Key*);
    Obj* retrieve(Key*);
    void dump(ofstream&);

  private:
    SkipNode<Key,Obj>* head;
    SkipNode<Key,Obj>* tail;
    float probability;
    int maxHeight;
    int curHeight;
    RandomHeight* randGen;
  };

template <class Key, class Obj>
  SkipList<Key,Obj>::SkipList(float p, int m, Key* k)
  {
    curHeight = 1;
    maxHeight = m;
    probability = p;
    randGen = new RandomHeight(m,p);

    // Create head and tail and attach them
    head = new SkipNode<Key,Obj>(maxHeight);
    tail = new SkipNode<Key,Obj>(k, (Obj*) NULL, maxHeight);
    for ( int x = 1; x <= maxHeight; x++ )
        head->fwdNodes[x] = tail;
  }

template <class Key, class Obj>
  SkipList<Key,Obj>::~SkipList()
  {
    // Walk 0 level nodes and delete all
    SkipNode<Key,Obj>* tmp;
    SkipNode<Key,Obj>* nxt;
    tmp = head;
    while ( tmp )
    {
      nxt = tmp->fwdNodes[1];
      delete tmp;
      tmp = nxt;
    }
  }

template <class Key, class Obj>
  bool SkipList<Key,Obj>::insert(Key* k, Obj* o)
  {
    int lvl = 0, h = 0;
    SkipNode<Key,Obj>** updateVec =
      new SkipNode<Key,Obj>* [maxHeight+1];
    SkipNode<Key,Obj>* tmp = head;
    Key* cmpKey;

    // Figure out where new node goes
    for ( h = curHeight; h >= 1; h-- )
    {
      cmpKey = tmp->fwdNodes[h]->getKey();
      while ( *cmpKey < *k )
      {
        tmp = tmp->fwdNodes[h];
        cmpKey = tmp->fwdNodes[h]->getKey();
      }
      updateVec[h] = tmp;
    }
    tmp = tmp->fwdNodes[1];
    cmpKey = tmp->getKey();

    // If dup, return false
    if ( *cmpKey == *k )
    {
      return false;
    }
    else
    {
      // Perform an insert
      lvl = randGen->newLevel();
      if ( lvl > curHeight )
      {
        for ( int i = curHeight + 1; i <= lvl; i++ )
          updateVec[i] = head;
        curHeight = lvl;
      }
      // Insert new element
      tmp = new SkipNode<Key,Obj>(k, o, lvl);
      for ( int i = 1; i <= lvl; i++ )
      {
        tmp->fwdNodes[i] = updateVec[i]->fwdNodes[i];
        updateVec[i]->fwdNodes[i] = tmp;
      }
    }
    return true;
  }


template <class Key, class Obj>
  bool SkipList<Key,Obj>::remove(Key* k)
  {
    SkipNode<Key,Obj>** updateVec =
      new SkipNode<Key,Obj>* [maxHeight+1];
    SkipNode<Key,Obj>* tmp = head;
    Key* cmpKey;

     // Find the node we need to delete
    for ( int h = curHeight; h > 0; h-- )
    {
      cmpKey = tmp->fwdNodes[h]->getKey();
      while ( *cmpKey < *k )
      {
        tmp = tmp->fwdNodes[h];
        cmpKey = tmp->fwdNodes[h]->getKey();
      }
      updateVec[h] = tmp;
    }
    tmp = tmp->fwdNodes[1];
    cmpKey = tmp->getKey();

    if ( *cmpKey == *k )
    {
      for ( int i = 1; i <= curHeight; i++ )
      {
        if ( updateVec[i]->fwdNodes[i] != tmp ) 
          break;
        updateVec[i]->fwdNodes[i] = tmp->fwdNodes[i];
      }
      delete tmp;
      while ( ( curHeight > 1 ) &&
            ( ( head->fwdNodes[curHeight]->getKey()
                == tail->getKey() ) ) )
        curHeight--;
      return true;
    }
    else
    {
      return false;
    }
  }

template <class Key, class Obj>
  Obj* SkipList<Key,Obj>::retrieve(Key* k)
  {
    int h = 0;
    SkipNode<Key,Obj>** updateVec =
      new SkipNode<Key,Obj>* [maxHeight+1];
    SkipNode<Key,Obj>* tmp = head;
    Key* cmpKey;

    // Find the key and return the node
    for ( h = curHeight; h >= 1; h-- )
    {
      cmpKey = tmp->fwdNodes[h]->getKey();
      while ( *cmpKey < *k )
      {
        tmp = tmp->fwdNodes[h];
        cmpKey = tmp->fwdNodes[h]->getKey();
      }
      updateVec[h] = tmp;
    }
    tmp = tmp->fwdNodes[1];
    cmpKey = tmp->getKey();
    if ( *cmpKey == *k )
      return tmp->getObj();
    else
      return (SkipNode<Key,Obj>*) NULL;
  }

template <class Key, class Obj>
  void SkipList<Key,Obj>::dump(ofstream& of)
  {
    SkipNode<Key,Obj>* tmp;

    tmp = head;
    while ( tmp != tail )
    {
      if ( tmp == head )
        of << "There's the head node!" << endl << flush;
      else
        // Your key class must support "<<"
        of << "Next node holds key: " << tmp->getKey() << endl
           << flush;
      tmp = tmp->fwdNodes[1];
    }
    of << "There's the tail node!" << endl << flush;
  }

#endif //SKIP_LIST

/* End of File */

When a SkipList is instantiated, it creates an instance of RandomHeight, and then creates the skip list's head and tail nodes. The constructor sets the pointers for key and object in the head node to NULL, and sets all forward pointers in the head node to the address of the tail node. The tail node's forward pointers and object pointer are set to NULL. The key pointer will point to the maximum key value provided in the SkipList constructor. After construction the skip list appears as shown in Figure 2, with a maximum height of 4 and a current height of 0.

Figure 2: A newly constructed skip list

The following snippet shows how to instantiate the SkipList object in your code. The maximum key value shown here is based on the example in Figure 1, and reflects the highest possible product identifier. In reality, this value will depend on your application.

String* maxKey = new String("Z9999");
SkipList<String, productData>
    *aSkipList =
        new SkipList<String,
                productData>
            ((float).5, 4, maxKey);