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:

• get a handle to the first element
• get a handle to the next element
• get a handle to the last element
• get a handle to the previous element
• get a handle to an arbitrary element
• insert an element at the beginning of the sequence
• insert an element at the end of the sequence
• insert an element after an element of a specific handle
• delete the first element
• delete the last element
• 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".