Liste concatenate in C

Definizione (lista concatenata). 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 →. La stessa struttura è presentata, in versione più elementare, in Liste concatenateLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate → e Pila e codaPila (LIFO) e coda (FIFO) come ADT: operazioni e costi; realizzazione in Python con list e collections.deque; realizzazione in C con array e indici, coda circolare; applicazioni (parentesi bilanciate, stack delle chiamate, visite).Pila e coda → (Fondamenti di Informatica); i puntatori usati qui sono quelli di Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C → e i blocchi di malloc vivono nello heap (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Esempio. Dopo addHead di $1$, $2$, $3$ in una lista vuota la lista è 3 2 1, con la testa che punta a 3. Stato dopo ciascuna chiamata (la freccia è il campo next):

L'ordine dei due assegnamenti di addHead conta: prima aux->next = *l (si salva la vecchia testa), poi *l = aux; invertendoli si perderebbe l'intera lista.

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

Operazioni

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

Esempio. Con Nodo *l = NULL; la chiamata addHead(&l, 5) rende l != NULL: senza il doppio puntatore la testa del chiamante non cambierebbe.

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 (si legge dall'interno: *l è il nodo corrente, (*l)->next il suo campo next, & ne prende l'indirizzo; le parentesi servono perché -> e [] hanno priorità su *): 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. La ricorsione è quella di Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →: caso base lista vuota, taglia che diminuisce di un nodo a ogni chiamata, quindi $n+1$ chiamate e costo $\Theta(n)$; lo stack di chiamate occupa $\Theta(n)$ (la versione iterativa usa $\Theta(1)$ di stack). Traccia di addTail(&l, 10) su 3 2 1: la prima chiamata vede *l = nodo $3$ e richiama su &(nodo 3)->next; poi su &(nodo 2)->next; poi su &(nodo 1)->next, dove *l == NULL: qui si crea il nodo e lo si scrive nel next del nodo $1$, che ora punta a $10$.
• 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");
}

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

Esempio. La lista 3 2 1 10 20 diventa 20 10 1 2 3 dopo inverti. Traccia su una lista più corta, 1 2 3 (ogni riga è lo stato alla fine dell'iterazione del while):

succ serve per non perdere il resto della lista prima di sovrascrivere cur->next. All'uscita cur == NULL e prec è l'ultimo nodo, la nuova testa: per questo l'ultima istruzione è *l = prec. Ogni nodo è visitato una volta, costo $\Theta(n)$ e $\Theta(1)$ di memoria aggiuntiva.

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

Definizione (coda con puntatori a testa e coda). 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; }

Esempio. Inseriti $10,20,30,40$ con enqueue, due dequeue danno $10$ e $20$ (ordine FIFO).

Prova: inseriti $10, 20, 30, 40$, due dequeue danno $10, 20$; dopo enqueue(99) si estrae $30, 40, 99$ (ordine FIFO). I due casi speciali sono quelli sulla coda vuota: in enqueue, se q->coda == NULL anche q->testa era NULL e il nuovo nodo è contemporaneamente testa e coda; in dequeue, se togliendo il nodo q->testa diventa NULL, la coda si è svuotata e anche q->coda va azzerato, altrimenti punterebbe a un nodo già liberato (puntatore pendente). 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

Proprietà (costi delle operazioni sulle liste concatenate)

Operazione	Lista semplice	Con puntatore alla coda
addHead, pop	$\Theta(1)$	$\Theta(1)$
addTail	$\Theta(n)$	$\Theta(1)$
ricerca di un valore	$\Theta(n)$	$\Theta(n)$
accesso al nodo $i$-esimo	$\Theta(i)$	$\Theta(i)$

Esempio. Con $n=1000$ nodi addTail ne scorre $1000$ in una lista semplice e nessuno con il puntatore alla coda. Costruire una lista di $n$ elementi con $n$ addTail su lista semplice costa $\sum_{k=0}^{n-1} k = \frac{n(n-1)}{2} \in \Theta(n^2)$ (somma di SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →, come in Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →), contro $\Theta(n)$ con addHead o con il puntatore alla coda.

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.