Le Liste

Nel capitolo sull’allocazione dinamica abbiamo detto che è possibile allocare dinamicamente la memoria per delle variabili. Questo risulta molto utile, se non indispensabile, per la creazione di STRUTTURE DINAMICHE, come liste (delle quali parleremo in questo capitolo), alberi e grafi.

Le liste concatenate consistono fondamentalmente in una catena di srutture chiamate NODI, ognuna delle quali contiene un campo dove ci possono essere delle informazioni e un campo che contiene il puntatore al nodo successivo.

Le liste sono delle strutture molto più flessibili degli array. Infatti negli array noi non possiamo inserire o cancellare particolari elementi dal loro interno. Con le liste invece si. A discapito delle liste però, c’è il fatto che viene persa la possibilità di accedere casualmente ad un elemento di esse, se non dopo aver effettuato una VISITA delle lista. Inoltre c’è da considerare che per una lista, accedere ad un nodo più vicino alla sua TESTA, è un’operazione veloce. Mentre se il nodo al quale si vuole accedere è lontano dalla testa, ciò richiede più tempo. Invece per l’array il tempo di accesso è lo stesso indipendentemente dalla posizione del dato ricercato.

DICHIARAZIONE DI UN TIPO NODO

Per la creazione di una lista concatenata, prima di tutto abbiamo bisogno, di una struct che rappresenti un singolo nodo delle lista. Per esempio, facciamo il caso in cui il nodo contenga un intero e un puntatore al nodo successivo della lista. Dichiareremo la struttura nodo così:

struct numero{ int valore;                            //Valore sarà il dato contenuto nel nodo

struct numero *p_next;};   // *p_next è il puntatore al nodo successivo della lista

ATTENZIONE: E’ fondamentale che *p_next sia un puntatore autoreferenziante in quanto deve puntare alla struttura stessa. Infatti è stato dichiarato di tipo struct numero. Ovvero dello stesso tipo della struct.

Adesso abbiamo dichiarato la struttura numero, ma dobbiamo ovviamente tenere traccia del punto dove la lista ha inizio, e per creare una lista vuota ad esempio, possiamo scrivere:

struct numero *testa=NULL

In questo modo abbiamo dichiarato una variabile che punta sempre al primo nodo della lista, che però in questo caso è vuota, e abbiamo scritto =NULL .

CREARE UN NUOVO NODO

Quando costruiamo una lista, ci sono tre passi fondamentali per la creazione di un nuovo nodo da inserire:

1. Allocare memoria per un nuovo nodo da inserire
2. Salvare i dati di quel nodo
3. Inserirlo facendo gli opportuni assegnamenti  in modo che il nuovo nodo venga concatenato ai nodi precedente e successore

Partiamo dal primo passo:

Quando creiamo un nodo abbiamo bisogno di una variabile di appoggio, o temporanea che punti a questo file fino a quando non lo inseriamo in lista. ESEMPIO: struct numero *nuovo;

Utilizzeremo la funzione malloc o calloc per allocare memoria:

nuovo=malloc(sizeof(struct numero));

oppure

nuovo=calloc(1,sizeof(struct numero));  /*ATTENZIONE AL SIZEOF!! DEVE CONTENERE IL TIPO                                                                            DI DATO CHE DEVE ESSERE ALLOCATO, NON IL   NOME DELLA VARIABILE*/

Successivamente possiamo salvare un dato nel membro valore del nuovo nodo:

(*nuovo).valore=2;

Per conferire maggiore leggibilità e scorrevolezza al programma, il C, visto che l’accesso di un membro di una struttura è un’operazione importantissima, mette a disposizione un operatore fatto apposta che è la “freccetta”, composta dal trattino e il simbolo di minore: -> . Quindi possiamo trasformare la la scrittura di sopra in:

nuovo->valore=2;

Nulla ci vieta di assegnare alla variabile valore, un numero tramite scanf, come:

scanf(“%d”,&nuovo->valore);   /*Non vi meravigliate se è stata messa la & commerciale! Anche se nuovo è un puntatore, senza la & passeremmo alla scanf il valore di nuovo->valore che è un intero!*/

OPERAZIONI EFFETTUABILI SU UNA LISTA CONCATENATA

Come vi dicevo prima, le liste sono molto più flessibili rispetto agli array perchè è possibile inserire elementi in mezzo, in testa, alla fine di esse. Mentre per un array ciò non è possibile.

1. Inserimento in testa: Considerando la struct precedentemente dichiarata, la variabile puntatore “nuovo” sta puntando al nodo che dovrà essere inserito, e la variabile puntatore “testa” sta puntando al primo nodo delle lista. Per l’inserimento in testa abbiamo bisogno di pochissime istruzioni, precisamente..due!! Ovvero:nuovo->p_next=testa; (in questo modo abbiamo modificato il membro p_next del nuovo nodo in modo che punti a quello che era l’inizio delle testa) e poi: testa=nuovo; Abbiamo fatto in modo che “testa” punti al nuovo nodo.
2. Eliminazione in testa: L’eliminazione in testa, come l’inserimento, è molto semplice. Dobbiamo fare in modo semplicemente che la testa punti al nodo successivo, al nodo che abbiamo intenzione di eliminare, in modo tale da bypassarlo
3. Eliminazione in un punto qualsiasi: L’eliminazione nel mezzo di una lista è un operazione abbastanza semplice. Essa coinvolge tre passi: localizzare il nodo da cancellare, modificare opportunamente i campi puntatori in modo da bypassare il nodo che è stato eliminato, invocare la funzione free( ) che libera la memoria allocata precedentemente per quel nodo che ora dovremo eliminare. Localizzare il nodo può sembrare un operazione stupida, ma vi assicuro che non lo è. E’ possibile effettuarla con un ciclo while o un ciclo for. Sono praticamente la stessa cosa, ma io preferisco il for perchè è molto flessibile. Supponiamo io stia cercando un nodo. Mi servono due puntatori: un puntatore al nodo precedente (che chiameremo *precedente) e uno che punti al nodo corrente (che chiamerò, senza troppa fantasia, *corrente). *testa, come sappiamo punterà alla testa della lista e n è l’intero che deve essere eliminato. (STO SEMPRE CONSIDERANDO LA STRUCT DI PRIMA). Potremo scrivere il for in questo modo:                     for (corrente=testa, precedente=NULL ; corrente!=NULL && corrente->valore!=n ; precedente=corrente, corrente=corrente->p_next); Quando questo ciclo terminerà, corrente punterà al nodo che deve essere eliminato e precedente punterà al nodo precedente se c’è.

Le funzioni per inserimento in fondo ad una lista ed eliminazione in fondo ad una lista, seguono la stessa logica, modificate opportunamente i campi dei puntatori e avrete fatto!