ADTS

An abstract data type (ADT) is a model of a data type defined by its behavior from the perspective of a user. An ADT specifies a finite set of values and a collection of operations that can be applied to those values, along with axioms describing how these operations interact. An ADT does not dictate how data is represented or how the operations are implemented; those choices are left to concrete data structures and algorithms.

Common examples include Stack, Queue, List, Map, and Set. Each ADT defines a standard interface. For example, a Stack provides operations such as push, pop, peek, and isEmpty; a Queue provides enqueue, dequeue, front, and isEmpty; a Map provides put, get, remove, and containsKey; a Set provides add, remove, contains, and size. These operations establish expected behavior without prescribing implementation details.

ADTs are independent of implementation. The same Stack ADT might be realized with an array, a linked list, or a dynamic array, with differing performance characteristics. The choice of underlying data structure affects time and space requirements for operations and can influence concurrency properties and memory usage.

Languages implement ADTs in various ways, such as interfaces or abstract classes in Java, type classes in Haskell, or modules in ML. Encapsulation and access controls help preserve abstraction, while some languages allow opaque representations to hide internal details. This separation of specification from implementation supports modular design and enables interchangeable implementations without changing user code.

Understanding ADTs provides a foundation for formal reasoning about correctness and efficiency, and it offers a concise vocabulary for discussing data manipulation independent of specific implementations.