Cos'è un tipo di dato astratto (ADT) e perché separarlo dalla sua implementazione?

Question

Accepted Answer

Un **tipo di dato astratto** definisce un insieme di valori e le **operazioni** consentite su di essi, descritti puramente dal **comportamento** — non dal codice. L'implementazione è la struttura concreta (array, lista collegata, albero) che realizza quel comportamento.

## Perché è importante

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

## Perché separare i due

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

## ADT comuni e implementazioni tipiche

| ADT | Implementazioni comuni |
|---|---|
| List | array dinamico, lista collegata |
| Stack | array, lista collegata |
| Queue | ring buffer, lista collegata |
| Map | hash table, albero bilanciato |
| Priority Queue | binary heap |

## Perché è importante

Programmare su un ADT (un'interfaccia) mantiene il codice flessibile: puoi ottimizzare l'implementazione in seguito senza rompere il codice dei chiamanti.

Accresce anche il ragionamento — decidi prima *quale comportamento* ti serve, poi scegli la struttura più economica che lo fornisce.

ADT	Implementazioni comuni
List	array dinamico, lista collegata
Stack	array, lista collegata
Queue	ring buffer, lista collegata
Map	hash table, albero bilanciato
Priority Queue	binary heap