Strutture dati — array, liste collegate, alberi e grafi

Le strutture dati sono modi di organizzare i dati in modo che operazioni comuni come ricerca, inserimento, eliminazione e attraversamento diventino più semplici. Se vuoi capire array, liste collegate, alberi e grafi, l'approccio più rapido è farti due domande: che forma hanno i dati e quale operazione deve risultare poco costosa?

Se i dati sono una sequenza, un array è spesso il punto di partenza. Se ogni elemento punta soprattutto all'elemento successivo, può andare bene una lista collegata. Se i dati hanno livelli, usa un albero. Se gli elementi possono collegarsi in molte direzioni, usa un grafo.

Ecco la regola utile più breve:

• Array: ideale per l'ordine indicizzato.
• Lista collegata: ideale per collegamenti locali concatenati.
• Albero: ideale per la gerarchia.
• Grafo: ideale per le reti.

Cosa fanno davvero array, liste collegate, alberi e grafi

Un array memorizza elementi in un ordine fisso e ti permette di riferirti direttamente a una posizione, come "elemento $7$". Nell'implementazione contigua usuale, questa indicizzazione diretta è $O(1)$.

Una lista collegata memorizza gli elementi come nodi, dove ogni nodo punta a un altro nodo. Puoi spostarti da nodo a nodo, ma per raggiungere l'$n$-esimo elemento di solito devi attraversare i nodi precedenti, quindi l'accesso per posizione è tipicamente $O(n)$.

Un albero memorizza i dati per livelli. Ogni nodo può avere figli, quindi la struttura rappresenta naturalmente annidamenti come cartelle dentro altre cartelle. I costi di ricerca e aggiornamento dipendono dal tipo di albero e dal fatto che resti bilanciato.

Un grafo memorizza nodi e archi. A differenza di un albero, un nodo può collegarsi a molti altri in modi arbitrari, e i cicli sono ammessi. Questo rende i grafi il modello naturale per strade, reti sociali e mappe di dipendenze.

Confronto rapido: quando si adatta ogni struttura dati

Struttura	Miglior modello mentale	Di solito è adatta a	Limite comune
Array	Una fila numerata di elementi	Accesso diretto per indice	Inserimenti ed eliminazioni nel mezzo spesso richiedono lo spostamento degli elementi
Lista collegata	Una catena di nodi	Inserire o rimuovere vicino a un nodo noto	L'accesso casuale è lento
Albero	Una gerarchia ramificata	Rappresentare livelli e relazioni padre-figlio	Il comportamento dipende molto dal tipo di albero
Grafo	Una rete di connessioni	Raggiungibilità, percorsi e relazioni	Gli algoritmi sono spesso più complessi

Esempio svolto: scegliere le strutture in un'unica app del campus

Supponiamo che tu stia costruendo un'unica app del campus con una schermata dell'orario, un catalogo dei corsi e una mappa dei percorsi a piedi. Il modo più semplice per scegliere una struttura dati è abbinare ogni funzione alla forma dei suoi dati.

Le schede dei giorni feriali in una schermata dell'orario sono naturalmente un array:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

La caratteristica chiave è l'accesso diretto per posizione. "Mostrami la scheda $3$" ha senso, e l'ordine conta.

Il catalogo dei corsi è naturalmente un albero:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

Ogni livello contiene il livello successivo. Questa è una gerarchia, quindi un albero è il modello più pulito.

I percorsi tra gli edifici sono naturalmente un grafo. Un edificio può collegarsi a molti altri, e i percorsi possono tornare indietro formando cicli. Se vuoi il tragitto più breve dalla biblioteca al laboratorio, stai risolvendo un problema di grafi, non un problema di alberi.

Una lista collegata si adatta a una parte più ristretta della stessa app: una catena di schermate visitate di recente, se l'operazione principale è andare avanti o indietro di un passo alla volta. In quel caso, ogni schermata ha bisogno soprattutto di collegamenti alle schermate vicine, non di accesso rapido alla $20$-esima schermata.

La lezione è che "migliore" dipende dal compito. Un solo prodotto può usare diverse strutture dati perché parti diverse dei dati hanno relazioni diverse.

Come distinguerli rapidamente

Molti studenti all'inizio li imparano come semplici parole di vocabolario. Questo fa sembrare l'argomento astratto, ma la domanda pratica è più semplice.

Chiediti: quale operazione dovrebbe risultare poco costosa?

Se vuoi che "vai alla posizione $i$" sia economico, gli array sono forti. Se vuoi che "segui la connessione successiva" sia economico, le strutture collegate aiutano. Se vuoi "scendere in una gerarchia", gli alberi sono adatti. Se vuoi "capire se due cose sono collegate", i grafi sono adatti.

Errori comuni quando si imparano le strutture dati

Pensare che una struttura sia sempre la più veloce

Non esiste un vincitore universale. "Veloce" dipende da ciò che fai più spesso e dall'implementazione.

Trattare gli alberi come automaticamente efficienti

Alcuni alberi supportano ricerche molto efficienti, ma questo dipende dal tipo di albero e da condizioni strutturali come il bilanciamento. Un albero con una forma sfavorevole può funzionare molto peggio di uno bilanciato.

Scegliere una lista collegata solo perché l'inserimento sembra economico

L'inserimento può essere economico una volta che hai già il nodo giusto. Trovare quel nodo può comunque richiedere tempo.

Usare un albero quando i dati sono in realtà un grafo

Se un elemento può avere più padri, collegamenti trasversali o cicli, forzare i dati dentro un albero può nascondere la struttura reale e rendere scomode le operazioni successive.

Confondere una struttura astratta con una funzionalità del linguaggio

"Array", "lista", "mappa" o "albero" in un linguaggio di programmazione possono includere scelte di implementazione che influenzano uso della memoria e velocità. L'idea astratta e il contenitore concreto sono collegati, ma non sono identici.

Quando si usano array, liste collegate, alberi e grafi

Gli array si usano per collezioni ordinate, tabelle, buffer e in tutti i casi in cui la posizione conta.

Le liste collegate compaiono in implementazioni specializzate in cui gli aggiornamenti locali dei puntatori contano più dell'accesso casuale.

Gli alberi si usano per dati gerarchici come file system, struttura dei documenti, alberi di espressione e molti indici di ricerca.

I grafi si usano per percorsi, analisi delle dipendenze, modellazione di reti, collegamenti di raccomandazione e problemi di connessione in generale.

Come scegliere la struttura dati giusta

Inizia facendoti due domande:

1. Che relazione hanno i dati: sequenza, gerarchia o rete?
2. Quale operazione conta di più: indicizzazione, aggiornamento locale, attraversamento gerarchico o ricerca di percorsi?

Queste due risposte di solito restringono rapidamente la scelta.

Se hai ancora dubbi, disegna su carta una versione molto piccola dei dati. Spesso l'immagine rivela la struttura prima ancora del codice.

Prova la tua versione

Scegli tre esempi familiari come una playlist, un sistema di cartelle e una mappa dei trasporti. Identifica se ciascuno è principalmente una sequenza, una gerarchia o una rete, poi scegli la struttura che rende facile l'operazione principale. Se vuoi un altro caso su cui metterti alla prova, GPAI Solver può generare esempi di classificazione simili.