Una struttura dati è un modo di organizzare e memorizzare i dati in memoria in modo che possano essere accessibili e modificati efficientemente. Un tipo di dato astratto (ADT) è il modello logico — le operazioni e il loro comportamento — indipendente da come viene implementato.
L'ADT descrive operazioni esistono; la struttura dati decide sono memorizzati e quanto velocemente vengono eseguiti.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Aspetto | Domanda da porsi |
|---|---|
| Modello di accesso | Accesso casuale o sequenziale? |
| Mutazioni | Inserimenti/cancellazioni frequenti nel mezzo? |
| Ordinamento | Ordinato, FIFO, LIFO, o nessuno? |
| Ricerche | Per indice o per chiave? |
La scelta giusta è quella le cui operazioni comuni sono economiche per il tuo carico di lavoro.
Scegliere la struttura sbagliata trasforma un'operazione O(1) in O(n), il che può rendere il codice migliaia di volte più lento su larga scala.
Pensare in termini di ADT ti permette di ragionare sul comportamento per primo, poi di scambiare implementazioni in seguito senza riscrivere i chiamanti.