Programming Python, 4th Edition

Chapter 18. Data Structures

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

Data structures are a central theme in most programs, even if Python programmers often don’t need to care. Their apathy is warranted—Python comes “out of the box” with a rich set of built-in and already optimized types that make it easy to deal with structured data: lists, strings, tuples, dictionaries, sets, and the like. For simple systems, these types are usually enough. Dictionaries, for example, subsume many of the classical searching algorithms, and lists replace much of the work you’d do to support collections in lower-level languages. Even so, both are so easy to use 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 or special cases. 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 can 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—to the scripts that use them, they can look and feel just like built-in lists, numbers, and dictionaries.

Although the examples in this chapter illustrate advanced programming and computer science techniques, they also underscore Python’s support for writing reusable software. As object implementations are coded with classes ...