Abstract Data Types

From

← Concept of an Element (Node)

↑ Contents: CS2

End

An abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations. The definition can be mathematical, or it can be programmed as an interface. A first class ADT supports the creation of multiple instances of the ADT, and the interface normally provides a constructor, which returns an abstract handle to new data, and several operations, which are functions accepting the abstract handle as an argument.[1]

The main contribution of the abstract data type theory (and its evolution, the design by contract) is that it (1) formalizes a definition of type (which was only intuitively hinted on procedural programming) (2) on the basis of the information hiding principle and (3) in a way that such formalization can be explicitly represented in programming language notations and semantics. This important advance in computer science theory (motivated by software engineering challenges in procedural programming) led to the emergence of languages and methodological principles of object-oriented programming.

Separation of interface and implementation

When realized in a computer program, the ADT is represented by an interface, which shields a corresponding implementation. Users of an ADT are concerned with the interface, but not the implementation, as the implementation can change in the future. (This supports the principle of information hiding, or protecting the program from design decisions that are subject to change.)

The strength of an ADT is that the implementation is hidden from the user. Only the interface is published. This means that the ADT can be implemented in various ways, but as long as it adheres to the interface, user programs are unaffected.

There is a distinction, although sometimes subtle, between the abstract data type and the data structure used in its implementation. For example, a List ADT can be represented using an array-based implementation or a linked-list implementation. A List is an abstract data type with well-defined operations (add element, remove element, etc.) while a linked-list is a pointer-based data structure that can be used to create a representation of a List. The linked-list implementation is so commonly used to represent a List ADT that the terms are interchanged in common use.

Similarly, a Binary Search Tree ADT can be represented in several ways: binary tree, AVL tree, red-black tree, array, etc. Regardless of the implementation, the Binary Search Tree always has the same operations (insert, remove, find, etc.)

Separating the interface from the implementation doesn't always mean the user is unaware of the implementation method, but rather that they can't depend on any of the implementation details. For example, an ADT can be created using a scripting language or one that can be decompiled (like C). Even though the user can discover the implementation method, the construct can still be called an ADT as long as any client program that conforms to the interface is unaffected if the implementation changes.

In object-oriented parlance, an ADT is a class; an instance of an ADT or class is an object. Some languages include a constructor for declaring ADTs or classes. For example, C++ and Java provide a class constructor for this purpose.

---

---