Next / Previous / Contents / Shipman's homepage

2. An implementation of skip lists in Python

The Python module is an implementation of Pugh's skip list data structure.

2.1. Definitions

It is necessary to define a few terms before we explore the use and construction of skip lists.

2.1.1. The child domain

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.

2.1.2. The key domain

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.

2.1.3. Stability

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.