ADTs vs Data Structures
A data structure is a concrete way of organizing data in memory, while an abstract data type (ADT) is the behavior that organization provides, described independently of how it is built.
The ADT acts as the interface—a set of operations and promised behavior. The data structure is one implementation of that interface. For example, a List ADT promises operations like get(i), add(x), remove(i), and size().
A List can be implemented by a contiguous array or a chain of linked nodes. Both honor the exact same List interface while offering very different internal performance characteristics.
Choosing the Right Fit
Because callers depend on the interface, not the implementation, you can swap one data structure for another to change performance without rewriting client code.
| Concept | Definition | Role |
|---|---|---|
| ADT | Abstract behavior | The interface |
| Structure | Memory organization | The implementation |
Common pitfall: Conflating the ADT with a particular implementation, thinking a list is an array. Keeping interface and implementation separate lets you reason about behavior first and performance second.