Listing 4: Skiplist search function

template <class DATA, class KEY>
DATA * Skiplist<DATA,KEY>::find( const KEY &key )
{
    int i;
    SLPosition<DATA,KEY> *cur = &head;
    for( i = level - 1; i >= 0; i-- )
    {
        while( cur->forward[i] != NULL &&
        cur->forward[i]->key < key )
        {
            cur = cur->forward[i];
        }
    }
    cur = cur->forward[0];
    if( cur != NULL && cur->key == key )
    {
        return( cur->data );
    }
    else
    {
        return (NULL );
    }
}