Liste concatenate in C

Una lista concatenata è una sequenza di nodi allocati nello heap, ciascuno con un valore e un puntatore al successivo; la lista è identificata dal puntatore alla testa (NULL = lista vuota). Premessa: Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C →. È l'implementazione concreta degli ADT di Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →.

typedef struct nodo {
    int val;
    struct nodo *next;
} Nodo;

Operazioni

Ogni funzione che può cambiare la testa riceve un Nodo **l (puntatore alla variabile testa del chiamante).

void addHead(Nodo **l, int n) {          /* O(1) */
    Nodo *aux = malloc(sizeof(Nodo));
    aux->val = n;
    aux->next = *l;
    *l = aux;
}

void addTail(Nodo **l, int n) {          /* O(n): scende fino al NULL finale */
    if (*l == NULL) {
        Nodo *aux = malloc(sizeof(Nodo));
        aux->val = n;
        aux->next = NULL;
        *l = aux;
    } else
        addTail(&(*l)->next, n);
}

int pop(Nodo **l) {                      /* O(1), precondizione: lista non vuota */
    Nodo *aux = *l;
    int res = aux->val;
    *l = aux->next;
    free(aux);
    return res;
}

• In addTail il puntatore passato alla chiamata ricorsiva è &(*l)->next, cioè l'indirizzo del campo next del nodo corrente: così quando si arriva a *l == NULL si scrive direttamente nel next dell'ultimo nodo. Versione iterativa equivalente: while (*l != NULL) l = &(*l)->next; e poi si inserisce in *l.
• Con addHead e pop si ottiene una pila (LIFO); con addTail e pop una coda (FIFO).
• pop deve fare free del nodo dopo aver letto val e next.

Funzioni di sola lettura si scrivono con const Nodo *l e senza * doppio:

int lunghezza(const Nodo *l) { return l == NULL ? 0 : 1 + lunghezza(l->next); }

void stampa(const Nodo *l) {
    for (; l != NULL; l = l->next) printf("%d ", l->val);
    printf("\n");
}

Inversione in loco, $O(n)$ e senza nodi nuovi: si ritorcono i puntatori scorrendo la lista.

void inverti(Nodo **l) {
    Nodo *prec = NULL, *cur = *l;
    while (cur != NULL) {
        Nodo *succ = cur->next;
        cur->next = prec;
        prec = cur;
        cur = succ;
    }
    *l = prec;
}

Liberare tutta la lista: while (*l != NULL) pop(l);.

Prova eseguita: dopo addHead di $1,2,3$, addTail(10), addTail(20) la lista è 3 2 1 10 20 (lunghezza $5$); dopo inverti è 20 10 1 2 3; pop restituisce $20$ e lascia 10 1 2 3.

Coda con due puntatori

Per rendere $O(1)$ anche l'inserimento in fondo si tengono due puntatori, in una struct:

typedef struct { Nodo *testa; Nodo *coda; } Coda;     /* estrae da testa, inserisce in coda */

void enqueue(Coda *q, int v) {
    Nodo *n = malloc(sizeof(Nodo));
    n->val = v; n->next = NULL;
    if (q->coda == NULL) q->testa = n;     /* coda vuota */
    else q->coda->next = n;
    q->coda = n;
}

int dequeue(Coda *q) {                     /* precondizione: non vuota */
    Nodo *n = q->testa;
    int v = n->val;
    q->testa = n->next;
    if (q->testa == NULL) q->coda = NULL;  /* si e' svuotata */
    free(n);
    return v;
}

int isEmpty(const Coda *q) { return q->testa == NULL; }

Prova: inseriti $10, 20, 30, 40$, due dequeue danno $10, 20$; dopo enqueue(99) si estrae $30, 40, 99$ (ordine FIFO). Con una lista doppiamente concatenata (campo prev in più) si può anche togliere dal fondo in $O(1)$.

Ricorsione sulle liste

Molti esercizi d'esame si risolvono con la ricorsione sul resto della lista. Schema: caso base l == NULL, poi si tratta il primo nodo e si richiama sul next. Esempi: contare i nodi con una proprietà, riempire un array di conteggi, copiare una lista in ordine inverso (la chiamata ricorsiva va prima dell'aggiunta in coda: gli elementi vengono accodati risalendo, quindi dall'ultimo al primo), confrontare due liste.

Costi

Errori comuni

• Passare Nodo *l invece di Nodo **l a una funzione che cambia la testa: la modifica si perde.
• pop su lista vuota (dereferenzia NULL), o free del nodo prima di salvare next.
• enqueue/dequeue che dimenticano di aggiornare entrambi i puntatori quando la coda era o diventa vuota.
• Non inizializzare next a NULL nel nuovo nodo (la lista non termina mai).
• Dimenticare free di tutti i nodi a fine uso.