The insertion of a new child element is depicted above; see Section 3.1, “The skip list data structure”.

pyskip.py

# - - - S k i p L i s t . i n s e r t - - - def insert ( self, child ): """Insert a new child element into the skip list."""

To link in a new child element, once we have decided how
many levels of links it will use, we must insert it into
each of those linked lists. So we define the idea of an
*insertion cut list*: a list of all
the predecessors whose forward links must be updated.

The main complication here is that we must implement stability, that is, objects with equal keys must be ordered by insertion time. For example, if we have five objects all with a key value of 5, the first one must be the first inserted, and the last one must be the last inserted.

So, when computing the insertion cut list, we must find
the point in the child sequence after the last child with
the same key. Refer to Section 4.2, “Verification functions”
for the verification functions used here, and also
see Section 4.9, “`SkipList.__keyOf()`

”.

pyskip.py

#-- 1 -- # [ key := key-of ( child ) ] key = self.__keyOf ( child )

The next step is to build the insertion cut list.
If there any elements with the same key as the new
element, the insertion cut list depends on whether
duplicates are allowed or not. We call the point of
insertion the *cut point*, and the
cut list is the list of links that cross the cut point.

If duplicates aren't allowed, the cut point is positioned
*before* any duplicate elements, so
that when we check for duplicates, we check the new key
against the *successor* of the cut
point.

But if duplicates are allowed, due to the stability
constraint, the cut point should be
*after* any duplicates. See Section 4.8, “`SkipList.insert()`

” for a discussion of stability.

pyskip.py

#-- 2 -- # [ cutList := insertion-cut-list ( key ) ] cutList = self.__insertCutList ( key ) #-- 3 - # [ prevItem := first item from cutList # nextItem := successor at level 0 of first item from # cutList ] prevItem = cutList[0] nextItem = prevItem.links[0]

Now that we have `nextItem`

pointing
just after the cut point, we can check for duplicates
when they're not allowed. See Section 4.13, “`SkipList.__compareItemKey()`

”.

pyskip.py

#-- 4 -- # [ if (not self.allowDups) and # (nextItem is not self.terminator) and # (cmp(key-of(nextItem.child, key)) == 0 ) -> # raise ValueError # else -> I ] if ( ( not self.allowDups ) and ( nextItem is not self.__terminator ) and ( self.__compareItemKey ( nextItem, key ) == 0 ) ): raise ValueError

Having eliminated the only error case, now we can proceed
with the actual insertion of the new element. See
Section 4.14, “`SkipList.__insertItem()`

”.

pyskip.py

#-- 5 -- # [ if cutList is insertion-cut-list ( key ) -> # self := self with a new _SkipItem containing (child) # inserted after the items pointed at by the # the first n elements of cutList, where # n is in [1,self.__maxLevels] ] self.__insertItem ( child, cutList )

The next step maintains the invariant on
`.__nItems`

, that is, we keep track of
the number of items in the list.

pyskip.py

#-- 6 -- self.__nItems = self.__nItems + 1