void eliminaTesta (elem*& lista) { if (lista != 0) { // puntatore temporaneo all'elemento da eliminare elem* p = lista; // la lista e` costituita ora dagli elementi // dal secondo all'ultimo lista = lista->next; // possiamo deallocare la memoria del primo elemento delete p; } }
Prima di procedere all'eliminazione dell'elemento di testa, bisogna accertarsi che la lista sia vuota; in caso affermativo è sufficiente uscire dalla funzione. Altrimenti, si definisce un puntatore al primo elemento della lista, si sposta il puntatore lista
al suo elemento successivo (nota: potrebbe anche andare a 0
, nel caso la lista sia costituita da un solo elemento), si rimuove l'elemento puntato da p
.
Come nel caso dell'inserzione, l'eliminazione dell'ultimo elemento di una lista è un'operazione un poco più complessa rispetto all'eliminazione in testa; infatti bisogna, con una procedura simile a quella per l'inserzione, cercare l'ultimo elemento scorrendo tutta la lista da sinistra a destra.
void eliminaCoda (elem*& lista) { // se la lista e` vuota la si lascia inalterata if (lista == 0) return; // se la lista e` costituita da un solo elemento // lo si elimina direttamente if (lista->next == 0) { delete lista; lista = 0; return; } // puntatori ausiliari che scorrono la lista da sx a dx // separati l'un l'altro da un solo elemento elem* p = lista; elem* q = lista->next; while (q->next != 0) { p = p->next; q = q->next; } // `q' ora e` l'ultimo elemento della lista // mentre `p' e` il penultimo p->next = 0; // chiude la lista delete q; }
La differenza fondamentale tra l'inserzione e l'eliminazione in coda è che, mentre nel primo caso basta un solo puntatore di scorrimento, nel secondo ce ne vogliono due; essi partono dai primi due elementi della lista, nel caso essa non sia vuota o costituita da un solo elemento, e la scorrono affiancati. Quando il campo next
del puntatore più avanzato è arrivato a fine corsa, basta eliminare l'ultimo elemento e fare in modo che il penultimo punti a 0
; l'utilizzo di due puntatori è molto comune nelle liste semplici, avendo esse un solo verso di percorrimento. Si consiglia di provare ad eseguire il programma seguente ``a mano'':
// ex7_7_5 void main() { elem* lista; inizializza (lista); generaLista (lista, 20, 5); stampa (lista, 5); eliminaTesta (lista); stampa (lista, 5); for (int i = 0; i < 4; i++) { eliminaCoda (lista); cout << "\n"; stampa (lista, 5); } }
esempio di output:
9 | 13 | 15 | 16 | 7 | |
13 | 15 | 16 | 7 | ||
13 | 15 | 16 | |||
13 | 15 | ||||
13 |