Was ist ein abstrakter Datentyp (ADT) und warum sollte er von seiner Implementierung getrennt werden?

Question

Accepted Answer

Ein **abstrakter Datentyp** definiert eine Menge von Werten und die auf ihnen zulässigen **Operationen**, beschrieben rein durch **Verhalten** – nicht durch Code. Die Implementierung ist die konkrete Struktur (array, linked list, tree), die dieses Verhalten realisiert.

## Derselbe ADT, verschiedene Implementierungen

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

## Warum sie trennen

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

## Häufige ADTs und typische Implementierungen

| ADT | Häufige Implementierungen |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Warum es wichtig ist

Programmierung gegen einen ADT (eine Schnittstelle) hält den Code flexibel: Sie können die Implementierung später optimieren, ohne die Aufrufer zu beschädigen.

Es schärft auch das Denken – Sie entscheiden zunächst, *welches Verhalten* Sie benötigen, und wählen dann die billigste Struktur aus, die es bietet.

ADT	Häufige Implementierungen
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap