**Abstract**

Describes a module in the Python programming language that implements a “skip list”, a data structure for storing and retrieving sorted elements in O(log n) time.

This publication is available in Web form and also as a PDF document.
Please forward any comments to `john@nmt.edu`

.

**Table of Contents**

- 1. Why skip lists?
- 2. An implementation of skip lists in Python
- 3. Internals of
`SkipList`

- 4. The source code
- 4.1. Declarations
- 4.2. Verification functions
- 4.3. The
`_SkipItem`

internal class - 4.4. The
`_SkipListIterator`

class - 4.5. The
`SkipList`

class - 4.6.
`SkipList.__init__()`

- 4.7.
`SkipList.__estimateLevels()`

- 4.8.
`SkipList.insert()`

- 4.9.
`SkipList.__keyOf()`

- 4.10.
`SkipList.__insertCutList()`

- 4.11.
`SkipList.__insertPoint()`

- 4.12.
`SkipList.__insertionPrecedes()`

- 4.13.
`SkipList.__compareItemKey()`

- 4.14.
`SkipList.__insertItem()`

- 4.15.
`SkipList.__pickLevel()`

- 4.16.
`SkipList.__insertRelink()`

- 4.17.
`SkipList.delete()`

- 4.18.
`SkipList.__searchCutList()`

- 4.19.
`SkipList.__searchPoint()`

- 4.20.
`SkipList.__searchPrecedes()`

- 4.21.
`SkipList.match()`

- 4.22.
`SkipList.__searchCutItem`

- 4.23.
`SkipList.find()`

- 4.24.
`SkipList.__len__()`

- 4.25.
`SkipList.__iter__()`

- 4.26.
`SkipList.__contains__()`

- 4.27.
`SkipList.__delitem__()`

- 4.28.
`SkipList.__getitem__()`

- 5.
`skiptest`

: A small test driver - 6. Performance testing

A skip list is a data structure for representing an ordered set of objects so that insertion and retrieval take minimal time.

This ingenious data structure was described in:

Pugh, William. Skip lists: a probabilistic alternative to balanced trees. In: Communications of the ACM, June 1990, 33(6)668-676.

Like balanced tree structures, skip lists support search whose time complexity varies as the log of the number of elements. However, compared to 2-3 trees and other tree-oriented techniques, skip lists require much simpler algorithms and much less storage overhead within the data structure.

There is also a probabilistic element in the construction of a skip list that makes it an interesting example of the use of randomness in algorithms.