Abstract data type

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

For example, "linear list" is an abstract data type, defined as follows. A linear list contains a sequence of elements; it supports operations including the following:

• get a pointer to the first element
• get a pointer to the Nth element
• get a pointer to the last element
• get a pointer to the element after the one this pointer points to
• get a pointer to the previous element
• set the element this pointer points to to this value
• get the value of the element this pointer points to
• insert this element (after the element this pointer points to, at the beginning, at the end)
• delete the element this pointer points to
• delete the element after the one this pointer points to
• delete the first element
• delete the last element
• delete the elements between these two pointers
• insert all the elements of another sequence (at the beginning, end, after this element)

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 Nth, previous, next, first, or last element, adding and deleting items at the end, but slow at inserting or deleting items from the middle or adding or deleting bunches of items; singly-linked lists are fast at accessing the first or next element, adding and deleting items or bunches of items anywhere, but slow at accessing the Nth, previous, or last element; and binary trees are fast at everything, although not nearly as fast as arrays or linked lists are at the things they're good for.

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