Definizione di Lista in informatica con implementazione in C

In informatica, con il termine lista si indica un insieme finito di  dati nel quale è  definita una  legge di ordinamento, ossia un insieme per il quale è stabilita una corrispondenza biunivoca tra i suoi elementi e l’insieme dei primi n  numeri naturali. In  base a  questa legge, è possibile stabilire quale è il  primo elemento di  questo insieme e  quale l’ultimo ed è inoltre possibile stabilire quale, tra due elementi qualsiasi dell’insieme, precede l’altro e quale segue. La caratteristica principale di una lista è nell’accesso ai suoi elementi: infatti, l’accesso ad un elemento qualsiasi di una lista avviene tramite  una ricerca sequenziale a  partire dal primo elemento della lista  per finire all’elemento considerato. Come vedremo, altre strutture  dati  come  la “pila” o la “matrice” presentano un metodo di accesso   diverso.

Esempio semplicissimo di lista è un normale testo letterario: in questo caso, gli elementi che costituiscono l’insieme sono le singole parole e i segni di  interpunzione, mentre l’ordinamento è definito dalla posizione fisica che gli elementi occupano nel testo. Un tipo particolare di lista è proprio la stringa: si tratta di una lista i cui elementi componenti sono caratteri di un determinato alfabeto. Gli elementi di una lista possono essere indicati con una notazione del tipo A1, A2, …, Ai-1, Ai, Ai+1, …, An-1, An che mette in rilievo la loro sequenzialità. Tuttavia questo tipo di notazione non deve indurre a pensare che l’accesso all’elemento Ai avvenga in base all’indice, ma, come detto prima, esso avviene in modo sequenziale a partire dall’elemento A1.

Se il numero dei dati che compongono una lista  rimane  costante  nel  tempo, allora si parla di lista a lunghezza fissa; se invece il numero di dati cambia (a seguito di operazioni di inserimento o di cancellazione), allora si parla di lista a lunghezza variabile. Le liste a  lunghezza variabile sono quelle più usate e  più interessanti dal punto  di vista applicativo: questa loro caratteristica fa sì che le liste vengano considerate strutture di dati di tipo dinamico (in seguito si tornerà su questa   definizione).

Su di una lista possono essere eseguite  due  diverse categorie di  operazioni: ci sono operazioni globali che interessano tutti gli elementi della lista e operazioni locali che interessano invece i singoli elementi della lista stessa. Tra le operazioni globali c’è per esempio la completa fusione di due liste in una sola, oppure la suddivisione di una lista in più parti o anche l’ordinamento degli elementi della lista secondo un ordine differente da quello iniziale e così   via.

Tra le operazioni locali, distinguiamo inviamo le seguenti operazioni fondamentali:

• l’accesso ad un elemento per determinarne il “valore” oppure per modificarlo;
• l’inserimento di un nuovo elemento tra altri due elementi, oppure all’inizio o alla fine della lista;
• l’eliminazione di un elemento, magari quello iniziale o quello finale.

Infine, si vuole ricordare che la nozione di lista può essere ulteriormente generalizzata: si possono infatti considerare liste i cui elementi sono a loro volta liste con elementi e così via.

Implementazione in C

Definiamo un nodo di elenco collegato:

typedef struct node {
    int val;
    struct node * next;
} node_t;

Si noti che stiamo definendo la struttura in modo ricorsivo, cosa possibile in C. Diamo un nome al nostro tipo di nodo node_t.

Ora possiamo usare i nodi. Creiamo una variabile locale che punti al primo elemento della lista (chiamato head).

node_t * head = NULL;
head = (node_t *) malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;

Abbiamo appena creato la prima variabile nell’elenco. Dobbiamo impostare il valore e l’elemento successivo deve essere vuoto, se vogliamo finire di popolare l’elenco. Notare che dovremmo sempre controllare se malloc ha restituito un valore NULL o meno.

Per aggiungere una variabile alla fine dell’elenco, possiamo semplicemente continuare ad avanzare al puntatore successivo:

node_t * head = NULL;
head = (node_t *) malloc(sizeof(node_t));
head->val = 1;
head->next = (node_t *) malloc(sizeof(node_t));
head->next->val = 2;
head->next->next = NULL;

Questo può andare avanti all’infinito, ma ciò che dovremmo effettivamente fare è avanzare all’ultimo elemento dell’elenco, finché la nextvariabile non sarà NULL.

Iterando su un elenco

Creiamo una funzione che stampa tutti gli elementi di un elenco. Per fare ciò, dobbiamo utilizzare un currentpuntatore che terrà traccia del nodo che stiamo attualmente stampando. Dopo aver stampato il valore del nodo, impostiamo il current puntatore al nodo successivo e stampiamo di nuovo, fino a quando non abbiamo raggiunto la fine della lista (il nodo successivo è NULL).

void print_list(node_t * head) {
    node_t * current = head;

    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;
    }
}