Programming Python, 3rd Edition

20.1. "Roses Are Red, Violets Are Blue; Lists Are Mutable, and So Is Set 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...

20.2. Implementing Stacks Stacks are a common and straightforward data structure, used in a variety of applications: language processing, graph searches, and so on. In short, stacks are a last-in-first-out collection of objectsthe la...

20.3. Implementing Sets Another commonly used data structure is the set, a collection of objects that support operations such as: Intersection Make a new set with all items in common. Union Make a new set with all items in either o...

20.4. Subclassing Built-In Types There is one more twist in the stack and set story, before we move on to some more classical data structures. In recent Python releases, it is also possible to subclass built-in datatypes such as lists a...

20.5. Binary Search Trees Binary trees are a data structure that impose an order on inserted nodes: items less than a node are stored in the left subtree, and items greater than a node are inserted in the right. At the bottom, the subtrees ar...

20.6. Graph Searching Many problems can be represented as a graph, which is a set of states with transitions ("arcs") that lead from one state to another. For example, planning a route for a trip is really a graph search problem in disguis...

20.7. Reversing Sequences Reversal of collections is another typical operation. We can code it either recursively or iteratively in Python, and as functions or class methods. Example 20-21 is a first attempt at two simple reversal fu...

20.8. Permuting Sequences The functions defined in Example 20-23 shuffle sequences in a number of ways: permute constructs a list with all valid permutations of any sequence.subset constructs a list with all valid permutations...

20.9. Sorting Sequences Another staple of many systems is sorting: ordering items in a collection according to some constraint. The script in Example 20-24 defines a simple sort routine in Python, which orders a list of objects on a field. B...

20.10. Data Structures Versus Python Built-Ins Now that I've shown you all of these complicated algorithms, I need to also tell you that at least in some cases, they may not be an optimal approach. Built-in types such as lists and di...

20.11. PyTree: A Generic Tree Object Viewer Up to now, this chapter has been command-line-oriented. To wrap up, I want to show you a program that merges the GUI technology we studied earlier in the book with some of the data structur...