Vad är en abstrakt datatyp (ADT) och varför ska man separera den från implementationen?

Question

Accepted Answer

En **abstrakt datatyp** definierar en uppsättning värden och **operationer** som är tillåtna på dem, beskrivna rent genom **beteende** — inte genom kod. Implementationen är den konkreta strukturen (array, länkad lista, träd) som realiserar det beteendet.

## Samma ADT, olika implementationer

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

## Varför separera 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.
```

## Vanliga ADT:er och typiska implementationer

| ADT | Vanliga implementationer |
|---|---|
| List | dynamisk array, länkad lista |
| Stack | array, länkad lista |
| Queue | ring buffer, länkad lista |
| Map | hash table, balanserat träd |
| Priority Queue | binär heap |

## Varför det är viktigt

Att programmera enligt en ADT (ett gränssnitt) gör koden flexibel: du kan optimera implementationen senare utan att bryta anropare.

Det skärper också resonemanget — du bestämmer först *vilket beteende* du behöver, sedan väljer du den billigaste strukturen som tillhandahåller det.

ADT	Vanliga implementationer
List	dynamisk array, länkad lista
Stack	array, länkad lista
Queue	ring buffer, länkad lista
Map	hash table, balanserat träd
Priority Queue	binär heap