Le liste sono uno degli argomenti più delicati da trattare, per il semplice fatto che sono uno strumento potente e versatile, ma anche molto fragile. Basti pensare che l'uso delle liste permette di impostare programmi di ordinamento in modo molto efficiente (un esempio su tutti l'algoritmo MergeSort), ed offre quella dinamicità, tra l'altro tipica del C, di cui si può avere bisogno durante lo sviluppo di un programma.
Definizione di lista in C
Una lista non è altro che una collezione di elementi omogenei, ma, a differenza dell'array, occupa in memoria una posizione qualsiasi, che tra l'altro può cambiare dinamicamente durante l'utilizzo della lista stessa; inoltre la sua dimensione non è nota a priori e può variare nel tempo (l'opposto dell'array, in cui la dimensione è ben nota e non è modificabile). Una lista può contenere uno o più campi contenenti informazioni, e, necessariamente, deve contenere un puntatore per mezzo del quale è legato all'elemento successivo.
Come sono strutturate
La lista base ha un solo campo informazione ed un puntatore, come mostrato di seguito:
Elemento = informazione + puntatore
che, tradotto in codice, risulta essere:
struct elemento {
int inf;
struct elemento *pun;
}
Una particolarità delle liste (a differenza, ad esempio, degli array) è che sono costituite da due funzioni del C, le strutture ed i puntatori, quindi non sono un tipo di dato nuovo, basato su implementazioni particolari, ma sono il risultato di un uso sapiente di tali costrutti.
Come si è detto prima, una lista può contenere uno o più campi di informazione, che possono essere di tipo int (come nell'esempio), char, float, ecc.; mentre deve esserci sempre un campo che punta ad un altro elemento della lista, che è NULL se non ci sono altri elementi, mentre risulta essere una struttura elemento nel caso vi sia un successore. Per dichiarare una lista, basta scrivere (riferendosi alla struttura dichiarata precedentemente):
- struct elemento *lista;
che altro non è che un puntatore ad una struttura elemento, e come tale potrebbe essere inizializzata anche ad un valore NULL, che identificherebbe una lista vuota. In questo modo definiamo, quindi, una lista lineare, ovvero una lista che deve essere visitata (o scandita) in ordine, cioè dal primo elemento fino all'ultimo, che viene identificato perché punta a NULL. Da ricordare che, anche se nella sua rappresentazione, una lista risulta essere sequenziale, in realtà l'allocazione di memoria relativamente agli elementi è libera, cioè ogni volta che devo aggiungere un elemento alla lista, devo allocare la memoria relativa, connetterlo all'ultimo elemento ed inserirvi l'informazione. La rappresentazione grafica di un elemento della lista è la seguente:
mentre quella di una lista risulta essere come segue:
