Pile, code e liste collegate: strutture dati dinamiche

In quarta, all’indirizzo Informatica e telecomunicazioni (ma il discorso vale anche per le scienze applicate), il programma di informatica segue più o meno questa scansione: programmazione a oggetti, strutture dati dinamiche, poi HTML, CSS e JavaScript. A inizio ottobre di solito siete ancora su classi e oggetti. Le strutture dati dinamiche arrivano a novembre e la verifica, pratica o scritta, cade fra fine novembre e dicembre: da oggi, 5 ottobre, parliamo di 6-10 settimane. Il tempo c’è, ma l’argomento ha un ostacolo preciso: richiede di aver capito davvero i puntatori. Chi li ha lasciati a metà in terza o all’inizio di quarta qui paga il conto. Se vuoi ripassarli, c’è un post dedicato ai puntatori e alla memoria in C.

Nelle mie lezioni vedo che la difficoltà non è il codice in sé, che è corto. È tenere in testa il disegno: chi punta a chi, e cosa succede se sposto una freccia prima di un’altra. Per questo in questo post parto dal disegno e poi arrivo al codice.

Perché un array non basta

Con un array dichiari la dimensione una volta per tutte, e gli elementi stanno uno accanto all’altro in memoria. Questo è comodo per leggere: l’elemento di indice $i$ si raggiunge in tempo costante, $O(1)$. I problemi sono due.

• Dimensione fissa. Se ti servono 100 posti e ne hai dichiarati 50, sei bloccato. Se ne dichiari 10 000 per sicurezza, sprechi memoria.
• Inserire o togliere in mezzo costa. Per inserire un elemento in posizione $k$ devi spostare di un posto tutti quelli dopo di lui: nel caso peggiore sono $n$ spostamenti, cioè $O(n)$. Se la complessità ti suona poco familiare, il post su complessità e notazione O grande è il posto giusto.

Una struttura dati dinamica cresce e si accorcia mentre il programma gira, chiedendo memoria solo per gli elementi che servono davvero. Gli elementi non stanno più uno accanto all’altro: sono sparsi, e ognuno sa dove si trova il successivo.

Il nodo e la lista collegata

L’unità di base è il nodo: un dato più un puntatore al nodo successivo.

struct Nodo {
    int dato;      // il valore memorizzato
    Nodo* next;    // puntatore al nodo successivo (nullptr se è l'ultimo)
};

Una lista collegata semplice è una catena di nodi. Ti serve solo un puntatore al primo, che chiamiamo testa. L’ultimo nodo ha next uguale a nullptr, ed è così che si riconosce la fine. Disegnata:

testa -> [10|*] -> [20|*] -> [40|nullptr]

Una lista vuota è semplicemente testa == nullptr. Questo caso va sempre gestito: ne parliamo negli errori.

Inserimento in testa

È l’operazione più semplice e la più veloce, $O(1)$:

void inserisciInTesta(Nodo*& testa, int valore) {
    Nodo* nuovo = new Nodo;   // alloco un nodo nell'heap
    nuovo->dato = valore;
    nuovo->next = testa;      // il nuovo punta alla vecchia testa
    testa = nuovo;            // la testa ora è il nuovo nodo
}

L’ordine delle due ultime righe è tutto. Se scrivi prima testa = nuovo, hai perso l’unico riferimento al resto della lista. Nota anche Nodo*& testa: passo il puntatore per riferimento, altrimenti la funzione modificherebbe una copia e la testa del chiamante non cambierebbe.

Inserimento in coda

Senza un puntatore alla coda devi scorrere tutta la lista, quindi $O(n)$:

void inserisciInCoda(Nodo*& testa, int valore) {
    Nodo* nuovo = new Nodo;
    nuovo->dato = valore;
    nuovo->next = nullptr;
    if (testa == nullptr) {       // lista vuota: il nuovo diventa la testa
        testa = nuovo;
        return;
    }
    Nodo* p = testa;
    while (p->next != nullptr) {  // mi fermo sull'ultimo nodo, non oltre
        p = p->next;
    }
    p->next = nuovo;
}

Ricerca

Nodo* cerca(Nodo* testa, int valore) {
    Nodo* p = testa;
    while (p != nullptr && p->dato != valore) {
        p = p->next;
    }
    return p;   // nullptr se non trovato
}

L’ordine delle due condizioni nel while conta: se p è nullptr, la prima condizione è falsa e il C++ non valuta la seconda, evitando di leggere p->dato su un puntatore nullo.

Cancellazione: i tre casi

Per togliere un nodo bisogna “scavalcarlo” e poi liberarne la memoria. I casi sono tre.

1. Lista vuota: non c’è niente da fare.
2. Nodo in testa: sposto la testa sul secondo nodo.
3. Nodo nel mezzo o ultimo: mi serve il nodo precedente, perché è lui che deve puntare al successivo del nodo cancellato. L’ultimo nodo non è un caso diverso: il suo next è nullptr, quindi il precedente diventa semplicemente l’ultimo.

void cancella(Nodo*& testa, int valore) {
    if (testa == nullptr) return;           // caso 1
    if (testa->dato == valore) {            // caso 2
        Nodo* daCancellare = testa;
        testa = testa->next;
        delete daCancellare;
        return;
    }
    Nodo* prec = testa;                     // caso 3
    while (prec->next != nullptr && prec->next->dato != valore) {
        prec = prec->next;
    }
    if (prec->next != nullptr) {            // trovato
        Nodo* daCancellare = prec->next;
        prec->next = daCancellare->next;    // scavalco
        delete daCancellare;
    }
}

Il puntatore da non perdere è daCancellare: lo salvo prima di modificare i collegamenti, così posso fare delete dopo.

Pila (stack): ultimo entrato, primo uscito

Una pila è una struttura LIFO (Last In, First Out): si aggiunge e si toglie sempre dallo stesso lato, come una pila di piatti. Le operazioni sono:

• push(x): metto x in cima;
• pop(): tolgo l’elemento in cima;
• top(): guardo l’elemento in cima senza toglierlo;
• vuota(): dice se non c’è nessun elemento.

Si implementa in modo naturale sopra una lista: la cima della pila è la testa della lista, così push e pop sono inserimento e cancellazione in testa, entrambi $O(1)$.

struct Pila {
    Nodo* cima = nullptr;

    bool vuota() const { return cima == nullptr; }

    void push(int x) {
        Nodo* nuovo = new Nodo;
        nuovo->dato = x;
        nuovo->next = cima;
        cima = nuovo;
    }

    int pop() {                 // precondizione: la pila non è vuota
        Nodo* vecchio = cima;
        int valore = vecchio->dato;
        cima = cima->next;
        delete vecchio;
        return valore;
    }

    int top() const { return cima->dato; }   // precondizione: non vuota
};

Esempi reali: il tasto “annulla” di un editor (ogni azione va in cima, annullare toglie l’ultima), la cronologia “indietro” del browser, la gestione delle chiamate di funzione, il controllo delle parentesi.

Per chi usa Python, la stessa pila si scrive con una lista usata da un lato solo:

pila = []
pila.append(10)      # push
pila.append(20)
cima = pila[-1]      # top -> 20
x = pila.pop()       # pop -> 20, la pila ora contiene [10]
vuota = len(pila) == 0

Qui Python nasconde il lavoro con i nodi, ma l’idea è la stessa: si lavora sempre sull’estremità.

Coda (queue): primo entrato, primo uscito

Una coda è FIFO (First In, First Out): si inserisce da un lato (in fondo) e si toglie dall’altro (davanti), come in fila alla cassa. Le operazioni sono enqueue(x) per accodare e dequeue() per togliere il primo. Esempi: la coda di stampa, le richieste a un server, le code di attesa.

Con una lista a un solo puntatore, l’inserimento in coda costa $O(n)$. La soluzione è tenere due puntatori: testa (davanti) e fondo (ultimo nodo).

struct Coda {
    Nodo* testa = nullptr;   // da qui si toglie
    Nodo* fondo = nullptr;   // qui si aggiunge

    bool vuota() const { return testa == nullptr; }

    void enqueue(int x) {
        Nodo* nuovo = new Nodo;
        nuovo->dato = x;
        nuovo->next = nullptr;
        if (fondo == nullptr) {      // coda vuota: primo elemento
            testa = fondo = nuovo;
        } else {
            fondo->next = nuovo;
            fondo = nuovo;
        }
    }

    int dequeue() {                  // precondizione: coda non vuota
        Nodo* vecchio = testa;
        int valore = vecchio->dato;
        testa = testa->next;
        if (testa == nullptr) fondo = nullptr;   // la coda è diventata vuota
        delete vecchio;
        return valore;
    }
};

Il dettaglio che si dimentica più spesso è proprio if (testa == nullptr) fondo = nullptr;: se togli l’ultimo elemento e non azzeri fondo, il puntatore resta appeso a un nodo già cancellato.

Costi a confronto

Non esiste una struttura migliore in assoluto: dipende da cosa fai più spesso. Se leggi per indice di continuo, vince l’array. Se inserisci e togli ai bordi, pila e coda su lista sono perfette.

Errori tipici

• Perdere il riferimento al resto della lista. Modificare testa o un next prima di aver salvato dove puntava. Soluzione: prima collega il nuovo nodo al resto, poi sposta il puntatore.
• Dimenticare il caso lista vuota. Un testa->next con testa == nullptr è un accesso a un puntatore nullo e il programma si ferma. Ogni funzione deve chiedersi: e se è vuota? E se ha un solo nodo?
• Non fare delete. Ogni new ha il suo delete. Se cancelli un nodo scavalcandolo ma non lo liberi, quella memoria resta occupata fino alla fine del programma: è un memory leak. Ricordati anche di svuotare l’intera struttura alla fine.
• Usare un puntatore dopo il delete. Dopo delete p; non leggere più p->dato. Salva prima quello che ti serve.
• nullptr non controllato. while (p->next != nullptr) è giusto se sei sicuro che p non sia nullo; altrimenti controlla prima p.

Se ti sembra di sbagliare sempre lo stesso tipo di errore, è quasi sempre un problema di disegno: prima di scrivere il codice, fai lo schema con le frecce.

Esercizi svolti

Esercizio 1: inserimento in testa e cancellazione in mezzo

Parti dalla lista

testa -> [10] -> [20] -> [40] -> nullptr

Inserisci 5 in testa, poi cancella il nodo con valore 20.

Inserimento di 5.

1. Creo il nodo nuovo = [5|?].
2. nuovo->next = testa: il nuovo punta a 10.

nuovo -> [5] -> [10] -> [20] -> [40] -> nullptr
testa ----------^

3. testa = nuovo: ora la testa punta a 5.

testa -> [5] -> [10] -> [20] -> [40] -> nullptr

Cancellazione di 20. Il valore non è in testa (la testa vale 5), quindi siamo nel caso 3. prec parte da 5 e scorre finché prec->next->dato vale 20:

• prec = nodo 5: prec->next->dato = 10, diverso da 20, avanzo.
• prec = nodo 10: prec->next->dato = 20, mi fermo.

Poi daCancellare = prec->next (il nodo 20), quindi prec->next = daCancellare->next: il nodo 10 ora punta a 40.

testa -> [5] -> [10] -> [40] -> nullptr
                         [20] (scollegato)

Infine delete daCancellare libera il nodo 20. Lista finale: 5, 10, 40.

Esercizio 2: parentesi bilanciate con una pila

Regola: scorro la stringa. Ogni parentesi aperta ((, [, {) va in pila. Ogni parentesi chiusa deve corrispondere a quella in cima alla pila: se la pila è vuota o la cima non corrisponde, la stringa è sbilanciata. Alla fine la pila deve essere vuota.

Stringa 1: {[(a+b)*c]-d}. Considero solo le parentesi, nell’ordine: { [ ( ) ] }.

Pila vuota alla fine: bilanciata.

Stringa 2: ([)].

Mi fermo: sbilanciata, anche se ci sono due aperte e due chiuse. Contare le parentesi non basta, serve l’ordine, ed è esattamente quello che dà la pila.

Esercizio 3: sequenza di enqueue e dequeue

Coda inizialmente vuota. Operazioni: enqueue(5), enqueue(8), dequeue(), enqueue(3), enqueue(9), dequeue(), dequeue(), enqueue(7). Qual è lo stato finale?

Scrivo la coda con il primo elemento a sinistra.

1. enqueue(5): [5]
2. enqueue(8): [5, 8]
3. dequeue(): esce 5, resta [8]
4. enqueue(3): [8, 3]
5. enqueue(9): [8, 3, 9]
6. dequeue(): esce 8, resta [3, 9]
7. dequeue(): esce 3, resta [9]
8. enqueue(7): [9, 7]

Stato finale: davanti 9, in fondo 7. Gli elementi usciti, in ordine, sono 5, 8, 3: lo stesso ordine in cui erano entrati, che è la firma di una FIFO. Con una pila, a parità di operazioni, il primo pop avrebbe tolto 8, non 5.

Esercitarsi e simulazione

Su questo argomento non c’è ancora un simulatore di informatica nel sito. Per le altre materie puoi guardare la categoria delle simulazioni del liceo, mentre la pagina Informatica spiega come lavoro sulla materia. Il consiglio pratico per la verifica: riscrivi a mano, senza guardare, inserimento in testa, cancellazione e push/pop; poi fai girare il codice con tre casi (lista vuota, un nodo, tanti nodi). Quando quei tre casi funzionano, hai capito.

Per capire a cosa serve tutto questo, ti può servire anche leggere come si ragiona su classi e oggetti in C++, perché pila e coda sono spesso richieste proprio come classi, e come lo stesso schema “nodi collegati” porta poi a grafi, alberi e visite BFS e DFS. Se invece le basi con gli array ti sembrano ancora instabili, parti da cicli e array.

Se qualcosa non torna

Le strutture dati dinamiche sono uno di quegli argomenti in cui, o scatta il disegno giusto, o si resta bloccati sullo stesso errore per settimane. Se ti riconosci, puoi scrivermi dalla pagina contatti: facciamo una diagnosi gratuita, guardiamo dove si inceppa il ragionamento e decidiamo se serve davvero una lezione o basta qualche indicazione mirata.