Muhammad Nadeem Khokhar
Properties of Abstract Data Types
The example of the previous section shows, that with abstraction you create a well-defined entity which can be properly handled. These entities define the data structure of a set of items. For example, each administered employee has a name, date of birth and social number.
The data structure can only be accessed with defined operations. This set of operations is called interface and is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).
Following figure shows an ADT which consists of an abstract data structure and operations. Only the operations are viewable from the outside and define the interface.
An abstract data type (ADT)
Once a new employee is ``created'' the data structure is filled with actual values: You now have an instance of an abstract employee. You can create as many instances of an abstract employee as needed to describe every real employed person.
Let's try to put the characteristics of an ADT in a more formal way:
Definition (Abstract Data Type) An abstract data type (ADT) is characterized by the following properties:
-
It exports a type.
-
It exports a set of operations. This set is called interface.
-
Operations of the interface are the one and only access mechanism to the type's data structure.
-
Axioms and preconditions define the application domain of the type.
Importance of Data Structure Encapsulation
The principle of hiding the used data structure and to only provide a well-defined interface is known as encapsulation. Why is it so important to encapsulate the data structure? To answer this question consider the following mathematical example where we want to define an ADT for complex numbers. For the following it is enough to know that complex numbers consists of two parts: real part and imaginary part. Both parts are represented by real numbers. Complex numbers define several operations: addition, substraction, multiplication or division to name a few. Axioms and preconditions are valid as defined by the mathematical definition of complex numbers. For example, it exists a neutral element for addition.
To represent a complex number it is necessary to define the data structure to be used by its ADT. One can think of at least two possibilities to do this:
-
Both parts are stored in a two-valued array where the first value indicates the real part and the second value the imaginary part of the complex number. If x denotes the real part and y the imaginary part, you could think of accessing them via array subscription: x=c[0] and y=c[1].
-
Both parts are stored in a two-valued record. If the element name of the real part is r and that of the imaginary part is i, x and y can be obtained with: x=c.r and y=c.i.
Point 3 of the ADT definition says that for each access to the data structure there must be an operation defined. The above access examples seem to contradict this requirement. Is this really true?
Have again a look to the performed comparison. Let's stick to the real part. In the first version, x equals c[0]. In the second version, x equals c.r. In both cases x equals ``something''. It is this ``something'' which differs from the actual data structure used. But in both cases the performed operation ``equal'' has the same meaning to declare x to be equal to the real part of the complex number c: both cases archieve the same semantics.
If you think of more complex operations the impact of decoupling data structures from operations becomes even more clear. For example the addition of two complex numbers requires to perform an addition for each part. Consequently, you must access the value of each part which is different for each version. By providing an operation ``add'' you can encapsulate these details from its actual use. In an application context you simply ``add to complex numbers'' regardless of how this functionality is actually archieved.
Once you have created an ADT for complex numbers, say Complex, you can use it similarly to well-known data types such as integers.
Let's summarize this: The separation of data structures and operations and the constraint to only access the data structure via a well-defined interface allows to choose data structures appropriate for the application environment.
