Explain the difference between a Data Structure and an Abstract Data Type (ADT).
Data Structure vs Abstract Data Type
An Abstract Data Type is a theoretical/logical model that defines a set of operations and their behavior without specifying how those operations are implemented. It describes 'what' the data type does, not 'how' it does it. A Stack ADT, for instance, defines push, pop, and peek operations along with LIFO ordering semantics, but says nothing about how the stack is stored in memory.
A Data Structure is the concrete implementation of an ADT. It specifies the actual memory layout and the algorithms used to implement the ADT's operations. For example, the Stack ADT can be implemented using an array-based data structure or a linked-list-based data structure, both satisfying the same interface but differing in performance characteristics such as resizing cost or memory overhead.
- 1
ADT = logical/interface-level specification (what operations exist)
- 2
Data Structure = physical/implementation-level realization (how operations are executed)
- 3
One ADT can have multiple valid data structure implementations
- 4
Example: List ADT implemented via Array List or Linked List
Follow-up Questions
- Give an example of an ADT with two different implementations and compare their trade-offs.