A skip list container class in Python

Deletion, like insertion, also uses the idea of a cut list, that is, a list of all the predecessors whose links must be repaired to leave out the deleted item.

However, deletion uses a slightly different concept of the cut list, the search cut list. The only difference comes when the skip list allows duplicate keys. When we're inserting a child with a duplicate key, we want it to go after the other children with that key, to guarantee stability.

For deletion and searching, however, we want the cut list to point before the first of any values whose keys are equal to the key we're deleting or searching for.

# - - -   S k i p L i s t . d e l e t e   - - -

    def delete ( self, key ):
        """Delete the first or only child with a given key value.
        """

First we find the search cut list for the given key. We also set local variables prevItem and nextItem to point to the predecessor and successor of the cut point at level 0. See Section 4.18, “SkipList.__searchCutList()”.

        #-- 1 --
        # [ cutList   :=  search-cut-list ( key )
        #   prevItem  :=  first element of search-cut-list ( key )
        #   nextItem  :=  successor to first element of
        #                 search-cut-list ( key ) ]
        cutList   =  self.__searchCutList ( key )
        prevItem  =  cutList[0]
        nextItem  =  prevItem.links[0]

If the cut point is before the terminator, or the element after the cut point does not have the key value we're looking for, we're done, and we return None to signify failure to delete anything. See Section 4.13, “SkipList.__compareItemKey()”.

        #-- 2 --
        # [ if (nextItem is self.__terminator) or
        #   ( cmp ( key-of ( nextItem's child ), key ) ) > 0 ) ->
        #     return None
        #   else -> I ]
        if ( ( nextItem is self.__terminator ) or
             ( self.__compareItemKey ( nextItem, key ) > 0 ) ):
            return None

We've found the item to be deleted, and nextItem points to it. Relink all the lists that point at that item so that the predecessor at that level in the cut list points at nextItem's successor at that level.

        #-- 3 --
        # [ self  :=  self modified so that for all I in
        #             [0,self.__nLevels), if the skipItem pointed to by
        #             cutList[I] has an (I)th link that points to
        #             nextItem, make that link point where nextItem's
        #             (I)th link points ]
        for i in xrange(self.__nLevels):
            #-- 3 body --
            # [ if the _SkipItem pointed to by cutList[i] has an
            #   (i)th link that points to nextItem ->
            #     that link is made to point where nextItem's (i)th
            #     link points ]
            prevItem  =  cutList[i]
            if  prevItem.links[i] is nextItem:
                prevItem.links[i]  =  nextItem.links[i]

Finally, we must adjust .__nItems to reflect the deletion of one child, and return the deleted child value.

We must also set the level-0 link in the deleted _SkipItem to None, for reasons discussed in Section 3.4, “Classes in this module”.

        #-- 4 --
        self.__nItems      =  self.__nItems - 1
        nextItem.links[0]  =  None
        return nextItem.child