An abstract data type (ADT) is a logical description of a data structure defined by the data it stores and the permitted operations on that data, rather than by how those operations are implemented. Examples include stacks, queues, lists, sets, and dictionaries.
The Reasoning and Mechanism
An ADT specifies an interface: the operations available to a program and the expected behavior of each operation. Its internal representation and algorithms are hidden through abstraction.
For example, a stack ADT follows last in, first out (LIFO) behavior. Its interface commonly provides:
push(item): adds an item to the toppop(): removes and returns the top itempeek(): returns the top item without removing itisEmpty(): checks whether the stack contains no items
The stack could be implemented using an array or a linked list. These implementations differ internally, but both represent the same ADT if they provide the required stack behavior.
| Aspect | ADT | Implementation |
|---|---|---|
| Focus | What operations do | How operations are performed |
| Example | Stack with push and pop | Array-based or linked-list stack |
| Visibility | Interface is available to the user | Internal details are hidden |
| Benefit | Supports abstraction and modular design | Determines efficiency and memory use |
This separation allows programmers to change an implementation without changing code that uses the interface. It also supports encapsulation, because access to the stored data is controlled by defined operations.
A common misconception is that an ADT is the same as a data structure. An ADT describes required behavior; a data structure is the concrete organization of data used to implement that behavior.
