A skip list container class in Python

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 tcc-doc@nmt.edu.

Table of Contents

1. Why skip lists?

2. An implementation of skip lists in Python

2.1. Definitions
2.2. Creating a Python skip list
2.3. Methods and attributes of the SkipList object

3. Internals of SkipList

3.1. The skip list data structure
3.2. Skip list algorithms
3.3. Iterators: toward a more Pythonic class
3.4. Classes in this module

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__()

1. Why skip lists?

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 useful of randomness in algorithms.