What is an abstract data type (ADT) and why separate it from its implementation?

Question

Accepted Answer

An **abstract data type** defines a set of values and the **operations** allowed on them, described purely by **behavior** — not by code. The implementation is the concrete structure (array, linked list, tree) that realizes that behavior.

## The same ADT, different implementations

```text
ADT "Queue":  enqueue, dequeue, peek  (FIFO contract)

Implementation A: array + two indices (ring buffer)
Implementation B: doubly linked list with head/tail pointers
Both honor the SAME contract; cost profiles differ.
```

## Why separate them

```python
# Callers depend on the CONTRACT, not the internals
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# Swap a list for a linked list internally — callers never change.
```

## Common ADTs and typical implementations

| ADT | Common implementations |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Why it matters

Programming to an ADT (an interface) keeps code flexible: you can optimize the implementation later without breaking callers.

It also sharpens reasoning — you decide *what behavior* you need first, then pick the cheapest structure that provides it.

ADT	Common implementations
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap