CHAPTER 18Data 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 clas-
sical 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 soft-
ware. As object implementations are coded with classes and modules, they naturally
become generally useful components that can be used in any program that imports
them. In effect, we will be building libraries of data structure tools, whether we plan
for it or not.
Moreover, though most examples in this chapter are pure Python code (and at least to
linear readers, some may seem relatively simple compared to those of earlier chapters),
they also provide a use case for discussing Python performance issues, and hint at what’s
possible with the subject of Chapter 20—from the most general perspective, new
1359