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:
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
mentre quella di una lista risulta essere come segue:
