Complex abstract data types are composed of a collection of data values such as the Python list or dictionary. A collection is a group of values with no implied organization or relationship between the individual values. A complex ADT is implemented using a particular data structure, which is the physical representation of how a collection of data is organized and manipulated. Data structures can be characterized by how they store and organize the individual data elements and what operations are available for accessing and manipulating the data.

There are many common data structures, including arrays, linked lists, stacks, queues, and trees, to name a few. All data structures store a collection of values, but differ in how they organize the individual data items and by what operations can be applied to manage the collection. The choice of a particular data structure depends on the ADT and the problem at hand. Some data structures are better suited to particular problems. For example, the queue structure is perfect for implementing a printer queue, while the B-Tree is the better choice for a database index. No matter which data structure we use to implement an ADT, by keeping the implementation separate from the definition, we can use an abstract data type within our program and later change to a different implementation, as needed, without having to modify our existing code.

A data structure or abstract data type that stores and organizes a collection is known as a container. The individual values of the collection are known as elements of the container and a container with no elements is said to be empty. The organization or arrangement of the elements can vary from one container to the next as can the operations available for accessing the elements. Although, many containers share a common set of operations such as insert, remove, search, and iteratation. While python provides a number of built-in containers, including strings, tuples, lists, dictionaries, and sets, there are many other types of containers. Throughout this book you will be introduced the a variety of common containers used in computer science and learn how those available in python are implemented.

• 2.1 Bags
• 2.2 Selecting a Data Structure
• 2.3 Implementing a Container
• 2.4 Iterators
• 2.5 The Polygon ADT
• 2.6 Maintaining Ordered Data
• 2.7 Maps
• 2.8 Map Operations
• 2.8 Organizing Related Data
• 2.9 Map: Single-List Implementation
• 2.10 Application: Histograms
• Chapter Exercises