Listing 1: Classes SLPosition and SkipList

#include <stdlib.h>
#include <assert.h>
const int SLMAX_LEVEL = 15;

template <class DATA, class KEY>
class Skiplist;   // forward declaration for friend statement

template <class DATA, class KEY>
class SLPosition
{
    DATA *data;
    KEY  key;
    SLPosition<DATA,KEY> **forward;
public:
     SLPosition( int level );
     SLPosition( int level, DATA *cdata, const KEY &ckey );
    ~SLPosition()
    {
         // note that we don't delete data as we can't tell who else
        // might have a pointer to it
        delete [] forward;
    }
    friend class Skiplist<DATA,KEY>;
};

template <class DATA, class KEY>
class Skiplist
{
    SLPosition<DATA,KEY> head;
    int level;  // the number of lists in the skiplist
    int rand_level();
public:
    Skiplist();
    void insert( DATA *data, const KEY &key );
    DATA * remove( const KEY &key );
    DATA * find( const KEY &key );
};
/* End of File */