Liste Collegate in C

Le liste collegate in C sono una struttura dati dinamica che permette di gestire collezioni di elementi in modo flessibile. A differenza degli array, le liste collegate possono crescere e ridursi dinamicamente durante l’esecuzione del programma, consentendo un utilizzo più efficiente della memoria. In questa guida, esploreremo come creare, manipolare e utilizzare le liste collegate in C, con esempi pratici che illustrano il loro funzionamento.

Cos’è una Lista Collegata?

Una lista collegata è una sequenza di nodi, dove ogni nodo contiene due campi:

1. Dati: L’informazione che si desidera memorizzare.
2. Puntatore al Prossimo Nodo: Un puntatore che collega il nodo al successivo nella lista.

Tipi di Liste Collegate

• Lista Singolarmente Collegata (Singly Linked List): Ogni nodo punta solo al nodo successivo.
• Lista Doppiamente Collegata (Doubly Linked List): Ogni nodo punta sia al nodo successivo che a quello precedente.

Creazione di una Lista Singolarmente Collegata

Definizione della Struttura Nodo

Per creare una lista collegata, iniziamo definendo la struttura di un nodo.

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

// Definizione della struttura del nodo
struct Nodo {
    int dato;
    struct Nodo* prossimo;
};

Qui, Nodo è una struttura che contiene un intero dato e un puntatore a un altro nodo prossimo.

Inserimento di un Nodo all’Inizio della Lista

Per inserire un nodo all’inizio della lista, creiamo una funzione che alloca un nuovo nodo e lo collega alla testa della lista.

void inserisci_in_testa(struct Nodo** testa, int nuovo_dato) {
    struct Nodo* nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nuovo_nodo->dato = nuovo_dato;
    nuovo_nodo->prossimo = *testa;
    *testa = nuovo_nodo;
}

Esempio di Uso:

int main() {
    struct Nodo* testa = NULL;

    inserisci_in_testa(&testa, 10);
    inserisci_in_testa(&testa, 20);
    inserisci_in_testa(&testa, 30);

    // Stampa i valori nella lista
    struct Nodo* corrente = testa;
    while (corrente != NULL) {
        printf("%d ", corrente->dato);
        corrente = corrente->prossimo;
    }

    return 0;
}

Uscita:

30 20 10

Inserimento e Cancellazione in una Lista Collegata

Inserimento alla Fine della Lista

Per inserire un nodo alla fine della lista, dobbiamo scorrere tutta la lista fino all’ultimo nodo e collegare il nuovo nodo.

void inserisci_in_fondo(struct Nodo** testa, int nuovo_dato) {
    struct Nodo* nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    struct Nodo* ultimo = *testa;
    nuovo_nodo->dato = nuovo_dato;
    nuovo_nodo->prossimo = NULL;

    if (*testa == NULL) {
        *testa = nuovo_nodo;
        return;
    }

    while (ultimo->prossimo != NULL)
        ultimo = ultimo->prossimo;

    ultimo->prossimo = nuovo_nodo;
}

Cancellazione di un Nodo

Per cancellare un nodo, è necessario aggiornare il puntatore del nodo precedente per saltare il nodo da eliminare.

void cancella_nodo(struct Nodo** testa, int key) {
    struct Nodo *temp = *testa, *precedente;

    if (temp != NULL && temp->dato == key) {
        *testa = temp->prossimo;
        free(temp);
        return;
    }

    while (temp != NULL && temp->dato != key) {
        precedente = temp;
        temp = temp->prossimo;
    }

    if (temp == NULL) return;

    precedente->prossimo = temp->prossimo;
    free(temp);
}

Esempio Completo con Inserimento e Cancellazione:

int main() {
    struct Nodo* testa = NULL;

    inserisci_in_fondo(&testa, 10);
    inserisci_in_fondo(&testa, 20);
    inserisci_in_fondo(&testa, 30);

    printf("Lista originale: ");
    struct Nodo* corrente = testa;
    while (corrente != NULL) {
        printf("%d ", corrente->dato);
        corrente = corrente->prossimo;
    }

    cancella_nodo(&testa, 20);
    printf("\nLista dopo cancellazione: ");
    corrente = testa;
    while (corrente != NULL) {
        printf("%d ", corrente->dato);
        corrente = corrente->prossimo;
    }

    return 0;
}

Uscita:

Lista originale: 10 20 30
Lista dopo cancellazione: 10 30

Liste Doppiamente Collegate

Le liste doppiamente collegate sono più flessibili perché permettono di attraversare la lista in entrambe le direzioni.

Definizione della Struttura Nodo per Liste Doppiamente Collegate

struct Nodo {
    int dato;
    struct Nodo* prossimo;
    struct Nodo* precedente;
};

Inserimento e Cancellazione in una Lista Doppiamente Collegata

Il processo di inserimento e cancellazione in una lista doppiamente collegata è simile a quello delle liste singolarmente collegate, con la differenza che occorre aggiornare anche il puntatore al nodo precedente.

Esempio di Inserimento in Lista Doppiamente Collegata:

void inserisci_in_testa(struct Nodo** testa, int nuovo_dato) {
    struct Nodo* nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nuovo_nodo->dato = nuovo_dato;
    nuovo_nodo->prossimo = *testa;
    nuovo_nodo->precedente = NULL;

    if (*testa != NULL)
        (*testa)->precedente = nuovo_nodo;

    *testa = nuovo_nodo;
}

Vantaggi e Svantaggi delle Liste Collegate

Vantaggi:

• Memoria Dinamica: Le liste collegate possono crescere e ridursi dinamicamente.
• Inserimenti/Cancellazioni: Le operazioni di inserimento e cancellazione sono efficienti, soprattutto alle estremità della lista.

Svantaggi:

• Accesso Lento: L’accesso agli elementi è sequenziale, il che può essere inefficiente rispetto agli array.
• Overhead di Memoria: Ogni nodo richiede memoria aggiuntiva per memorizzare i puntatori.

Conclusioni

Le liste collegate in C sono una struttura dati essenziale che fornisce flessibilità nella gestione dinamica della memoria. Comprendere come creare, manipolare e utilizzare liste collegate è fondamentale per affrontare problemi complessi dove gli array tradizionali non sono sufficienti. Nonostante gli svantaggi in termini di accesso sequenziale, le liste collegate sono insostituibili in situazioni che richiedono frequenti inserimenti e cancellazioni di elementi.