Listing 6: Skiplist deletion function

template <class DATA, class KEY>
DATA * Skiplist<DATA,KEY>::remove( const KEY &key )
{
    SLPosition<DATA,KEY> *update[SLMAX_LEVEL];
    SLPosition<DATA,KEY> *cur = &head;
    DATA *to_ret = NULL;
    int i;

    for( i = level-1; i >= 0; i-- )
    {
        while( cur->forward[i] != NULL &&
          cur->forward[i]->key < key )
        {
             cur = cur->forward[i];
        }
        update[i] = cur;
    }
    cur = cur->forward[0];
    if( cur != NULL && cur->key == key )
    {
        to_ret = cur->data;
        for( i = 0; i < level; i++ )
        {
            if( update[i]->forward[i] != cur )
            {
                break;
            }
            else
            {
                update[i]->forward[i] = cur->forward[i];
            }
        }
        delete cur;
        while( level > 0 && head.forward[level] == NULL )
        {
            level--;
        }
    }
    return( to_ret );
}