Strutture Dati Lineari: Array, Liste Collegate, Stack e Queue a Confronto Spiegate Semplice

Nel 1976 uno dei più grandi pionieri dell’informatica moderna, Niklaus Wirth, intitolò un suo celebre libro universitario con una formula che è diventata il manifesto di tutti i programmatori:

Questo aforisma racchiude una verità fondamentale: un algoritmo (la ricetta logica) non può funzionare nel vuoto. Ha bisogno di un supporto ordinato all’interno della memoria RAM dove appoggiare, organizzare e ritrovare i dati con cui deve lavorare.

Se organizzi i dati in modo disordinato o scegli il contenitore sbagliato, anche l’algoritmo più geniale del mondo si trasformerà in un software lento come una lumaca e instabile!

I contenitori più importanti e utilizzati in tutti i linguaggi di programmazione sono le Strutture Dati Lineari: collezioni in cui gli elementi sono disposti uno dopo l’altro in una sequenza ordinata.

In questa guida esploreremo le quattro strutture regine: gli Array, le Liste Collegate, le Pile (Stack) e le Code (Queue), capendo quando usare ciascuna di esse attraverso analogie divertenti e immediate.

flowchart TD

subgraph ARR["1. ARRAY IN RAM: Blocco Fisico Contiguo (Accesso Diretto O(1))"]

C0["Indice [0]
Indirizzo: 0x1000
Dato: 'Roma'"] --- C1["Indice [1]
Indirizzo: 0x1004
Dato: 'Milano'"] --- C2["Indice [2]
Indirizzo: 0x1008
Dato: 'Napoli'"] --- C3["Indice [3]
Indirizzo: 0x100C
Dato: 'Torino'"]

end
subgraph LST["2. LISTA COLLEGATA (LINKED LIST): Nodi Sparsi in Memoria con Puntatori"]
    N1["Nodo 1 (Head)
Valore: 'Roma'
Next: 0x8540"] -->|"Puntatore"| N2["Nodo 2 (RAM sparsa)
Valore: 'Milano'
Next: 0x2210"]
    N2 -->|"Puntatore"| N3["Nodo 3 (RAM sparsa)
Valore: 'Napoli'
Next: NULL"]
end

1. Array contro Liste Collegate: I Sedili del Treno contro la Caccia al Tesoro

Per capire la differenza fondamentale tra come un Array e una Lista organizzano la memoria, immaginiamo due modi completamente diversi di far sedere un gruppo di amici:

flowchart LR

subgraph STK["STACK (Politica L.I.F.O. - Last In, First Out)"]

direction TB

P_IN["📥 PUSH (Inserisci in Cima)"] --> S3["Elemento C (In Cima)"]

S3 --> S2["Elemento B"]

S2 --> S1["Elemento A (Fondo Pila)"]

S3 --> P_OUT["📤 POP (Estrai dalla Cima)"]

end
subgraph QUE["QUEUE (Politica F.I.F.O. - First In, First Out)"]
    direction LR
    Q_IN["📥 ENQUEUE (Accodamento sul Retro)"] --> Q3["Ultimo arrivato"]
    Q3 --> Q2["In attesa"]
    Q2 --> Q1["Primo arrivato (Testa)"]
    Q1 --> Q_OUT["📤 DEQUEUE (Servito per Primo)"]
end

2. Lo Stack (La Pila): La Politica L.I.F.O. (Last In, First Out)

Lo Stack (chiamato in italiano Pila) è una struttura dati semplicissima ed elegantissima che tutti noi usiamo ogni giorno senza saperlo.

Immaginiamo una pila di piatti da lavare o una pila di magliette ripiegate nell’armadio:

• Puoi appoggiare un nuovo piatto solo sopra la cima della pila.
• Se vuoi prendere un piatto, puoi sfilare solo quello che sta in cima. Se provi a tirare fuori un piatto dal fondo, fai crollare tutto!

Questa regola si chiama L.I.F.O. (Last In, First Out – L’ultimo arrivato è il primo a uscire):

Dove viene usato lo Stack nella vita reale?

1. Il Tasto "Annulla" (Ctrl + Z): Ogni azione che compi in Word o Photoshop viene impilata in uno Stack. Quando premi "Annulla", il software fa un pop() ed elimina l’ultimissima azione compiuta!
2. Il Tasto "Indietro" del Browser Web: Ogni sito che visiti viene impilato sopra la cronologia. Premendo la freccia indietro, torni all’ultima pagina vista.
3. Il Call Stack della CPU: Quando una funzione ne chiama un’altra, il processore memorizza il punto di ritorno in una pila speciale (se chiami funzioni all’infinito senza fermarti, saturi la memoria provocando il celebre errore Stack Overflow!).

3. La Queue (La Coda): La Politica F.I.F.O. (First In, First Out)

Se lo Stack è una pila di piatti, la Queue (Coda) è esattamente come la fila di persone alla cassa del supermercato o allo sportello delle Poste:

• Chi arriva per primo viene servito per primo.
• Chi arriva dopo si mette in fondo alla fila e deve attendere il proprio turno.
• È severamente vietato "passare avanti" saltando la fila!

Questa regola si chiama F.I.F.O. (First In, First Out – Il primo arrivato è il primo a uscire):

Dove viene usata la Coda nel computer?

1. La Coda di Stampa (Print Spooler): Se tre persone in ufficio inviano contemporaneamente un documento alla stessa stampante, la stampante non mescola i fogli: li mette in una coda e stampa prima il documento arrivato per primo!
2. I Server Web e i Biglietti dei Concerti: Quando migliaia di fan si collegano su TicketOne, vengono messi in una coda virtuale FIFO: chi si è collegato alle 10:00:01 acquista prima di chi si è collegato alle 10:00:05.
3. I Buffer Audio/Video: Quando guardi un video su YouTube, i pacchetti di dati scaricati finiscono in una coda FIFO pronti per essere riprodotti in ordine senza scatti.

4. Quadro sinottico comparativo delle Strutture Dati Lineari

La tabella seguente riassume le quattro strutture dati lineari, evidenziandone la complessità temporale e i casi d’uso ottimali:

5. Domande Frequenti sulle Strutture Dati (FAQ)

Che differenza c’è tra una Lista Semplice e una Lista Doppiamente Collegata?

• In una Lista Singolarmente Collegata (Singly Linked List), ogni nodo ha un solo puntatore che guarda verso il nodo successivo: puoi camminare solo in avanti.
• In una Lista Doppiamente Collegata (Doubly Linked List), ogni nodo ha due puntatori: uno che guarda al successivo e uno che guarda al precedente! Puoi scorrere la lista comodamente sia in avanti che all’indietro (come la playlist delle canzoni su Spotify, dove puoi fare sia "Traccia Successiva" che "Traccia Precedente").

In Python le Liste sono Array o Liste Collegate?

In Python, l’oggetto comune lista = [1, 2, 3] è in realtà implementato internamente come un Array Dinamico ridimensionabile, non come una lista collegata a puntatori! Per questo motivo accedere a lista[5] è istantaneo $O(1)$. Se hai bisogno di una vera coda super-veloce in Python, la libreria standard offre collections.deque.

Che cos’è una "Coda con Priorità" (Priority Queue)?

È una variante speciale della coda in cui gli elementi non vengono serviti solo in ordine di arrivo, ma anche in base alla loro importanza o urgenza. L’esempio perfetto è il Pronto Soccorso dell’ospedale: anche se sei arrivato prima con un raffreddore (codice bianco), una persona che arriva dopo con un’emergenza critica (codice rosso) viene servita immediatamente prima di te!

Come si verifica se uno Stack è vuoto prima di fare un Pop?

Nei programmi seri, prima di estrarre un elemento con pop() si controlla sempre una funzione booleana chiamata is_empty(). Se provi a estrarre un piatto da una pila completamente vuota, il programma si blocca sollevando un errore chiamato Stack Underflow!

6. Glossario essenziale

• Nodo (Node): Il singolo elemento di una lista collegata contenente sia il dato utile, sia il puntatore con l’indirizzo di memoria del nodo successivo.
• Puntatore (Pointer): Una speciale variabile che non contiene un numero comune, ma l’indirizzo esatto di una cella della memoria RAM.
• LIFO (Last In, First Out): La politica di gestione per cui l’ultimo elemento inserito è il primo a essere estratto (modello Pila/Stack).
• FIFO (First In, First Out): La politica di gestione per cui il primo elemento inserito è il primo a essere servito (modello Coda/Queue).
• Buffer Circolare: Un’ingegnosa implementazione di una coda all’interno di un array a dimensione fissa in cui la fine dell’array si ricollega all’inizio formando un anello continuo.

Fonti e Riferimenti Accademici Ufficiali

• Wirth, Niklaus (1976): Algorithms + Data Structures = Programs, Prentice-Hall. L’opera seminale che ha definito per la prima volta la relazione inscindibile tra architettura della memoria e algoritmi di calcolo.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.: Introduction to Algorithms (4th Edition), MIT Press. Capitolo 10: "Elementary Data Structures – Stacks and Queues, Linked Lists, Implementing Pointers".
• Knuth, Donald E.: The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley. Capitolo 2: "Information Structures – Linear Lists, Stacks, Queues, and Deques".
• Sedgewick, Robert, & Wayne, Kevin: Algorithms (4th Edition), Addison-Wesley. Capitolo 1.3: "Bags, Queues, and Stacks".