Hva er en abstrakt datatype (ADT) og hvorfor skille den fra implementeringen?

Question

Accepted Answer

En **abstract data type** definerer et sett med verdier og **operasjonene** tillatt på dem, beskrevet rent gjennom **oppførsel** — ikke gjennom kode. Implementeringen er den konkrete strukturen (array, linked list, tree) som realiserer denne oppførselen.

## Samme ADT, ulike 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 skille 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.
```

## Vanlige ADTer og typiske implementeringer

| ADT | Vanlige 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 er viktig

Å programmere mot en ADT (et interface) holder koden fleksibel: du kan optimalisere implementeringen senere uten å bryte kallerne.

Det skjerper også resonnementet ditt — du bestemmer først *hvilken oppførsel* du trenger, og velger deretter den billigste strukturen som gir den.

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