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

Armand d'Hubert: Ma questa tua opera di mezzana non è fuori moda?
Léonie: Quello che è sensato non passa mai di moda.

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

Nell'ultimo articolo avevo promesso che avrei concluso l'argomento linked list descrivendo una variazione interessante, le doubly linked list. E qui casca a fagiolo la citazione qui sopra:  in The Duellists (I duellanti) di Ridley Scott, la bella Léonie (Meg Wynn Owen) dice che "Quello che è sensato non passa mai di moda", esattamente come non passerà mai di moda la programmazione low-level del nostro amato C: in molti casi si può programmare aiutandosi con librerie già fatte (quelli del lato oscuro della forza ne sanno qualcosa, usano la STL anche per legarsi le scarpe) ma, quando è necessario, bisogna "sporcarsi le mani" con le basi della programmazione, e quindi le basi bisogna conoscerle bene, bisogna conoscerle come le proprie tasche. Avete mai provato a scrivere "scrivere" una libreria invece di "usarla"? Le basi, amici miei, le basi... E, come avrete già intuito, anche in questo articolo parleremo di linked list!

...le linked list non passeranno mai di moda...

Le doubly linked list sono una interessantissima variazione su tema delle linked list classiche. L'unica differenza apparente consiste nella presenza nei nodi, oltre al famoso campo next, anche di un campo prev (che sta per previous). E quindi, ogni node contiene un pointer anche al node precedente, e questa piccola aggiunta permette interessanti sviluppi. Prima di andare avanti è il caso di fare un breve riepilogo dei pro e contro delle liste doppie rispetto a quelle singole:

Vantaggi delle doubly linked list

• È possibile attraversare la lista in due direzioni (avanti e indietro). In alcune applicazioni pratiche questa e`una notevole semplificazione (e.g.: in un browser la navigazione avanti/indietro o la gestione della cronologia).
• L'eliminazione di un nodo è più semplice e rapida rispetto alle linked list, poiché non è necessario, per modificare i collegamenti, mantenere un pointer al nodo precedente mentre si scorre la lista.
• Inoltre, l'inserimento e la cancellazione agli estremi della lista avvengono in tempo costante O(1) se si dispone dei pointer a head e alla coda.
• Questa struttura è ideale per implementare funzionalità di undo/redo, deque (code con due estremità) e cache MRU/LRU.

Svantaggi delle doubly linked list

• C'è un maggiore consumo di memoria, poiché ogni ha due pointer (ai node precedente e successivo) oltre ai dati, aumentando l'overhead rispetto alle linked list.
• Le operazioni di inserimento e cancellazione generano un overhead maggiore nella gestione dei pointer, rendendo l'implementazione più complessa e error-prone se i pointer non vengono aggiornati correttamente.
• Infine, le operazioni di ricerca e accesso rimangono in tempo lineare, quindi non offrono vantaggi di velocità di accesso rispetto ad altre strutture come gli array, specialmente per liste di grandi dimensioni.

(...ecco, su quest'ultimo svantaggio apro una parentesi: in realtà non sarebbe il caso di parlare di array: stiamo parlando di liste. Però, già che ci sono, faccio notare che in alcune operazioni gli array sono superiori (ricerca) e in altre sono inferiori (sostituzione). Comunque i punti precedenti (vantaggi e svantaggi) si riferiscono solo a doubly linked list vs linked list", quindi dimentichiamoci, almeno per il momento, degli array. Chiudo la parentesi...)

E qui ci starebbe bene un piccolo riepilogo:

"In sintesi, le doubly linked lists sono ottime quando le operazioni di inserimento e cancellazione sono frequenti e necessitano di manipolazione bidirezionale, ma non sono ideali se la memoria è limitata o se è necessario un accesso casuale rapido agli elementi (ma quest'ultimo punto è, di nuovo, rispetto agli array, come ho appena descritto nella parentesi qui sopra)."

Ok, bando alle ciance: ho rivisto il codice dell'ultimo articolo per usare le doubly linked list; noterete che il risultato è molto simile, ma, grazie al doppio pointer, ho potuto fare alcune ottimizzazioni, specialmente nella cancellazione dei nodi (che, guarda caso, era proprio uno dei vantaggi descritti sopra). Vai col codice!

// linklist.c - un programma di esempio sulle doubly linked list
#include <stdlib.h>
#include <stdio.h>
// node di una doubly linked list con campo dati
typedef struct snode {
    int data;
    struct snode *prev;
    struct snode *next;
} node_t;
// prototipi locali
node_t *createNode(int data);
void   addNode(node_t **head, int data);
void   appendNode(node_t **head, int data);
node_t *findNode(node_t **head, int data);
void   delNode(node_t **head, int data);
void   cleanList(node_t **head);
void   printList(node_t **head);
// funzione main
int main()
{
    // init lista vuota e inserisco con appendNode() 5 nodi con data = indice del loop
    node_t *head = NULL;
    for (int i = 0; i < 5; i++)
        appendNode(&head, i);
    // mostro la lista
    printList(&head);
    // cerco un node: quello con data == 3
    findNode(&head, 3);
    // cancello un node: quello con data == 3
    delNode(&head, 3);
    // cerco il node cancellato (quello con data == 3)
    findNode(&head, 3);
    // mostro di nuovo la lista: deve mancare il node con data == 3
    printList(&head);
    // cancello l'intera lista
    cleanList(&head);
    // mostro di nuovo la lista: deve essere vuota
    printList(&head);
    return 0;
}
// createNode - crea un node vuoto
node_t *createNode(int data)
{
    // alloco un nuovo node e lo ritorno
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}
// addNode - alloca in testa alla lista un node con dati e pointer agli elementi next/previous
void addNode(node_t **head, int data)
{
    // creo un nuovo node
    node_t *node = createNode(data);
    // aggiungo il nuovo node
    node_t *current = *head;
    if (current == NULL) {
        // caso speciale per lista vuota: assegna head lista al nuovo node
        *head = node;
    }
    else {
        // assegno all'ultimo node il nuovo node
        current->prev = node;
        node->next    = *head;
        // assegno la head lista al nuovo node
        *head = node;
    }
}
// appendNode - alloca in fondo alla lista un node con dati e pointer agli elementi next/previous
void appendNode(node_t **head, int data)
{
    // creo un nuovo node
    node_t *node = createNode(data);
    // 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 {
        // scorro la lista per trovare l'ultimo node
        while (current->next != NULL)
            current = current->next;
        // assegno all'ultimo node il nuovo node
        current->next = node;
        node->prev    = current;
    }
}
// findNode - trova un node nella lista
node_t *findNode(node_t **head, int data)
{
    // scorro la lista
    node_t *current = *head;
    while (current) {
        // cerco il node con il <data> corrispondente
        if (current->data == data) {
            // node trovato!
            printf("%s: node trovato: data=%d (myhead=%p prev=%p next=%p)\n\n", __func__,
                   current->data, (void *)current, (void *)current->prev, (void *)current->next);
            return current;
        }
        // passo al prossimo node
        current = current->next;
    }
    // node non trovato!
    printf("%s: node con data=%d non trovato!\n\n", __func__, data);
    return NULL;
}
// delNode - rimuove un node dalla lista
void delNode(node_t **head, int data)
{
    // cerco il node con il <data> corrispondente
    node_t *current = findNode(head, data);
    // modifico il riferimento <next> per eliminare dall'elenco il node trovato
    if (current->prev)
        current->prev->next = current->next;
    else
        *head = current->next;
    // cancello il node e ritorno
    printf("%s: cancello data=%d (current=%p prev=%p next=%p)\n", __func__,
           current->data, (void *)current, (void *)current->prev, (void *)current->next);
    free(current);
    return;
}
// cleanList - reset completo della lista
void cleanList(node_t **head)
{
    printf("%s: cancello elementi:\n", __func__);
    // scorro la lista
    node_t *current = *head;
    node_t *next;
    while (current) {
        // salvo il node successivo prima di liberare quello corrente
        next = current->next;
        // cancello il node
        printf("cancello data=%d (current=%p prev=%p next=%p)\n",
               current->data, (void *)current, (void *)current->prev, (void *)current->next);
        free(current);
        // mi sposto sul node successivo
        current = next;
    }
    printf("\n");
    // imposto la head lista a NULL per indicare che la lista è vuota
    *head = NULL;
}
// printList - mostra la lista
void printList(node_t **head)
{
    // scorro la lista e stampo i valori
    node_t *current = *head;
    printf("%s: lista in %p - elementi contenuti:\n", __func__, (void *)current);
    int find = 0;
    while (current) {
        printf("data=%d (current=%p prev=%p next=%p)\n",
               current->data, (void *)current, (void *)current->prev, (void *)current->next);
        current = current->next;
        find++;
    }
    if (!find)
        printf("%s: nessun elemento trovato!\n", __func__);
    else
        printf("\n");
}

Interessante no? Avrete anche notato (spero) che ho aggiunto una nuova funzione createNode() che evita di ripetere le stesse linee di creazione in varie funzioni dell'applicazione (serve solo a rendere più leggibile e fluido il codice). E poi, dato che c'ero, ho deciso di variare un po' e ho usato appendNode() invece di addNode() per creare la lista: il risultato è una lista con un ordine crescente in memoria invece che decrescente (come era, invece, l'esempio nell'ultimo articolo) il che la rende un po più user-frendly come interpretazione.

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, quando necessario, valori significativi invece di void). Non dimenticatevene mai!

E anche questa volta: cosa manca per finire l'articolo? Ah, si, compilare ed eseguire. Vediamo un po:

aldo@Linux $ gcc -Wall -Wextra -pedantic linklist.c -o linklist
aldo@Linux $ ./linklist
printList: lista in 0x612757d4b2a0 - elementi contenuti:
data=0 (current=0x612757d4b2a0 prev=(nil) next=0x612757d4b2c0)
data=1 (current=0x612757d4b2c0 prev=0x612757d4b2a0 next=0x612757d4b2e0)
data=2 (current=0x612757d4b2e0 prev=0x612757d4b2c0 next=0x612757d4b300)
data=3 (current=0x612757d4b300 prev=0x612757d4b2e0 next=0x612757d4b320)
data=4 (current=0x612757d4b320 prev=0x612757d4b300 next=(nil))
findNode: node trovato: data=3 (myhead=0x612757d4b300 prev=0x612757d4b2e0 next=0x612757d4b320)
findNode: node trovato: data=3 (myhead=0x612757d4b300 prev=0x612757d4b2e0 next=0x612757d4b320)
delNode: cancello data=3 (current=0x612757d4b300 prev=0x612757d4b2e0 next=0x612757d4b320)
findNode: node con data=3 non trovato!
printList: lista in 0x612757d4b2a0 - elementi contenuti:
data=0 (current=0x612757d4b2a0 prev=(nil) next=0x612757d4b2c0)
data=1 (current=0x612757d4b2c0 prev=0x612757d4b2a0 next=0x612757d4b2e0)
data=2 (current=0x612757d4b2e0 prev=0x612757d4b2c0 next=0x612757d4b320)
data=4 (current=0x612757d4b320 prev=0x612757d4b300 next=(nil))
cleanList: cancello elementi:
cancello data=0 (current=0x612757d4b2a0 prev=(nil) next=0x612757d4b2c0)
cancello data=1 (current=0x612757d4b2c0 prev=0x612757d4b2a0 next=0x612757d4b2e0)
cancello data=2 (current=0x612757d4b2e0 prev=0x612757d4b2c0 next=0x612757d4b320)
cancello data=4 (current=0x612757d4b320 prev=0x612757d4b300 next=(nil))
printList: lista in (nil) - elementi contenuti:
printList: nessun elemento trovato!

Beh, anche questa volta i risultati parlano chiaro, no? E corrispondono nuovamente ai passi indicati nel codice (che non sto a ripetere qui, piuttosto leggete i commenti super-dettagliati!).

Ok, credo che per un po' potremo accantonare questo interessante (spero) argomento delle linked list. Cosa ci riserverà il futuro? Boh, in questo momento non lo so, ma sicuramente sarà interessantissimo!

Ciao, e al prossimo post!