Skip Lists in C++

The SkipNode Class

Skip nodes are implemented in SkipNode.h (Listing Three). Each node represents a single element in a skip list, and contains pointers to the node's key, its object, and subsequent skip nodes at or below its height.

Listing Three

#ifndef SKIP_LIST_NODE
#define SKIP_LIST_NODE

struct Product
{
  float cost;
  int   quantity;
  int   location;
};

typedef Product productData;

template <class Key, class Obj>
  class SkipList;

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

    Key* getKey(void);
    Obj* getObj(void);
    int   getHgt(void);
    SkipNode** fwdNodes;

  private:
    int nodeHeight;
    Key* key;
    Obj* obj;
  };

template <class Key, class Obj>
  SkipNode<Key,Obj>::~SkipNode()
  {
    delete key;
    delete obj;
    delete [] fwdNodes;
  }

template <class Key, class Obj>
  SkipNode<Key,Obj>::SkipNode(Key* k, 
    Obj* o, int h)
  {
    nodeHeight = h;
    key = k;
    obj = o;
    fwdNodes =
  new SkipNode<Key,Obj>* [h+1];
    for ( int x = 1; x <= nodeHeight; x++ )
      fwdNodes[x] =
  (SkipNode<Key,Obj>*) NULL;
  }

template <class Key, class Obj>
  SkipNode<Key,Obj>::SkipNode(int h)
  {
    nodeHeight = h;
    key = (Key*) NULL;
    obj = (Obj*) NULL;
    fwdNodes =
  new SkipNode<Key,Obj>* [h+1];
    for ( int x = 1; x <= nodeHeight; x++ )
      fwdNodes[x] =
  (SkipNode<Key,Obj>*) NULL;
  }


template <class Key, class Obj>
  Key* SkipNode<Key,Obj>::getKey(void)
  {
    return key;
  }

template <class Key, class Obj>
  Obj* SkipNode<Key,Obj>::getObj(void)
  {
    return obj;
  }

template <class Key, class Obj>
  int SkipNode<Key,Obj>::getHgt(void)
  {
    return nodeHeight;
  }

#endif //SKIP_LIST_NODE

/* End of File */

A skip node can be instantiated with one of two constructors. The first takes pointers to a key and an object, and an integer indicating the height of the new node. The node's height is kept in a private attribute called nodeHeight, and is reflected in the number of allocated forward node pointers kept in fwdNodes. To make the code easier to read, I've made the fwdNodes attribute public. This also avoids the overhead of a method call when checking whether any of the node's forward pointers actually point to anything.

The second SkipNode constructor takes an integer identifying the node height. When the node is constructed with only a height, the forward pointers are allocated, and the key and object pointers are set to NULL. This constructor is used only for the list's head node. Both constructors set all allocated forward pointers to NULL. These forward pointers will be used heavily by the SkipList class when inserting, searching for, and deleting SkipNode objects.

SkipNode also contains methods you can call to retrieve a key (getKey), an object (getObj), and the node's height (getHgt). Here's a short example in which I instantiate a product node with a key, object, and height, followed by a query for the key and height:

String* key =
    new String("Bill Whitney");
productData* obj  = new productData;
SkipNode* newNode =
    new SkipNode<Key,Obj>(key, obj,
            rndGen->newLevel());

    String* x = newNode->getKey();
    int hgt = newNode->getHgt();

SkipNode's destructor deletes memory allocated for the key, object, and forward pointers.