Abstract Data Types

Abstract data types, commonly abbreviated ADTs, are a way of classifying data structures based on how they are used and the behaviors they provide. They do not specify how the data structure must be implemented or laid out in memory, but simply provide a minimal expected interface and set of behaviors. For example, a stack is an abstract data type that specifies a linear data structure with LIFO (last in, first out) behavior. Stacks are commonly implemented using arrays or linked lists, but a needlessly complicated implementation using a binary search tree is still a valid implementation. To be clear, it is incorrect to say that stacks are arrays or vice versa. An array can be used as a stack. Likewise, a stack can be implemented using an array.

Since abstract data types don't specify an implementation, this means it's also incorrect to talk about the time complexity of a given abstract data type. An associative array may or may not have \(O(1)\) average search times. An associative array that is implemented by a hash table does have \(O(1)\) average search times.

To further complicate matters, since certain abstract data types are almost always implemented with a particular data structure, some programmers will use the two terms interchangeably: for example, priority queue and heap, or associative array and hash table. The context in which the term is being used can usually provide distinction.