The Python module pyskip.py is an implementation of Pugh's skip list data structure.
It is necessary to define a few terms before we explore the use and construction of skip lists.
A child object is any object that you want to store in a skip list. Typically all child objects are the same type, but there's nothing preventing you from using more than one child object type in a skip list, if you need to.
By child domain we mean the type (or types) of child objects.
Since skip lists are designed to allow rapid lookup of random child objects, and because child objects are kept in sorted order, we must define how two child objects are to be compared so they can be placed in order.
By key we mean the value used to compare two child objects. Depending on the application, the key may be a value stored inside the child object, or the key may be the child object itself, or a value derived from the child object.
For example, you might have a set of
representing fish licenses, each containing a
unique ten-character license number. You might use
a skip list to hold this set of objects, and
designate the license number as the key. Then you
could rapidly retrieve fish licenses by number.
We use the term key domain to mean the set of possible key values.
If duplicates are allowed, equal members will be kept
in their order of insertion. For example, if you
insert three equal elements
c into a skip list in that
order, if you then iterate over the members of the
list, those three elements will be returned in the same
This property of a container class is called stability. The term comes from sorting theory: a sort that does not perturb the order of elements with equal keys is called a stable sort.