A skip list container class in Python

Before we discuss the main SkipList class, we need a helper object to hold the structural bookkeeping information associated with one element of the skip list.

This helper object doesn't have much to it:

Here, then, is the _SkipItem class:

# - - - - -   c l a s s   _ S k i p I t e m   - - - - -

class _SkipItem:
    """Represents one child element of a SkipList.

      Exports:
        _SkipItem ( child, nLevels ):
          [ (child is a child object) and
            (nLevels is an integer >= 1) ->
              return a new _SkipItem with that child object and
              (nLevels) forward links, each set to None ]
        .child:        [ as passed to constructor, read-only ]
        .links:
          [ if self is an active SkipList element ->
              a list of nLevels elements, read-write, containing
              pointers to a _SkipItem instance
            else ->
              a list of at least 1 whose first element is None ]
    """

# - - -   _ S k i p I t e m . _ _ i n i t _ _   - - -

    def __init__ ( self, child, nLevels ):
        """Constructor for _SkipItem"""
        self.child  =   child
        self.links  =   [None]*nLevels

The final line uses the Python convention that an expression of the form “[x]*n”, where n is an integer, gives you a list containing n copies of x.