Come scegli la giusta struttura dati per un problema?

Question

Accepted Answer

Scegli la struttura le cui **operazioni più frequenti sono più economiche** per il tuo schema di accesso. Inizia elencando le operazioni che eseguirai, stima la loro frequenza, quindi abbina la struttura alle sue caratteristiche di forza.

## Una checklist decisionale

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Abbina operazioni a complessità

| Esigenza | Miglior struttura | Costo op chiave |
|---|---|---|
| Accesso casuale per indice | array dinamico | O(1) |
| Lookup per chiave | hash map | O(1) avg |
| Ordinato + query di intervallo | BST bilanciato | O(log n) |
| Min/max ripetutamente | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Ricerca per prefisso | trie | O(L) |

## Esempio di ragionamento

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Perché è importante

Scegliere bene spesso è la differenza tra una soluzione O(n) e O(n²) — la leva singola più grande sulla performance.

I colloquiatori testano esattamente questo ragionamento: vogliono vedere come mappi i requisiti ai costi delle operazioni, non che memorizzi le strutture.

Esigenza	Miglior struttura	Costo op chiave
Accesso casuale per indice	array dinamico	O(1)
Lookup per chiave	hash map	O(1) avg
Ordinato + query di intervallo	BST bilanciato	O(log n)
Min/max ripetutamente	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Ricerca per prefisso	trie	O(L)