La eliminazione dell'ultimo elemento di una lista può sembrare, a prima vista, un problema abbastanza semplice. Invece, presenta un serie di trabocchetti.
La prima cosa da fare è chiaramente quella di seguire i puntatori fino ad arrivare all'ultima struttura della lista, che è quella che va deallocata. Nel programma delultimo1.c usiamo un ciclo di scansione che termina solo quando il puntatore di scansione vale NULL. La lista viene passata per riferimento. Questo può non essere a prima vista chiaro, dal momento che la il puntatore deve comunque contenere l'indirizzo della prima struttura, sia prima che dopo la cancellazione. Esiste infatti un caso in cui questo non vale: se la lista ha un unico elemento, la cancellazione dell'ultimo equivale a mettere NULL nel puntatore. Quindi, il puntatore che prima conteneva l'indirizzo della prima struttura ora contiene NULL, per cui è stato modificato, e quindi va passato per riferimento.
/* prima versione: ERRATA */
void EliminaUltimoLista(TipoLista *pl) {
TipoLista r;
r=*pl;
while(r!=NULL)
r=r->next;
free(r);
r=NULL;
}
Il problema di questa funzione è evidente, se si pensa che dopo un ciclo la condizione del ciclo deve essere necessariamente falsa (se non ci sono break dentro il ciclo). Nel nostro caso, la condizione è r!=NULL; se questa è falsa allora r vale NULL. In altre parole, si esce dal ciclo solo quando r vale NULL. Si può quindi dire che il ciclo while equivale alla assegnazione r=NULL. È quindi chiaro che l'istruzione free(r) è equivalente a free(NULL), e che l'ultima istruzione della funzione, ossia r=NULL, non ha nessun effetto. Questa funzione lascia la lista inalterata.
Quello che ci serve non è ovviamente un puntatore con dentro NULL. Ci serve l'indirizzo dell'ultima struttura della lista, in modo da poterla deallocare. Se si va a vedere il ciclo di scansione della lista della funzione precedente, ci si accorge subito che esiste un momento in cui effettivamente r punta all'ultima struttura della lista, ossia contiene il suo indirizzo. Il problema del programma di sopra è che viene poi eseguita una ulteriore iterazione del ciclo, per cui questo valore che ci serve viene rimpiazzato da r->next, che vale NULL.
Occorre quindi fare in modo che non si vada avanti fino a che r vale NULL, ma occorre fermarsi quando r punta all'ultima struttura della lista. Per definizione, l'ultima struttura della lista è quella che contiene NULL nel campo next. Quindi, r punta all'ultima struttura della lista quando r->next vale NULL. Possiamo quindi modificare il ciclo, come viene fatto nel programma delultimo2.c, la cui funzione di eliminazione dell'ultimo elemento è riportata qui sotto.
/* seconda versione: ERRATA */
void EliminaUltimoLista(TipoLista *pl) {
TipoLista r;
r=*pl;
while(r->next!=NULL)
r=r->next;
free(r);
r=NULL;
}
Questa funzione realizza in parte quello che era richiesto, ma non è completamente corretta. Infatti, l'ultima struttura viene effettivamente deallocata, ma l'ultimo elemento non è stato realmente tolto dalla lista. Consideriamo infatti la evoluzione della memoria per una semplice lista di tre elementi.
A questo punto r->next vale effettivamente NULL, per cui si esce dal ciclo (si vede chiaramente dalle figure che non si esce prima, dato che prima r->next contiene indirizzi di altre strutture e non NULL). A questo punto viene liberata la memoria puntata da r, e in r si mette il valore NULL, per cui si ottiene una situazione di questo tipo:
Questa figura si ottiene semplicemente operando le due istruzioni free(r) e r=NULL sulla figura di sopra: dato che r punta all'ultima struttura, questa viene deallocata. Si mette poi NULL in r, e questo viene rappresentato graficamente con una croce.
È evidente che la lista finale non è fatta nel modo in cui ci si aspetta. Infatti, l'ultima struttura (quella che contiene 22) non ha NULL nel campo next. Al contrario, contiene l'indirizzo di una zona di memoria che è stata deallocata, per cui non sappiamo neanche con certezza cosa c'è in questa zona. Si noti che l'istruzione r=NULL mette il valore NULL nella variabile r e basta. Come per tutte le assegnazioni in C, quando si assegna un valore a una variabile, le altre non vengono infuenzate. Nel nostro caso, mettere NULL in r non lo mette anche nel campo next della penultima struttura.
Il problema è quindi quello di mettere il valore NULL nel campo next della struttura che rappresenta il penultimo elemento della lista (e che ora deve diventare l'ultimo). Per poter fare questa operazione, ci serve l'indirizzo della penultima struttura della lista. Infatti, dato questo indirizzo, possiamo usare (indirizzo penultima struttura)->next=NULL per chiudere in fondo la lista.
Riguardando ancora l'evoluzione della memoria durante la scansione, si vede chiaramente che esiste un momento in cui r contiene effettivamente questo indirizzo. Questo avviene esattamente alla fine della penultima iterazione del ciclo. Possiamo quindi dire che si esegue una iterazione di troppo. In particolare, r contiene l'indirizzo della penultima struttura solo quando r->next contiene l'indirizzo dell'ultima struttura. A sua volta, r->next è l'indirizzo dell'ultima struttura solo se r->next->next vale NULL. Possiamo quindi far terminare il ciclo non appena r->next->next vale NULL. A questo punto: possiamo deallocare l'ultima struttura, dato che conosciamo il suo indirizzo, che è r->next; possiamo mettere a NULL il campo next della penultima struttura, dato che l'indirizzo della penultima struttura è r, e quindi possiamo fare r->next=NULL. In altre parole, definiamo la funzione nel seguente modo. Il programma completo in cui questa funzione è inserita è delultimo3.c
void EliminaUltimoLista(TipoLista *pl) {
TipoLista r;
r=*pl;
while(r->next->next!=NULL)
r=r->next;
free(r->next);
r->next=NULL;
}
Rivediamo ora nel dettaglio la situazione della memoria dopo che r=r->next è stato eseguito per la prima volta:
A questo punto, r->next->next vale NULL, per cui si esce dal ciclo. Ora r punta alla penultima struttura, mentre r->next è l'indirizzo dell'ultima struttura. Quindi, possiamo fare la deallocazione dell'ultima struttura passando r->next alla funzione free. Per mettere NULL nel campo next della penultima struttura, basta fare r->next=NULL.
Quello che si ottiene è la seguente situazione (la zona di memoria deallocata ha un contenuto indefinito).
La lista rappresentata da *pl si ottiene semplicemente seguendo i puntatori, per cui il primo elemento è 65, mentre il secondo è 22, e non ci sono altri elementi (si arriva al puntatore NULL). Quindi, la lista che si ottiene è (65 22), che è effettivamente la lista originaria (65 22 -90) a cui è stato tolto l'ultimo elemento.
Tutto questo funziona bene se la lista ha tre elementi. È facile verificare che va ancora tutto bene se la lista contiene più elementi, oppure nel caso in cui ne contiene solo due (basta simulare il comportamento della funzione usando la notazione grafica). D'altra parte, la funzione va in errore nel caso in cui la lista contiene un elemento, oppure nessuno.
Supponiamo infatti che la lista contenga un solo elemento. In questo caso, abbiamo una situazione del genere:
In altre parole, r->next vale NULL, per cui r->next->next equivale a NULL->next, ossia (*NULL).next. Come è noto, l'operatore * produce un errore quando viene applicato a NULL. Il caso in cui la lista è vuota è simile, soltanto che r=*pl fa sí che in r venga messo il valore NULL.
La soluzione del problema è comunque abbastanza semplice. Infatti, solo due casi particolari (lista vuota e lista di un elemento) danno dei problemi. Quindi, possiamo semplicemente controllare questi due casi e agire di conseguenza. Nel caso di lista vuota (ossia *pl==NULL), possiamo semplicemente stampare un messaggio di errore. Nel caso di lista di un elemento (ossia (*pl)->next==NULL), dobbiamo deallocare questo elemento e mettere NULL in *pl e uscire dalla funzione.
Il programma finale delultimo4.c contiene quindi la seguente funzione.
void EliminaUltimoLista(TipoLista *pl) {
TipoLista r;
if(*pl==NULL) {
printf("Tentativo di eliminazione da lista vuota\n");
exit(1);
}
if((*pl)->next==NULL) {
free(*pl);
*pl=NULL;
return;
}
r=*pl;
while(r->next->next!=NULL)
r=r->next;
free(r->next);
r->next=NULL;
}
Si noti che il controllo *pl==NULL viene fatto prima del controllo (*pl)->next==NULL. Questo è necessario. Se si prova a mettere prima il controllo (*pl)->next==NULL, e la lista è vuota, questo equivale a verificare NULL->next==NULL, ossia è un accesso a *NULL, che genera un errore. Seguendo invece l'ordine della funzione sopra, nel caso in cui la lista è vuota *pl vale NULL, per cui si esegue la prima istruzione condizionale e non si arriva alla seconda.