An abstract data type (or ADT) is a programmer-defined data type that specifies a set of data values and a collection of well-defined operations that can be performed on those values. Abstract data types are defined independent of their implementation, allowing us to focus on the use of the new data type instead of how it's implemented. This separation is typically enforced by requiring interaction with the abstract data type through an interface or defined set of operations. This is known as information hiding.
By hiding the implementation details and requiring abstract data types to be accessed through an interface, we can work with an abstract view abstract view of the data and focus on what functionality the ADT provides instead of how that functionality is implemented.
Abstract data types can be viewed like black boxes as illustrated in Figure 1.3.1. User programs interact with instances of the ADT by invoking one of the several operations defined by its interface. The implementation of the various operations are hidden inside the black box, the contents of which we do not have to know in order to utilize the ADT.
Figure 1.3.1: Separating the ADT definition from its implementation.
Abstract data types can be simple or complex. A simple ADT is composed
of a single or several individually named data fields such as those used to
represent a date or rational number. The complex ADTs are composed of a collection of data values such as the Python list or dictionary.
There are several advantages of working with abstract data types and focusing on the "what" instead of the "how."
- We can focus on solving the problem at hand instead of getting bogged down in the implementation details.
For example, suppose we need to extract a collection of values from a file on disk and store them for later use in our program. If we focus on the implementation details, then we have to worry about what type of storage structure to use, how it should be used, and whether it is the most efficient choice.
- We can reduce logical errors that can occur from accidental misuse of storage structures and data types by preventing direct access to the implementation.
If we used a list to store the collection of values in the previous example, there is the opportunity to accidentally modify its contents in a part of our code where it was not intended. This type of logical error can be difficult to track down. By using ADTs and requiring access via the interface, we have fewer access points to debug.
- The implementation of the abstract data type can be changed without having to modify the program code that uses the ADT.
There are many times when we discover the initial implementation of an ADT is not the most efficient or we need the data organized in a different way. Suppose our initial approach to the previous problem of storing a collection of values is to simply append new values to the end of the list. What happens if we later decide the items should be arranged in a different order than simply appending them to the end? If we are accessing the list directly, then we will have to modify our code at every point where values are added and make sure they are not rearranged in other places. By requiring access via the interface, we can easily "swap out" the black box with a new implementation with no impact on code segments that use the ADT.
- It's easier to manage and divide larger programs into smaller modules, allowing different members of a team to work on the separate modules.
Large programming projects are commonly developed by teams of programmers in which the workload is divided among the members. By working with ADTs and agreeing on their definition, the team can better ensure the individual modules will work together when all the pieces are combined. Using our previous example, if each member of the team directly accessed the list storing the collection of values, they may inadvertently organize the data in different ways or modify the list in some unexpected way. When the various modules are combined, the results may be unpredictable.
Working with abstract data types, which separate the definition from the implementation, is advantageous in solving problems and writing programs. At some point, however, we must provide a concrete implementation in order for the program to execute. ADTs provided in language libraries, like Python, are implemented by the maintainers of the library. When you define and create your own abstract data types, you must eventually provide an implementation. The choices you make in implementing your ADT can affect its functionality and efficiency.
