The (Duel)Lists come usare le Linked List in C - pt.1

Armand d'Hubert: [rivolgendosi a Gabriel Feraud] Sono stato ai tuoi ordini per 15 anni... Secondo le regole dei duelli adesso la tua vita mi appartiene. Dichiarerò che sei morto. Se avrai mai a che fare con me, lo farai da uomo morto. Mi sono piegato alla tua nozione di onore per troppo tempo. Adesso tu ti piegherai alla mia.

(...una premessa: questo post è 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...)

The Duellists (I duellanti) è uno dei capolavori di Ridley Scott, ed è il suo film d'esordio (e che esordio!); racconta la storia di due ufficiali francesi (interpretati da Keith Carradine e Harvey Keitel) che si affrontano a duello in vari scenari europei durante le campagne napoleoniche, per ben quindici anni. È un film imperdibile! Ah, e visto che siamo in tema: vorrei ricordarvi che se qualcuno parla male delle linked list lo sfido a duello, quindi state attenti... Come avrete già intuito, in questo articolo parleremo di linked list!

...Cosa dicevi delle linked list?...

Da queste parti avevamo già affrontato (di striscio) il tema delle linked list, in due vecchi articoli, qui e qui. Ricordo anche che una volta giustificai l'argomento così:

"Per chi non le avesse mai usate, le linked-list non sono una frivolezza: sono una delle costruzioni più potenti della programmazione in generale (e del C in particolare). Chi lavora intensamente in C su progetti grandi e professionali finirà, prima o poi, con usarle: un motivo in più, quindi, per familiarizzare con la allocazione dinamica della memoria."

Ok, credo che la maniera migliore di presentare l'argomento sia un esempietto semplice semplice (ma, come sempre: funzionante!). Vai col codice!

// linklist.c - un programma di esempio sulle linked list
#include<stdlib.h>
#include<stdio.h>
// nodo di una linked list singola con campo dati
typedef struct snode {
    int data;
    struct snode *next;
} node_t;
// prototipi locali
void addNode(node_t **head, int data);
void appendNode(node_t **head, int data);
// funzione main
int main()
{
    // init lista vuota 1 e inserisce con addNode() 3 nodi con data = indice del loop
    node_t *head1 = NULL;
    for (int i = 0; i < 3; i++)
        addNode(&head1, i);
    // scorre la lista e stampa i valori
    node_t *myhead1 = head1;
    printf("myhead1=%p - metodo ADD\n", (void *)myhead1);
    while (myhead1) {
        printf("data=%d (myhead1=%p next=%p)\n", 
               myhead1->data, (void *)myhead1, (void *)myhead1->next);
        myhead1 = myhead1->next;
    }
    // init lista vuota 2 inserisce con appendNode() 3 nodi con data = indice del loop
    node_t *head2 = NULL;
    for (int i = 0; i < 3; i++)
        appendNode(&head2, i);
    // scorre la lista e stampa i valori
    node_t *myhead2 = head2;
    printf("myhead2=%p - metodo APPEND\n", (void *)myhead2);
    while (myhead2) {
        printf("data=%d (myhead2=%p next=%p)\n", 
               myhead2->data, (void *)myhead2, (void *)myhead2->next);
        myhead2 = myhead2->next;
    }
    return 0;
}
// addNode - alloca in testa a una lista un node con dati e pointer al prossimo elemento
void addNode(node_t **head, int data)
{
    // alloca un nuovo node
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = *head;
    // assegna head lista al nuovo node
    *head = node;
}
// appendNode - alloca in fondo a una lista un node con dati e pointer al prossimo elemento
void appendNode(node_t **head, int data)
{
    // alloca un nuovo node
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = NULL;
    // appende il nuovo node
    node_t *current = *head;
    if (current == NULL) {
        // caso speciale per lista vuota: assegna head lista al nuovo node
        *head = node;
    }
    else {
        // scorre la lista per trovare l'ultimo node
        while (current->next != NULL)
            current = current->next;
        // assegna all'ultimo node il nuovo node
        current->next = node;
    }
}

Cosa dire? Più elementare di così! Eppure funziona... Come si evince dagli abbondanti commenti per fare una linked list basta creare un punto di inizio (un "head") e aggiungere nodi con una semplicissima funzione che ho chiamato (in modo veramente originale) addNode(). Il segreto sta nella struttura del nodo, che deve sempre contenere un pointer al nodo successivo (ma va? Sarà mica per questo che si chiamano linked list?). Dato che c'ero ho anche aggiunto una funzione per appendere nodi, che è ugualmente utile. Ovviamente l'esempio fornito è abbastanza limitato: mancano le funzioni per cancellare i nodi, oppure per gestire la lista in modo doppio (double-linked-list), ecc. Ma sulla (solida) base fornita è possibile costruire, in modo relativamente semplice, tutte le estensioni che vogliamo.

Nel main() ho aggiunto un po' di tracce di log, che ci aiutano, durante l'esecuzione, a capire cosa succede quando aggiungiamo un nodo e quando, in alternativa, lo appendiamo. Il risultato finale è lo stesso (nell'esempio è una lista con tre nodi), ma la disposizione cambia: nel caso append  abbiamo una disposizione più logica dei nodi: la lista cresce in avanti, e ogni nuovo nodo è l'ultimo. Nel caso insert, invece, è la testa della lista che cambia ad ogni inserzione, e quindi, quando leggiamo i dati, li troviamo invertiti rispetto all'ordine di inserimento.

Entrambe le liste hanno usi validi (ad esempio una va meglio per creare code FIFO e l'altra va meglio per creare code LIFO) e, per applicazioni più sofisticate dove bisogna aggiungere/leggere/cancellare nodi in posizioni determinate si può decidere (quasi) indistintamente per una struttura o l'altra. Io normalmente uso il metodo append, che mi sembra più logico, anche se, lo riconosco, la funzione di append è un po' più complicata e meno immediata di quella di insert. Però la lista ordinata in avanti mi sembra più coerente e facile da maneggiare.

Compilando (con gli opportuni flag) ed eseguendo, il programma ci mostrerà questo log:

aldo@Linux $ gcc -Wall -Wextra -pedantic linklist.c -o linklist
aldo@Linux $ ./linklist
myhead1=0x5a2fd71412e0 - metodo ADD
data=2 (myhead1=0x5a2fd71412e0 next=0x5a2fd71412c0)
data=1 (myhead1=0x5a2fd71412c0 next=0x5a2fd71412a0)
data=0 (myhead1=0x5a2fd71412a0 next=(nil))
myhead2=0x5a2fd7141710 - metodo APPEND
data=0 (myhead2=0x5a2fd7141710 next=0x5a2fd7141730)
data=1 (myhead2=0x5a2fd7141730 next=0x5a2fd7141750)
data=2 (myhead2=0x5a2fd7141750 next=(nil))

che mi sembra inutile spiegare (parla da solo!). Come già accennato sopra, il codice presentato è solo un "buon inizio": in una applicazione reale bisognerà aggiungere un po' di funzioni accessorie per cercare, inserire e cancellare nodi. E, visto che usiamo delle malloc(3), bisognerà anche aggiungere, quando servono, le corrispondenti free(3)... Ma anzi, crepi l'avarizia! Farò una seconda parte dell'articolo aggiungendo quello che manca, ma sempre in maniera semplificata e ben comprensibile, eh!

Ok, ci sentiremo prossimamente con la seconda parte dell'articolo e, come sempre, vi ricordo di non trattenere il respiro nell'attesa (può nuocere gravemente alla salute...).

Ciao e al prossimo post!