abstract data type(redirected from Abstract data structure)
Also found in: Acronyms, Wikipedia.
abstract data type[′abz·trakt ′dad·ə ‚tīp]
Abstract data type
A mathematical entity consisting of a set of values (the carrier set) and a collection of operations that manipulate them. For example, the Integer abstract data type consists of a carrier set containing the positive and negative whole numbers and 0, and a collection of operations manipulating these values, such as addition, subtraction, multiplication, equality comparison, and order comparison.
To abstract is to ignore some details of a thing in favor of others. Abstraction is important in problem solving because it allows problem solvers to focus on essential details while ignoring the inessential, thus simplifying the problem and bringing to attention those aspects of the problem involved in its solution. Abstract data types are important in computer science because they provide a clear and precise way to specify what data a program must manipulate, and how the program must manipulate its data, without regard to details about how data are represented or how operations are implemented. Once an abstract data type is understood and documented, it serves as a specification that programmers can use to guide their choice of data representation and operation implementation, and as a standard for ensuring program correctness.
A realization of an abstract data type that provides representations of the values of its carrier set and algorithms for its operations is called a data type. Programming languages typically provide several built-in data types, and usually also facilities for programmers to create others. Most programming languages provide a data type realizing the Integer abstract data type, for example. The carrier set of the Integer abstract data type is a collection of whole numbers, so these numbers must be represented in some way. Programs typically use a string of bits of fixed size (often 32 bits) to represent Integer values in base two, with one bit used to represent the sign of the number. Algorithms that manipulate these strings of bits implement the operations of the abstract data type. See Algorithm, Programming languages
Realizations of abstract data types are rarely perfect. Representations are always finite, while carrier sets of abstract data types are often infinite. Many individual values of some carrier sets (such as real numbers) cannot be precisely represented on digital computers. Nevertheless, abstract data types provide the standard against which the data types realized in programs are judged.
Such specifications of abstract data types provide the basis for their realization in programs. Programmers know which data values need to be represented, which operations need to be implemented, and which constraints must be satisfied. Careful study of program code and the appropriate selection of tests help to ensure that the programs are correct. Finally, specifications of abstract data types can be used to investigate and demonstrate the properties of abstract data types themselves, leading to better understanding of programs and ultimately higher-quality software. See Computer programming, Software engineering
Relation to object-oriented paradigm
A major trend in computer science is the object-oriented paradigm, an approach to program design and implementation using collections of interacting entities called objects. Objects incorporate both data and operations. In this way they mimic things in the real world, which have properties (data) and behaviors (operations). Objects that hold the same kind of data and perform the same operations form a class.
Abstract data values are separated from abstract data type operations. If the values in the carrier set of an abstract data type can be reconceptualized to include not only data values but also abstract data type operations, then the elements of the carrier set become entities that incorporate both data and operations, like objects, and the carrier set itself is very much like a class. The object-oriented paradigm can thus be seen as an outgrowth of the use of abstract data types. See Object-oriented programming
abstract data type(programming)
Objects and ADTs are both forms of data abstraction, but objects are not ADTs. Objects use procedural abstraction (methods), not type abstraction.
A classic example of an ADT is a stack data type for which functions might be provided to create an empty stack, to push values onto a stack and to pop values from a stack.
Cook paper "OOP vs ADTs".