Eliminazione del primo elemento di una lista

Finora abbiamo visto come si crea una lista, come si aggiungono elementi, e come si scandisce (abbiamo visto solo la stampa). Ora vediamo come si fa a cancellare gli elementi di una lista. Il caso più semplice, che è quello che vediamo in questa pagina, è la cancellazione del primo elemento di una lista.

Iniziamo a vedere come è fatta le memoria prima della cancellazione, e come deve essere fatta dopo.


Si noti che la prima struttura della lista non è più necessaria, e quindi va deallocata usando la funzione free.

Si vede chiaramente dalla figura che la posizione della freccia che parte da l deve essere modificata. Infatti, non deve più puntare alla prima struttura della lista, ma alla seconda. Spostare la freccia sul grafico equivale a cambiare il valore di l. In particolare, dentro l dobbiamo mettere l'indirizzo della seconda struttura della lista. Dal primo grafico risulta anche evidente che il campo next della prima struttura della lista contiene l'indirizzo della seconda struttura. Quindi, per ottenere lo spostamento della freccia, occorre copiare il valore di l->next in l. Il meccanismo più semplice per eliminare il primo elemento è quello di fare l=l->next. Questo modifica la situazione iniziale in questo modo:

Questa figura si ottiene dalla considerazione che fare l'assegnamento fra puntatori significa copiare l'indirizzo scritto in un puntatore nell'altro, e questo equivale a modificare la freccia in modo che abbia la punta nella posizione in cui si trova la punta dell'altra.

Da questa figura si capisce chiaramente che:

  1. la lista rappresentata da l è ora (22 -90). Infatti, il primo elemento della lista è quello che si trova nella struttura puntata da l, e questa struttura contiene 22 e un puntatore che punta a un'altra struttura che contiene -90 e NULL;
  2. la struttura che contiene il valore 65 non è più necessaria. Infatti, partendo da l e seguendo i puntatori, non si arriva mai a questa struttura.

Si ricordi che la disposizione grafica delle strutture non ha importanza: la lista è quella che si ottiene seguendo i puntatori, ossia le freccie. Eventuali strutture che si trovano al di fuori di questo percorso non fanno comunque parte della lista.

La struttura che contiene 65 non viene più usata, per cui occupa memoria senza motivo. È quindi bene deallocare la memoria. Per deallocare la memoria è necessario passare alla funzione free l'indirizzo iniziale della zona, in questo caso l'indirizzo della struttura. Il problema è che, avendo solo il valore di l, non riusciamo a risalire a questo indirizzo. Se per esempio la funzione di cancellazione del primo elemento è stata realizzata con una funzione, a questa passiamo solo il valore di l. Una volta che abbiamo fatto l=l->next non abbiamo nessun modo per risalire all'indirizzo della prima struttura (basta guardare la figura: possiamo capire gli indirizzi della varie strutture solo seguendo le freccie a partire da l, ma in questo modo non arriviamo mai alla prima struttura).

Se però guardiamo la prima figura, quella che dice lo stato della memoria prima della cancellazione, vediamo che l'indirizzo della prima struttura è scritto in l. È stata l'istruzione l=l->next che ci ha fatto perdere questa informazione. Dal momento che l'indirizzo che ci serve per fare la free è scritto nella variabile l all'inizio, possiamo copiare questo valore in un'altra variabile prima di fare l=l->next.

Facciamo quindi una sequenza di questo tipo: primo, memorizziamo il valore di l in una variabile temporanea s; secondo, mettiamo in l l'indirizzo della seconda struttura con l=l->next; terzo, liberiamo la memoria occupata dalla prima struttura: dato che il suo indirizzo sta scritto in s, questo si può fare con free(s).

s=l;

l=l->next;

free(s);

L'esecuzione di queste tre istruzioni produce la seguente evoluzione della memoria.




A prima vista, può sembrare che questo codice si possa semplificare usando la seguente soluzione:

		/* CODICE ERRATO */
free(l);
l=l->next;

Questa soluzione è sbagliata. Infatti, una volta che la zona di memoria puntata da l è stata deallocata con free(l), il suo contenuto è indefinito. Per quello che è possibile sapere, la zona di memoria potrebbe anche essere stata riempita di zeri. In questo caso, l'operazione di andare a prendere il secondo campo l->next è un errore di programmazione, perchè si sta accedendo a una zona di memoria il cui contenuto non è garantito. Quindi, dopo l=l->next il contenuto di l (ossia l'indirizzo contenuto in l) è indefinito.

In alcuni casi, questo frammento di codice può anche funzionare. Questo però è un problema più che un vantaggio, perchè diventa molto difficile capire perchè il programma in alcuni casi non funziona.


Scriviamo ora una funzione che realizza la cancellazione del primo elemento di una lista. Questa funzione riceve come parametro il puntatore alla prima struttura della lista. Dai grafici di sopra è abbastanza evidente che il puntatore al primo elemento della struttura deve essere modificato (dopo la esecuzione della funzione deve contenere l'indirizzo della seconda struttura e non della prima). Quindi, va passato per riferimento. Questo si fa come al solito: al posto di l si mette *pl nella intestazione e nel corpo della funzione, e il programma chiamante usa &l come parametro.

Per il resto, il corpo della procedura è esattamente identico al frammento di codice che elimina il primo elemento di una lista:

void EliminaTestaLista(TipoLista *pl) {
  TipoLista s;

  s=*pl;

  *pl=(*pl)->next;

  free(s);
}

Il programma delprimo1.c è un esempio di uso di questa funzione: si legge una lista da file, e si cancellano i primi due elementi.

La funzione definita sopra funziona, se la lista non è vuota. Nel caso in cui la lista sia inizialmente vuota, si genera un errore in esecuzione. Infatti, l'istruzione *pl=(*pl)->next tenta di accedere a una struttura il cui indirizzo si trova in *pl. Nel caso in cui la lista è vuota, *pl contiene NULL, e tentare di accedere alla memoria puntata da NULL genera un errore.

Per evitare questi problemi, possiamo aggiungere alla funzione un test per verificare se la lista è vuota. Nel caso in cui la lista è vuota possiamo comporarci in diversi modi: stampare un messaggio di errore ed eventualmente uscire, oppure semplicemente assumere che eliminare il primo elemento da una lista vuota genera la lista vuota. Nel programma delprimo2.c usiamo la funzione in cui è stata adottata la prima scelta.

void EliminaTestaLista(TipoLista *pl) {
  TipoLista s;

  if(*pl==NULL) {
    printf("Tentativo di eliminazione testa da lista vuota\n");
    exit(1);
  }

  s=*pl;

  *pl=(*pl)->next;

  free(s);
}