This routine takes care of repairing all the linked lists
that must contain the newly created `_SkipItem`

. In general,
insertion into a linked lists has this form, where

is
the predecessor,
`P`

is
the successor, and
`S`

is
the new block:
`N`

.link =`N`

`S`

.link =`P`

`N`

So all we need to do is execute this relinking operation
once for each level that contains the new `_SkipItem`

. See
also the diagram of this relinking in Section 3.1, “The skip list data structure”.

pyskip.py

# - - - S k i p L i s t . _ _ i n s e r t R e l i n k - - - def __insertRelink ( self, levels, cutList, newItem ): """Insert the new _SkipItem into all its linked lists. [ (cutList is insertion-cut-list(key-of(child))) and (newItem is a _SkipItem with child=(child) and at least (levels) links) -> self := self with newItem linked into the first (levels) lists, just after the element pointed at by the corresponding element of cutList ] """ #-- 1 -- for i in xrange(levels): #-- 1 loop -- # [ i is an integer in [0,levels) -> # newItem.links[i] := cutList[i].links[i] # cutList[i].links[i] := newItem ] #-- 1.1 -- # [ i is an integer in [0,levels) -> # prevItem := the item pointed at by cutList[i] # succItem := the (i)th link from the item # pointed at by cutList[i] ] prevItem = cutList[i] succItem = prevItem.links[i] #-- 1.2 -- # [ i is an integer in [0,levels) -> # newItem := newItem with its (i)th link # pointing to succItem # prevItem := prevItem with its (i)th link # pointing to newItem ] newItem.links[i] = succItem prevItem.links[i] = newItem