Programming Python, Second Edition

Chapter 17. Data Structures

“Roses Are Red, Violets Are Blue; Lists Are Mutable, and So Is Class Foo”

Data structures are a central theme in most programs, whether you know it or not. It may not always be obvious, because Python provides a set of built-in types that make it easy to deal with structured data: lists, strings, tuples, dictionaries, and the like. For simple systems, these types are usually enough. Technically, dictionaries make many of the classical searching algorithms unnecessary in Python, and lists replace much of the work you’d do to support collections in lower-level languages. Both are so easy to use, though, that you generally never give them a second thought.

But for advanced applications, we may need to add more sophisticated types of our own to handle extra requirements. In this chapter, we’ll explore a handful of advanced data structure implementations in Python: sets, stacks, graphs, and so on. As we’ll see, data structures take the form of new object types in Python, integrated into the language’s type model. That is, objects we code in Python become full-fledged datatypes -- they can look and feel just like built-in lists, numbers, and dictionaries, to the scripts that use them.

Although the examples in this chapter illustrate advanced programming techniques, they also underscore Python’s support for writing reusable software. By coding object implementations with classes, modules, and other Python tools, they naturally become generally useful components, ...