Mikä on abstrakti tietotyyppi (ADT) ja miksi se tulee erottaa sen toteutuksesta?

Question

Accepted Answer

**Abstrakti tietotyyppi** määrittelee arvojen joukon ja siihen sallitut **operaatiot**, joita kuvataan puhtaasti **käyttäytymisellä** — ei koodilla. Toteutus on konkreettinen rakenne (array, linked list, tree), joka toteuttaa tämän käyttäytymisen.

## Sama ADT, eri toteutukset

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

## Miksi ne erottaa

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

## Yleiset ADT:t ja tyypilliset toteutukset

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

## Miksi sillä on merkitystä

Ohjelmoiminen ADT:ta vastaan (rajapintaa) pitää koodin joustavana: voit optimoida toteutuksen myöhemmin ilman, että rikot kutsujia.

Se myös terävöittää päättelyä — päätät ensin, *millaista käyttäytymistä* tarvitset, ja valitset sitten halvimman rakenteen, joka sen tarjoaa.

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