Nell'ultima pagina si è vista una cosa che in apparenza contrasta con quello che è stato detto nel caso iterativo: infatti, passiamo la lista vuota a una funzione, e questo modifica la lista di cui quella passata era il resto. In altre parole, sappiamo che inserire in coda nel modo seguente non funziona:
void AggiungiCodaLista(TipoLista *pl, int e) {
TipoLista r;
r=*pl;
while(r->next!=NULL)
r=r->next;
InserisciTestaLista(&r, e);
}
Questo non funziona perchè la aggiunta in testa a r crea una nuova struttura il cui indirizzo viene messo in r, ma non viene messo nel campo next dell'ultima struttura della lista. La funzione non è corretta perchè porta troppo avanti il puntatore, per cui non abbiamo più la possibilità di modificare il campo next dell'ultima struttura.
D'altra parte, la funzione di sopra non è la versione iterativa della funzione ricorsiva di inserimento in lista. Infatti, la chiamata ricorsiva ha come argomento non il valore del campo next della prima struttura, ma il suo indirizzo. Infatti, la chiamata avviene passando come parametro &(*pl)->next. Questo è esattamente l'indirizzo del campo next della struttura. Questo significa che, quando viene fatta l'ultima chiamata ricorsiva, ossia quando il campo next vale NULL, non viene passato il valore NULL, ma viene passato l'indirizzo della variabile che contiene il valore NULL. Quando si inserisce in lista, abbiamo l'indirizzo del campo next dell'ultima struttura, e lo usiamo per mettere in questo campo l'indirizzo della nuova struttura che è stata creata.
Vediamo ora come si può effettuare l'inserimento in coda a una lista usando in modo iterativo il metodo di usare un puntatore al campo next. Il punto fondamentale è questo: la funzione riceve come parametro un puntatore a una variabile di tipo lista. Per evitare di avere un comportamento differente a seconda se l'elemento va inserito come primo o come successivo, facciamo la scansione, però facciamo sempre in modo tale che la variabile di scansione non sia di tipo lista, ma sia dello stesso tipo del parametro, ossia sia un puntatore a una variabile di tipo lista.
All'inizio la variabile pl contiene l'indirizzo della variabile di tipo lista. Portare avanti il puntatore significa metterci dentro l'indirizzo del resto della lista. In altre parole, la successiva variabile di tipo lista è (*pl)->next. In pl ci mettiamo non il valore di questa variabile, ma il suo indirizzo. Siamo all'ultima struttura quando *pl vale NULL, per cui usiamo questa condizione per uscire dal ciclo di scansione. Quando siamo fuori dal ciclo, possiamo aggiungere la nuova struttura, mettendo il suo indirizzo in *pl. Si noti che pl contiene l'indirizzo del campo next dell'ultima struttura della lista, per cui mettere un indirizzo in *pl equivale a metterlo nel campo next dell'ultima struttura.
La funzione, che insieme ad altre dello stesso genere è contenuta nel file puntpunt.c, è la seguente.
void AggiungiCodaLista(TipoLista *pl, int e) {
/* scansione */
while(*pl!=NULL)
pl=&(*pl)->next;
/* aggiunta */
*pl=malloc(sizeof(struct NodoLista));
(*pl)->val=e;
(*pl)->next=NULL;
}
Supponiamo di chiamare la funzione passando come parametri la lista (65 22 -90) e l'intero da inserire 3. La situazione iniziale è la seguente (dato che si passa l'indirizzo di una lista, *pl e l sono la stessa cosa).
Dato che *pl non vale NULL si porta avanti il puntatore. In questo caso, pl non contiene l'indirizzo di una struttura, ma l'indirizzo del solo campo next della struttura. Infatti, *pl contiene l'indirizzo della prima struttura, per cui (*pl)->val e (*pl)->next sono i due campi della prima struttura. L'espressione &(*pl)->next dà l'indirizzo del campo next della prima struttura.
Dato che *pl non vale NULL, si fa la stessa assegnazione pl=&(*pl)->next, il cui effetto è ancora quello di ``portare avanti'' il puntatore.
Dato che *pl non vale NULL, si porta ancora avanti il puntotore.
A questo punto, *pl vale NULL. Si fa la allocazione di una nuova struttura, e il suo indirizzo viene messo in *pl. Si noti che pl contiene l'indirizzo dell'ultima struttura della lista, per cui mettere qualcosa in *pl equivale a metterlo nel campo next dell'ultima struttura della lista. Quando mettiamo l'indirizzo della nuova struttura in *pl, lo stiamo mettendo nel campo next dell'ultima struttura della lista. Questo effettivamente crea una nuova struttura in coda alla lista.
A questo punto, possiamo riempire la struttura con i valori esatti (il numero da inserire e il valore NULL che chiude la lista).
Come si vede, la lista è stata modificata: un nuovo elemento è stato aggiunto in coda.
Il metodo del puntatore a puntatore presenta un vantaggio nel caso in cui la lista va modificata. Il vantaggio è che in qualsiasi momento della scansione (sia che siamo all'inizio, alla fine, o in mezzo alla lista) quello che abbiamo è sempre un puntatore a una variabile di tipo lista. Questo fa sí che si abbia un comportamento uniforme, ossia si devono fare le stesse cose sia che l'elemento vada inserito/cancellato all'inizio, in mezzo, oppure in coda. Il programma completo puntpunt.c contiene altre funzioni di inserimento e cancellazione che usano questo metodo.