An abstract data type (ADT) is a container whose properties (data and operations) are specified independently of any particular implementation. For example, we can discuss a list of items and the ability to add and remove things in the list without getting into the details of how the items in the list are stored or how the add and remove operations are carried out. The list serves a concrete purpose but can be discussed in an abstract way. Recall that the goal in design is to reduce complexity through abstraction.

To put the concept of an ADT into context, we need to look at how we view data. In computing, we view data from three perspectives: the application level, the logical level, and the implementation level.

The application (or user) level is the view of the data within a particular problem. The logical (or abstract) level is an abstract view of the data values (the domain) and the operations that manipulate them. The implementation level is a specific representation of the structure that holds the data items and the coding of the operations in a programming language. This view sees the properties represented as specific data fields and subprograms. It is concerned with data structures, the implementation of a composite data field in an abstract data type.

The abstract data types that we examine in this chapter are those that history and experience have shown come up again and again in real-world problems. These ADTs are containers in which data items are stored, and each exhibits specific behaviors. They are called containers because their sole purpose is to hold other objects.