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, which may be used in any program that imports them. In effect, we will be building libraries of data structure classes, whether we plan for it or not.
In addition, although the examples in this chapter are pure Python code, we will also be building a path towards the next part of the book here. From the most general perspective, new Python objects can be implemented in either Python or an integrated language such as C. In particular, pay attention to the stack objects implemented in the first section of this chapter; they will later be reimplemented in C to gauge both the benefits and complexity of C migration.
Introducing Python
Part I: System Interfaces
System Tools
Parallel System Tools
Larger System Examples I
Larger System Examples II
Part II: GUI Programming
Graphical User Interfaces
A Tkinter Tour, Part 1
A Tkinter Tour, Part 2
Larger GUI Examples
Part III: Internet Scripting
Network Scripting
Client-Side Scripting
Server-Side Scripting
Larger Web Site Examples I
Larger Web Site Examples II
Advanced Internet Topics
Part IV: Assorted Topics
Databases and Persistence
Data Structures
Text and Language
Part V: Integration
Extending Python
Embedding Python
VI: The End
Conclusion Python and the Development Cycle