dottor Jacquin: [rivolgendosi a Armand d'Hubert] Ho studiato a fondo l'uomo militare, gli ho letteralmente scrutato il cervello; ma il mio fato è quello di rabberciarlo di continuo senza avere alcuna idea di come funzioni..
(...una premessa: questo post (parte 2 di 3) è un remake di un mio vecchio post. Ma, anche se tratta lo stesso argomento, amplia e perfeziona un po' il discorso è mi è sembrato il caso di riproporlo. Leggete e mi direte...)
Allora: dove eravamo rimasti? Ah, si: le linked list. Nell'ultimo articolo avevo spiegato l'importanza di questi oggetti nel nostro linguaggio preferito e avevo anche fornito un esempio molto elementare (ma funzionale!). È giunto ora il momento di estendere un po' l'esempio (l'avevo promesso, e "ogni promessa è debito"). Leggete attentamente l'articolo perché l'argomento è moderatamente intricato e intrigante e, mi raccomando, non fate come il dottor Jacquin di The Duellists (I duellanti) di Ridley Scott: se qualcosa non vi è chiaro provate e riprovate fino a trovare il bandolo della matassa, non vi arrendete. Come avrete già intuito, anche in questo articolo parleremo di linked list!
![]() |
| ...Ci risiamo... |
- findNode() - cerca un node specifico. In questo esempio il node è identificato dal campo "data" che funge anche da identificativo (vedi note più avanti).
- delNode() - cancella un node specifico (e libera la memoria). In questo esempio il node è identificato dal campo "data" che funge anche da identificativo (vedi note più avanti).
- cleanList() - cancella l'intera lista (e libera la memoria).
- printList() - mostra il contenuto dell'intera lista.
Ebbene si, credo che sia giunto il momento di mostrare la nuova versione del programma. Vai col codice!
// linklist.c - un programma di esempio sulle linked list#include <stdlib.h>#include <stdio.h>// node di una linked list singola con campo datitypedef struct snode {int data;struct snode *next;} node_t;// prototipi localivoid addNode(node_t **head, int data);void appendNode(node_t **head, int data);void findNode(node_t **head, int data);void delNode(node_t **head, int data);void cleanList(node_t **head);void printList(node_t **head);// funzione mainint main(){// init lista vuota e inserisceo con addNode() 5 nodi con data = indice del loopnode_t *head = NULL;for (int i = 0; i < 5; i++)addNode(&head, i);// mostro la listaprintList(&head);// cerco un node: quello con data == 3findNode(&head, 3);// cancello un node: quello con data == 3delNode(&head, 3);// cerco il node cancellato (quello con data == 3)findNode(&head, 3);// mostro di nuovo la lista: deve mancare il node con data == 3printList(&head);// cancello l'intera listacleanList(&head);// mostro di nuovo la lista: deve essere vuotaprintList(&head);return 0;}// addNode - alloca in testa a una lista un node con dati e pointer al prossimo elementovoid addNode(node_t **head, int data){// alloco un nuovo nodenode_t *node = malloc(sizeof(node_t));node->data = data;node->next = *head;// assegno la head lista al nuovo node*head = node;}// appendNode - alloca in fondo a una lista un node con dati e pointer al prossimo elementovoid appendNode(node_t **head, int data){// alloca un nuovo nodenode_t *node = malloc(sizeof(node_t));node->data = data;node->next = NULL;// appende il nuovo nodenode_t *current = *head;if (current == NULL) {// caso speciale per lista vuota: assegna head lista al nuovo node*head = node;}else {// scorro la lista per trovare l'ultimo nodewhile (current->next != NULL)current = current->next;// assegno all'ultimo node il nuovo nodecurrent->next = node;}}// findNode - trova un node nella listavoid findNode(node_t **head, int data){// scorro la listanode_t *current = *head;while (current) {// cerco il node con il <data> corrispondenteif (current->data == data) {// node trovato!printf("node trovato: data=%d (myhead=%p next=%p)\n",current->data, (void *)current, (void *)current->next);return;}// passo al priossimo nodecurrent = current->next;}// node non trovato!printf("node con data=%d non trovato!\n\n", data);return;}// delNode - rimuove un node dalla listavoid delNode(node_t **head, int data){// scorro la listanode_t *current = *head;node_t *previous = NULL;while (current) {// cerco il node con il <data> corrispondenteif (current->data == data) {// modifico il riferimento <next> per eliminare dall'elenco il node trovatoif (previous)previous->next = current->next;else*head = current->next;// cancello il node e ritornoprintf("%s: cancello data=%d (current=%p next=%p)\n",__func__, current->data, (void *)current, (void *)current->next);free(current);return;}// passo al prossimo nodeprevious = current;current = current->next;}}// cleanList - reset completo della listavoid cleanList(node_t **head){// scorro la listanode_t *current = *head;node_t *next;while (current) {// salvo il node successivo prima di liberare quello correntenext = current->next;// cancello il nodeprintf("%s: cancello data=%d (current=%p next=%p)\n",__func__, current->data, (void *)current, (void *)current->next);free(current);// mi sposto sul node successivocurrent = next;}// imposto la head lista a NULL per indicare che la lista è vuota*head = NULL;}// printList - mostra la listavoid printList(node_t **head){// scorro la lista e stampo i valorinode_t *current = *head;printf("%s: lista in %p - elementi contenuti:\n", __func__, (void *)current);while (current) {printf("data=%d (current=%p next=%p)\n",current->data, (void *)current, (void *)current->next);current = current->next;}printf("\n");}
Come avrete notato è molto simile a quello dell'ultimo articolo ma, anche grazie alla nuova funzione printList(), il codice è un po' più lineare e leggibile. Credo che grazie ai commenti esagerati sia tutto molto chiaro, ma qualche nota da aggiungere c'è: questo è un esempio molto semplificato, quindi non è il caso di chiedersi a che serve una linked list con un solo dato (che è, oltretutto, un semplice int): evidentemente una linked list può contenere (oltre all'indispensabile campo "next") quanti altri campi semplici si vogliono, oppure un solo campo data che può essere, a sua volta, una struttura complessa, oppure più strutture complesse, ecc.
Però la architettura del codice rimarrá la stessa, semplicemente sarà un po' più complicato aggiungere e cancellare elementi nel caso che ci siano altre malloc(3)/free(3) da fare, ma niente di cui preoccuparsi. E anche la findNode() e la delNode() potrebbero cercare un semplice campo identificativo oppure cercare una struttura complessa: il meccanismo si può semplificare o complicare a piacere, ma alla fin fine l'architettura di base è quella che vi ho appena mostrato.
Ah, un'ultima cosa, e scusatemi se mi ripeto: quello sopra è un esempio molto semplificato e, ovviamente, se si vorrà usare come codice di produzione bisognerà aggiungere gli opportuni controlli (specialmente sull'esito delle malloc(3)) e gli opportuni trattamenti degli errori delle funzioni (che dovranno ritornare valori significativi invece di essere void come nell'esempio). Non dimenticatevene mai!
Cosa manca per finire l'articolo? Ah, si, compilare ed eseguire. Vediamo un po:
aldo@Linux $ gcc -Wall -Wextra -pedantic linklist.c -o linklistaldo@Linux $ ./linklistprintList: lista in 0x56a7786e6320 - elementi contenuti:data=4 (current=0x56a7786e6320 next=0x56a7786e6300)data=3 (current=0x56a7786e6300 next=0x56a7786e62e0)data=2 (current=0x56a7786e62e0 next=0x56a7786e62c0)data=1 (current=0x56a7786e62c0 next=0x56a7786e62a0)data=0 (current=0x56a7786e62a0 next=(nil))node trovato: data=3 (myhead=0x56a7786e6300 next=0x56a7786e62e0)delNode: cancello data=3 (current=0x56a7786e6300 next=0x56a7786e62e0)node con data=3 non trovato!printList: lista in 0x56a7786e6320 - elementi contenuti:data=4 (current=0x56a7786e6320 next=0x56a7786e62e0)data=2 (current=0x56a7786e62e0 next=0x56a7786e62c0)data=1 (current=0x56a7786e62c0 next=0x56a7786e62a0)data=0 (current=0x56a7786e62a0 next=(nil))cleanList: cancello data=4 (current=0x56a7786e6320 next=0x56a7786e62e0)cleanList: cancello data=2 (current=0x56a7786e62e0 next=0x56a7786e62c0)cleanList: cancello data=1 (current=0x56a7786e62c0 next=0x56a7786e62a0)cleanList: cancello data=0 (current=0x56a7786e62a0 next=(nil))printList: lista in (nil) - elementi contenuti:
Beh, i risultati parlano chiaro, no? Corrispondono ai passi indicati nel codice:
- Creo una lista di cinque elementi e stampo il contenuto (indirizzi di memoria inclusi! Per chi ha dubbi sul funzionamento delle linked list...)
- Cerco un node (in questo caso quello con data == 3) e mostro cosa ho trovato.
- Cancello un node (in questo caso quello con data == 3).
- Cerco un node (in questo caso quello con data == 3) e mostro che non l'ho trovato (certo che se lo trovavo era un problema...).
- Mostro di nuovo la lista: deve mancare il node con data == 3 (speriamo...)
- Cancello l'intera lista e stampo il contenuto: non deve apparire nulla (di nuovo: speriamo...).
Funziona!
Quando ho cominciato a scrivere lo scorso articolo pensavo a una cosa semplice semplice in una sola parte e via... poi mi è sembrato il caso di aggiungere questa seconda parte e... ma si, prolungherò ulteriormente la descrizione: nel prossimo articolo parlerò di doubly linked list! Così mi tolgo il pensiero e non dovrò ritornare sull'argomento chissà quando. Restate sintonizzati!
Ciao, e al prossimo post!


