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. 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-***** tree, array, etc. Regardless of the implementation, the Binary Search Tree always has the same operations (insert, remove, find, etc.)
