liste-cpp.md

Liste concatenate in C++ — esempi progressivi

Ogni blocco è indipendente e compilabile da solo (g++ -std=c++17 file.cpp).

1. Il nodo

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

int main() {
    Nodo a{10, nullptr};
    std::cout << a.dato << "\n";
}

Un nodo è un dato + un puntatore al nodo successivo. next == nullptr significa "fine lista".

2. Collegare due nodi a mano

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

int main() {
    Nodo b{20, nullptr};
    Nodo a{10, &b};   // a.next punta a b

    std::cout << a.dato << " -> " << a.next->dato << "\n";
}

a.next->dato legge il campo dato del nodo puntato da next.

3. Attraversamento (stampa)

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

void stampa(Nodo* testa) {
    Nodo* n = testa;
    while (n != nullptr) {
        std::cout << n->dato << " ";
        n = n->next;
    }
    std::cout << "\n";
}

int main() {
    Nodo c{30, nullptr};
    Nodo b{20, &c};
    Nodo a{10, &b};
    stampa(&a);   // 10 20 30
}

4. Inserimento in testa, con new

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

Nodo* inserisciTesta(Nodo* testa, int valore) {
    Nodo* nuovo = new Nodo{valore, testa};
    return nuovo;   // il nuovo nodo diventa la testa
}

void stampa(Nodo* testa) {
    for (Nodo* n = testa; n != nullptr; n = n->next)
        std::cout << n->dato << " ";
    std::cout << "\n";
}

int main() {
    Nodo* lista = nullptr;
    lista = inserisciTesta(lista, 30);
    lista = inserisciTesta(lista, 20);
    lista = inserisciTesta(lista, 10);
    stampa(lista);   // 10 20 30
}

Qui la lista cresce a runtime: nessuna dimensione dichiarata a priori (il problema che FORTRAN non risolveva).

5. Inserimento dopo un nodo dato

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

void inserisciDopo(Nodo* nodo, int valore) {
    Nodo* nuovo = new Nodo{valore, nodo->next};
    nodo->next = nuovo;
}

void stampa(Nodo* testa) {
    for (Nodo* n = testa; n != nullptr; n = n->next)
        std::cout << n->dato << " ";
    std::cout << "\n";
}

int main() {
    Nodo c{30, nullptr};
    Nodo a{10, &c};
    stampa(&a);              // 10 30
    inserisciDopo(&a, 20);
    stampa(&a);              // 10 20 30
}

Nessuno spostamento di indici (a differenza dell'array FORTRAN): si aggiornano solo due puntatori.

6. Rimozione di un nodo

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

Nodo* rimuoviTesta(Nodo* testa) {
    if (testa == nullptr) return nullptr;
    Nodo* prossimo = testa->next;
    delete testa;
    return prossimo;
}

void stampa(Nodo* testa) {
    for (Nodo* n = testa; n != nullptr; n = n->next)
        std::cout << n->dato << " ";
    std::cout << "\n";
}

int main() {
    Nodo* lista = new Nodo{10, new Nodo{20, new Nodo{30, nullptr}}};
    stampa(lista);              // 10 20 30
    lista = rimuoviTesta(lista);
    stampa(lista);              // 20 30
}

7. Lista doppiamente concatenata (avanti e indietro)

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
    Nodo* prev;
};

int main() {
    Nodo b{20, nullptr, nullptr};
    Nodo a{10, &b, nullptr};
    b.prev = &a;

    std::cout << "avanti: " << a.dato << " " << a.next->dato << "\n";
    std::cout << "indietro: " << b.dato << " " << b.prev->dato << "\n";
}

Questo è il modello simmetrico usato da SLIP di Weizenbaum: ogni cella naviga in entrambe le direzioni.

8. Lista di liste (annidamento)

#include <iostream>

struct Nodo {
    int dato;
    Nodo* next;
};

struct NodoLista {
    Nodo* sottolista;   // il "dato" qui è una lista intera
    NodoLista* next;
};

void stampaSemplice(Nodo* n) {
    for (; n != nullptr; n = n->next) std::cout << n->dato << " ";
}

int main() {
    Nodo* interna = new Nodo{1, new Nodo{2, nullptr}};
    NodoLista esterna{interna, nullptr};

    stampaSemplice(esterna.sottolista);   // 1 2
    std::cout << "\n";
}

Una lista può contenere un'altra lista come dato: è l'annidamento che l'array fisso FORTRAN non permetteva senza dichiarare matrici rigide a priori.