Main Page | See live article | Alphabetical index

Abstract data type

Abstract data types or ADTs are data types described in terms of the operations they support (their interface) rather than how they are implemented.

For example, a sequence could be defined as follows. A sequence contains a variable number of ordered elements, and supports the following operations:

Where a handle is associated with a single element and allows the following operations: Arrays, linked lists, and binary trees --- among other data structures --- can all support these operations, with different performance tradeoffs. Arrays are fast at accessing the previous, next, first, last or arbitrary element, but slow at inserting or deleting items from anywhere but the very end; singly-linked lists are fast at accessing the first or next element, as well as adding or deleting items after a given handle, but slow at accessing arbitrary, the previous, or the last element; and binary trees are relatively fast at all the above operations, but not as fast as arrays or linked lists are at the specific operations for which they are each fastest.

Some programming languages, such as Ada and Modula-2, have explicit support for abstract data types. Object-oriented languages carry this a step further by adding inheritance and polymorphism to ADTs to get "objects".