Nelle ultime lezioni del corso di programmazione in linguaggio C abbiamo introdotto due strumenti che, presi singolarmente, possono sembrare un po’ astratti: la gestione dinamica della memoria e le strutture autoreferenziali, cioè struct che contengono un puntatore a una struct dello stesso tipo. Messi insieme, però, permettono di costruire una delle strutture dati più importanti in assoluto: la lista collegata.

In questa lezione, la numero 39 del corso, passiamo dalla teoria alla pratica e partiamo dal caso più semplice di lista collegata, lo stack. È un concetto che chi lavora con microprocessori e firmware conosce bene, perché è lo stesso meccanismo che la CPU usa per salvare l’indirizzo di ritorno quando chiama una subroutine. Qui lo realizziamo noi, in C, con i puntatori.

Cos’è una lista collegata in C

Una lista collegata è una collezione di elementi, ognuno dei quali è una struttura autoreferenziale: oltre ai dati utili contiene un puntatore all’elemento successivo. Questa catena di puntatori collega porzioni di memoria che non sono necessariamente contigue, e permette di attraversare tutta la lista partendo da un unico punto di ingresso, tipicamente il puntatore alla testa.

La fine della lista si riconosce in modo molto semplice: l’ultimo elemento ha il puntatore next impostato a NULL. È una convenzione che ritroveremo in tutte le operazioni, dalla stampa all’inserimento, e che rende naturale anche la gestione della lista vuota.

Liste collegate o array: vantaggi e svantaggi

La domanda che viene spontanea è perché complicarsi la vita con i puntatori quando esistono gli array. La risposta, come spesso accade in ingegneria, dipende dal contesto.

Il problema della memoria allocata in anticipo

Un array richiede di allocare fin da subito tutta la memoria che potrebbe servire. Se un programma deve gestire fino a un milione di record, ma nell’uso normale ne contiene qualche migliaio, l’array deve comunque essere dimensionato per il caso peggiore. In un sistema operativo multitasking, dove più applicazioni condividono le stesse risorse, è una scelta poco elegante: un programma dovrebbe usare la memoria di cui ha effettivamente bisogno, non quella di cui potrebbe avere bisogno. Con l’allocazione dinamica una lista cresce e si riduce insieme ai dati.

Accesso casuale e accesso sequenziale

L’array ha dalla sua l’accesso casuale: i dati sono contigui e l’elemento i-esimo è raggiungibile immediatamente. Una lista, invece, va percorsa dall’inizio fino a trovare l’elemento cercato, a meno di mantenerla ordinata o di adottare strategie di ricerca più furbe. Non sempre però l’indice è un’informazione utile: se cerchiamo una persona per nome, sapere che si trova in posizione 512 non ci dice molto.

L’overhead dei puntatori

C’è poi un costo da tenere presente: ogni elemento della lista porta con sé un puntatore che non contiene dati utili. Se l’elemento è un singolo intero, lo spazio dedicato alla gestione della lista è paragonabile a quello dei dati stessi. Se invece ogni nodo contiene un record ricco di campi, il peso del puntatore diventa trascurabile.

Lo stack come struttura dati LIFO

Lo stack è una struttura di tipo LIFO, Last In First Out: l’ultimo elemento inserito è il primo a uscire. È l’opposto della coda FIFO a cui siamo abituati nella vita quotidiana, e l’esempio più intuitivo è una pila di documenti, da cui si può prendere solo il foglio in cima.

Le operazioni fondamentali sono due:

• push, che inserisce un nuovo elemento in cima allo stack
• pop, che legge e rimuove l’elemento in cima

Proprio perché si lavora solo sulla testa, lo stack è la lista collegata concettualmente più semplice: niente inserimenti in mezzo, niente cancellazioni di elementi interni, niente ricerche. Questo lo rende il punto di partenza ideale per prendere confidenza con la catena di puntatori.

Push, pop e free: la gestione della memoria

Nella push si alloca un nuovo nodo con malloc, si verifica che l’allocazione sia andata a buon fine, si assegna il valore e si collega il nuovo elemento alla vecchia testa prima di aggiornare il puntatore al top. Nella pop si salva un riferimento temporaneo alla testa, si legge il valore, si sposta il top sull’elemento successivo e infine si libera la memoria con free.

Quest’ultimo passaggio è fondamentale: la memoria allocata dinamicamente che non usiamo più va restituita al sistema, che potrà assegnarla ad altre applicazioni o al nostro stesso programma in un secondo momento. Altrettanto importante è proteggere le funzioni dal caso dello stack vuoto, per evitare di dereferenziare un puntatore nullo.

Il puntatore a puntatore: l’insidia del C

Il punto più delicato della lezione è un classico del linguaggio C. Le funzioni push e pop devono modificare il puntatore alla testa della lista, non solo il dato a cui punta. Passando alla funzione il semplice puntatore, tutto sembra funzionare all’interno della funzione, ma al ritorno il chiamante si ritrova con il valore originale, e il compilatore non segnala nulla.

La soluzione è passare l’indirizzo del puntatore, cioè un puntatore a puntatore. Il fatto di partire già da un puntatore tende a confondere, ma il principio è lo stesso del passaggio per riferimento visto nelle lezioni dedicate ai puntatori. La funzione di stampa, che si limita a leggere la lista, può invece ricevere direttamente il puntatore alla testa.

Domande frequenti sulle liste collegate in C

Come si capisce che una lista collegata è finita?
L’ultimo elemento ha il puntatore al successivo impostato a NULL.

Perché le funzioni push e pop ricevono un puntatore a puntatore?
Perché devono modificare il valore del puntatore alla testa dello stack, che appartiene al chiamante.

Uno stack si può realizzare anche con un array?
Sì, ma si perde il vantaggio dell’allocazione dinamica, perché la memoria va dimensionata in anticipo.

Perché è importante chiamare free dopo una pop?
Per restituire al sistema la memoria non più utilizzata ed evitare di occupare risorse inutilmente.

Guarda la lezione

Nel video costruiamo lo stack passo dopo passo, con l’aiuto di animazioni che mostrano come si spostano i puntatori durante push e pop, e poi lo implementiamo in CLion, anche se tutto può essere replicato con GDB online. È la base su cui costruiremo le prossime lezioni, dove affronteremo le liste collegate più generali e l’inserimento di elementi in mezzo alla lista. Se state seguendo il corso di C, è una puntata da non saltare.