A skip list container class in Python

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 FishLicense objects 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 a, b, and 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 order.

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.