1.3 Abstract Data Types (ADT)

A data type consists of two parts, a set of data with identical properties and the operations that can be performed on the data. Thus we see that integer type consists of values (whole numbers) and operations (add, subtract, multiply, divide etc).

Abstract Data Types (ADT) uses the idea of abstraction and hiding information on implementation details. Applications that use the data type are oblivious to the implementation: they only make use of operations defined or specified abstractly. In this way, the application, which might be millions of lines of code, is completely isolated from the implementation. With an ADT, applications are not concerned with how the task is done but rather with what it can do. With the use of ADT, our programs divide into two pieces or layers.

The application:

The part that uses the ADT

The Implementation:

The part that implements the ADT

These two pieces are completely independent. It should be possible to take the implementation developed for one application and use it for completely different application with no changes.

The formal definition of an ADT is “ a data declaration packaged together with the operations that are meaningful for the data type and it uses the abstraction and information hiding on implementation details.”

In other words, we encapsulate the data and the operations on the data and we hide them from the user. All references to and manipulation of the data in the ADT must be handled through carefully well-defined interfaces to the structure of the ADT.

Model For An Abstract Data Type

The ADT model is shown in Figure 2. The dark shaded area with an irregular outline represents the model. Inside the abstract area are two different aspects of the model: the data structure and the operational functions. Both are entirely contained in the model and are not within the user’s scope. However, the data structure is available to all of the ADT’s operations as needed, and an operation may call on other functions to accomplish its task. In other words, the data structure and the functions are within scope of each other.

ADT Operations

Data are entered, accessed, modified, and deleted through the operational interfaces drawn as rectangles partially in and partially out of the structure. For each operation header there is an algorithm that performs its specific operation. Only the operation name and its parameters are visible to the user, and they provide the only interface to the ADT. Additional operations may be created to satisfy specific requirements. For example, in a file ADT, status calls for end-of-file or input/output error are generally provided.