Abstract data type

For thoughtful child sponsors

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 (or list) could be defined as follows. A sequence contains a variable number of ordered elements, and supports the following operations:

create a new, empty sequence
get a handle to the first element of a sequence
get a handle to the next element of a sequence
get a handle to the last element of a sequence
get a handle to the previous element of a sequence
get a handle to an arbitrary element of a sequence
insert an element at the beginning of a sequence
insert an element at the end of a sequence
insert an element after an element of a specific handle
delete the first element of a sequence
delete the last element of a sequence
delete the element at a specific handle
delete all elements between two handles

Where a handle is associated with a single element and allows the following operations:

get the value of the associated element of this handle
modify the value of the associated element of this handle

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".