Nei titoli e nei testi troverete qualche rimando cinematografico (ebbene si, sono un cinefilo). Se non vi interessano fate finta di non vederli, già che non sono fondamentali per la comprensione dei post...

Di questo blog ho mandato avanti, fino a Settembre 2018, anche una versione in Spagnolo. Potete trovarla su El arte de la programación en C. Buona lettura.

sabato 16 aprile 2016

The (Duel)lists
come usare le Linked Lists in C

Se qualcuno parla male delle Linked Lists lo sfido a duello. Si, farò proprio come Harvey Keitel in uno dei capolavori di Ridley Scott. State attenti.
Cosa dicevi delle Linked Lists?
Da queste parti avevamo già affrontato (di striscio) il tema delle Linked Lists, in un post preistorico sulla malloc(): dovreste andare a rileggerlo, ma, se proprio non ne avete voglia, vi riporto una parte:

"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."

Premessa: se qualcuno non ha la minima idea di cosa sia una lista concatenata gli consiglio di leggersi (prima di continuare) una delle mille descrizioni (alcune veramente ottime) che si trovano in rete. Questa, per esempio. Per questo nuovo post ho deciso di riprendere il codice che avevo scritto per quello vecchio e semplificarlo/migliorarlo in maniera di ottenere:
  1. condensare in una sola funzione le due che nel vecchio codice creavano un nuovo nodo nella lista (semplificare!).
  2. aggiungere una funzione che permette di appendere un nuovo nodo invece di metterlo in testa alla lista (migliorare!).
Vai col codice!
#include<stdlib.h>
#include<stdio.h>

// nodo di una linked list con campo dati
typedef struct snode {
    int data;
    struct snode *next;
} node_t;

// alloca in testa a una lista un node con i dati e un 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;
}

// alloca in fondo a una lista un node con i dati e un 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;
    }
}

// main() per test
void main()
{
    int i;

    // init lista vuota 1 e inserisce con addNode() 3 nodi con data = indice loop
    node_t *head1 = NULL;
    for (i = 1; i <= 3; i++)
        addNode(&head1, i);

    // scorre la lista e stampa i valori
    node_t *myhead1 = head1;
    printf("myhead1=%p - metodo ADD\n", myhead1);
    while (myhead1) {
        printf("data=%d (myhead1=%p next=%p)\n", myhead1->data, myhead1, myhead1->next);
        myhead1 = myhead1->next ;
    }

    // init lista vuota 2 inserisce con appendNode() 3 nodi con data = indice loop
    node_t *head2 = NULL;
    for (i = 1; i <= 3; i++)
        appendNode(&head2, i);

    // scorre la lista e stampa i valori
    node_t *myhead2 = head2;
    printf("myhead2=%p - metodo APPEND\n", myhead2);
    while (myhead2) {
        printf("data=%d (myhead2=%p next=%p)\n", myhead2->data, myhead2, myhead2->next);
        myhead2 = myhead2->next ;
    }
}
Come si nota è abbastanza semplice e conciso, e, come sempre, il codice è auto-esplicativo, ampiamente commentato e con commenti che parlano da soli.

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. Però la lista ordinata in avanti mi sembra più coerente e facile da maneggiare.

Alla fin fine il programma ci mostra questo log:
myhead1=0x11b5050 - metodo ADD
data=3 (myhead1=0x11b5050 next=0x11b5030)
data=2 (myhead1=0x11b5030 next=0x11b5010)
data=1 (myhead1=0x11b5010 next=(nil))
myhead2=0x11b5070 - metodo APPEND
data=1 (myhead2=0x11b5070 next=0x11b5090)
data=2 (myhead2=0x11b5090 next=0x11b50b0)
data=3 (myhead2=0x11b50b0 next=(nil))
che mi sembra inutile spiegare (parla da solo!). Finisco con una ultima, doverosa, precisazione: evidentemente quello presentato è solo un programma di test: in una applicazione reale bisognerà aggiungere un po' di funzioni accessorie per cercare e cancellare nodi, ecc. E, visto che usiamo delle malloc(), bisognerà ricordarsi di usare le corrispondenti free()...

Beh, vi auguro un buon lavoro con le Linked Lists, che, sicuramente, vi daranno delle soddisfazioni. E se non ve le danno, pazienza: fossero questi i problemi della vita...

Ciao e al prossimo post!