Hvad er en abstrakt datatype (ADT), og hvorfor adskille den fra dens implementering?

Question

Accepted Answer

En **abstrakt datatype** definerer et sæt af værdier og de **operationer**, der er tilladt på dem, beskrevet rent gennem **adfærd** – ikke gennem kode. Implementeringen er den konkrete struktur (array, linked list, tree), der realiserer denne adfærd.

## Den samme ADT, forskellige implementeringer

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

## Hvorfor adskille dem

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

## Almindelige ADT'er og typiske implementeringer

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

## Hvorfor det betyder noget

At programmere mod en ADT (et interface) holder koden fleksibel: du kan optimere implementeringen senere uden at bryde opkaldere.

Det skarpner også ræsonnementet – du beslutter først, *hvilken adfærd* du har brug for, og vælger derefter den billigste struktur, der leverer det.

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