Wat is een abstract data type (ADT) en waarom scheiden we het van zijn implementatie?

Question

Accepted Answer

Een **abstract data type** definieert een set waarden en de **operaties** die daarop zijn toegestaan, beschreven puur door **gedrag** — niet door code. De implementatie is de concrete structuur (array, linked list, tree) die dat gedrag realiseert.

## Waarom het belangrijk is

Hetzelfde ADT, verschillende implementaties

```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.
```

## Waarom scheiden

```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.
```

## Veelgebruikte ADTs en typische implementaties

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

## Waarom het belangrijk is

Programmeren naar een ADT (een interface) houdt code flexibel: je kunt de implementatie later optimaliseren zonder aanroepers te breken.

Het scherpt ook je redenering — je bepaalt eerst *welk gedrag* je nodig hebt, en kiest dan de goedkoopste structuur die het biedt.

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