Abstract data type
|
|
Abstract data types or ADTs are a mathematical specification of a set of data and the set of operations that can be performed on the data. They are abstract in the sense that the focus is on the definitions of the constructor that returns an abstract handle that represents the data, and the various operations with their arguments. The actual implementation is not defined, and does not affect the use of the ADT.
For example, rational numbers (numbers that can be written in the form a/b where a and b are integers) cannot be represented natively in a computer. A Rational ADT could be defined as shown below.
Construction: Create an instance of a rational number ADT using two integers, a and b, where a represents the numerator and b represents the denominator.
Operations: addition, subtraction, multiplication, division, exponentiation, comparison, simplify, conversion to a real (floating point) number.
To be a complete specification, each operation should be defined in terms of the data. For example, when multiplying two rational numbers a/b and c/d, the result is defined as ac/bd. Typically, inputs, outputs, preconditions, postconditions, and assumptions to the ADT are specified as well.
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.)
ADTs typically seen in textbooks and implemented in programming languages (or their libraries) include:
- String ADT
- List ADT
- Stack (last-in, first-out) ADT
- Queue (first-in, first-out) ADT
- Binary Search Tree ADT
- Priority Queue ADT
- Complex Number ADT (imaginary numbers)
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 and understood 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.)
In a more concrete example, written in C-style notation, the interface for a Stack ADT might be:
long stack_create(); /* create new instance of a stack */ void stack_push(long stack, void *item); /* push an item on the stack */ void *stack_pop(long stack); /* get item from top of stack */ void stack_delete(long stack); /* delete the stack */
This ADT could be used in the following manner:
long stack; struct foo *f; stack = create_stack(); /* create a stack */ stack_push(stack, f); /* add foo structure to stack */ f = stack_pop(stack); /* get top structure from stack */
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. The above stack ADT could be initially implemented using an array, and then later changed to a linked list, without affecting any user code.
The number of ways a given ADT can be implemented depends on the programming language. For example, the above example could be written in C using a struct and an accompanying set of data structures using arrays or linked lists to store the entries; however, since the constructor function returns an abstract handle, the actual implementation is hidden from the user. In object-oriented languages such as C++ and Java, ADTs are typically represented using the class construct where the data is represented by data members (attributes) and the operations are represented by member functions (methods). In addition, some languages such as C++ and Java provide a mechanism of enforcement (the private or protected keywords) to only allow the defined functions to operate on the data. When using object-oriented ADTs, the user can often expand the ADT by creating a subclass of the ADT.
Because some ADTs are so common and useful in computer programs, some programming languages are building implementations of ADTs into the language as native types or adding them into their standard libraries. For instance, Perl arrays can be thought of as an implementation of the List or Deque ADTs and Perl hashes can be thought of in terms of Map or Table ADTs. The C++ Standard Library and Java libraries provides classes that implement the List, Stack, Queue, Map, Priority Queue, and String ADTs.