void insTesta (elem*& lista, int info) { lista = new elem (info, lista); }Gli argomenti passati sono la lista alla quale aggiungere un elemento, e il campo informazione di esso; l'inserzione avviene con un solo statement: si assegna al puntatore lista (attenzione: passato per riferimento!) il valore di un nuovo elemento avente l'informazione
info
e che punta al suo valore. Vediamo cosa succede in realtà nel seguente esempio:
// ex7_7_2.cpp // si copino in questo punto le definizioni // della struttura `elem' e della funzione `insTesta' void main() { elem* lista = 0; // si metta SEMPRE a zero una lista vuota insTesta (lista, 2); insTesta (lista, 5); }Inizialmente creiamo una lista vuota, la quale è costituita da un puntatore a
0
; si faccia bene attenzione a mettere sempre a zero una nuova lista, magari utilizzando la seguente banale funzione, da chiamare subito dopo avere definito il puntatore lista
:
void inizializza (elem*& lista) { lista = 0; }Dopo avere inizializzato la lista, chiamiamo per la prima volta la funzione
insTesta
su di essa, passando l'intero 2
come informazione: prima di tutto viene creato un nuovo elemento, i cui campi vengono immediatamente inizializzati con il valore di info
e con il puntatore lista
, che vale al momento 0
. Tale nuovo elemento avrà un indirizzo, il quale viene tornato dall'operatore new e assegnato a lista
, che dunque punta al primo (e per ora unico) elemento. Quando chiamiamo per la seconda volta la funzione insTesta
su lista
, ripetiamo le medesime operazioni appena elencate, con l'unica eccezione che il puntatore nel neonato elemento è riferito non a 0
ma all'elemento preesistente. Per meglio convincersi del funzionamento di tale meccanismo, si consiglia calorosamente di eseguire qualche prova ``su carta'' di inserimenti su liste vuote e non.
L'inserzione in testa presenta un notevole svantaggio: i dati risultano inseriti in ordine inverso rispetto a quello con il quale li si immette; conviene allora spesso eseguire delle inserzioni in coda, cioè aggiungere ogni nuovo elemento alla fine della lista. Tale procedura è un poco più articolata perché, mentre sappiamo bene dove inizia una lista, non possiamo immaginare dove essa termini se non la scorriamo completamente da sinistra a destra (immaginiamo sempre di avere la testa all'estrema sinistra e la coda all'estrema destra). Ricordiamo che la fine della lista è segnalata dal puntatore next
messo a 0
:
void insCoda (elem*& lista, int info) { // separiamo il caso in cui la lista sia vuota // per il quale basta inserire l'elemento in testa if (lista == 0) { insTesta (lista, info); return; } // puntatore ausiliatio di scorrimento elem* p = lista; // scorriamo la lista fino a quando l'elemento // successivo a `p' e` non nullo while (p->next != 0) p = p->next; // passa alla cella successiva // quando usciamo dal while, vuol dire che // ci troviamo sull'ultimo elemento // al quale dobbiamo farne seguire un altro // contenente `info' p->next = new elem (info, 0); // ovviamente l'ultimo elemento deve puntare a 0 }Non ci si lasci spaventare dalla lunghezza di questa funzione: in realtà essa è molto semplice, e presenta inoltre numerosi commenti. La prima operazione da effettuare è verificare se la lista è vuota: in caso affermativo bisogna operare una strategia a parte, che consiste semplicemente nell'inserire il nostro elemento in testa. Trattare a parte i casi particolari (nessun elemento, un solo elemento) è sempre fondamentale quando si lavora con le liste. Se la lista non è vuota, allora creiamo un puntatore ausiliario, che indichiamo con il nome
p
, che ci permetterà di scorrere la lista da sinistra a destra; infatti assegnamo al puntatore p
il valore di lista
, che è l'indirizzo del primo elemento, e lo facciamo ``proseguire'' tramite il comando p = p->next
fino a che esso non si trova sull'ultimo elemento della lista, ovvero fino a quando il suo campo next
è non-zero. A questo punto basta creare un nuovo elemento che punti a 0
, siccome esso diventerà l'elemento terminale della lista, e che abbia il campo dati uguale a info
, e assegnare il suo indirizzo all'ex-elemento terminale, cioè p
.