Liste concatenate

In questa pagina 6

Idea

Una lista concatenata (linked list) è una sequenza di nodi; ogni nodo contiene un valore e il puntatore al nodo successivo. Il primo nodo è indicato da un puntatore testa; l'ultimo ha successivo NULL.

testa -> [3 | *] -> [7 | *] -> [1 | NULL]

I nodi non sono contigui in memoria: si allocano uno alla volta nell'heap (Gestione della memoria in C).

Confronto con l'array

Operazione	Array (o lista Python)	Lista concatenata
accesso al `k`-esimo elemento	$O(1)$	$O(k)$ : bisogna scorrere
inserimento/rimozione in testa	$O(n)$ (spostamenti)	$O(1)$
inserimento/rimozione dopo un nodo noto	$O(n)$	$O(1)$
inserimento in fondo	$O(1)$ ammortizzato	$O(n)$ , oppure $O(1)$ tenendo un puntatore alla coda
ricerca	$O(n)$ ( $O(\log n)$ se ordinato)	$O(n)$ , anche se ordinata
memoria	contigua, compatta	un puntatore in più per elemento

In C

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo {
    int valore;
    struct nodo *succ;
} Nodo;

(Struct autoreferenziali: Strutture (struct) in C.)

Inserimento in testa

La funzione deve modificare il puntatore testa del chiamante: o lo restituisce, o riceve un puntatore a puntatore (Puntatori in C).

/* versione che restituisce la nuova testa */
Nodo *inserisci_testa(Nodo *testa, int x) {
    Nodo *n = malloc(sizeof *n);
    if (n == NULL) return testa;      /* allocazione fallita: lista invariata */
    n->valore = x;
    n->succ = testa;
    return n;
}

/* versione con puntatore a puntatore */
void inserisci_testa2(Nodo **pt, int x) {
    Nodo *n = malloc(sizeof *n);
    if (n == NULL) return;
    n->valore = x;
    n->succ = *pt;
    *pt = n;
}

Scorrimento e ricerca

void stampa(const Nodo *p) {
    while (p != NULL) {
        printf("%d ", p->valore);
        p = p->succ;
    }
    printf("\n");
}

Nodo *cerca(Nodo *p, int x) {
    while (p != NULL && p->valore != x)    /* corto circuito: niente p->valore con p NULL */
        p = p->succ;
    return p;                              /* NULL se non trovato */
}

int lunghezza(const Nodo *p) {             /* ricorsiva: la lista è una struttura ricorsiva */
    return p == NULL ? 0 : 1 + lunghezza(p->succ);
}

Rimozione

/* rimuove la prima occorrenza di x; restituisce la nuova testa */
Nodo *rimuovi(Nodo *testa, int x) {
    Nodo *prec = NULL, *cur = testa;
    while (cur != NULL && cur->valore != x) {
        prec = cur;
        cur = cur->succ;
    }
    if (cur == NULL) return testa;         /* non trovato */
    if (prec == NULL) testa = cur->succ;   /* era il primo */
    else prec->succ = cur->succ;           /* scavalca cur */
    free(cur);
    return testa;
}

Inserimento ordinato

void inserisci_ordinato(Nodo **pt, int x) {
    while (*pt != NULL && (*pt)->valore < x)
        pt = &(*pt)->succ;                 /* pt punta al campo succ da modificare */
    inserisci_testa2(pt, x);               /* inserisce prima del nodo corrente */
}

Con il puntatore a puntatore il caso "inserimento in testa" non va trattato a parte.

Deallocazione

void distruggi(Nodo *p) {
    while (p != NULL) {
        Nodo *s = p->succ;     /* salvare il successivo PRIMA del free */
        free(p);
        p = s;
    }
}

int main(void) {
    Nodo *lista = NULL;                    /* lista vuota */
    for (int i = 1; i <= 3; i++)
        lista = inserisci_testa(lista, i); /* 3 2 1 */
    lista = rimuovi(lista, 2);             /* 3 1 */
    stampa(lista);
    distruggi(lista);
    return 0;
}

Varianti

Puntatore alla coda: inserimento in fondo $O(1)$ ; con inserimento in fondo e rimozione in testa si ottiene una coda (Pila e coda). Con inserimento e rimozione in testa si ottiene una pila.
Doppiamente concatenata: ogni nodo ha anche il puntatore al precedente; rimozione di un nodo noto in $O(1)$ e scorrimento nei due versi.
Circolare: l'ultimo nodo punta al primo.

In Python

Il valore None fa da NULL; la memoria è gestita dall'interprete.

python

class Nodo:
    def __init__(self, valore, succ=None):
        self.valore = valore
        self.succ = succ

testa = None
for x in [1, 2, 3]:
    testa = Nodo(x, testa)        # inserimento in testa: 3 -> 2 -> 1

p = testa
while p is not None:
    print(p.valore)
    p = p.succ

In Python una lista concatenata si scrive soprattutto per studio: list e deque coprono i casi d'uso pratici.

Errori tipici

Accedere a p->succ dopo free(p).
Perdere la testa della lista scorrendola con la stessa variabile testa: usare un puntatore ausiliario.
Non gestire la lista vuota o la rimozione del primo nodo.
Dimenticare di aggiornare il puntatore del chiamante dopo un inserimento in testa (inserisci_testa(lista, x); senza assegnare il risultato).