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 ); }