CodeUtility
Facilitiamo la vita agli sviluppatori!
Strutture dati in C/C++

La lista collegata semplice in C e C++

In questa lezione costruirai, scorrerai e libererai una lista collegata semplice in C e C++.

Introduzione

Una lista collegata semplice (singly linked list) è formata da nodi (node), e ogni nodo contiene un valore e un puntatore al nodo successivo. A differenza di un array, i nodi non devono stare uno accanto all'altro in memoria, quindi puoi aggiungere elementi senza spostare gli altri.

Punti importanti

  • Definisci le condizioni che devono essere sempre vere (invarianti) prima di scrivere le operazioni.
  • Gestisci i casi di struttura vuota, piena e di allocazione di memoria fallita.
  • Valuta insieme la complessità e la gestione della memoria di ogni operazione.

Guarda come funziona

Aggiungi nodi in testa o in coda e fai clic su un nodo per eliminarlo. Premi Avvia per seguire i puntatori next da head fino a NULL.

Esempi di codice C e C++

C
Esegui →
main.c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
Risultato dell'esecuzione
1 2 3
C++
Esegui →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
Risultato dell'esecuzione
1 2 3

Confronto tra C e C++

Nella versione in C, ogni nodo viene allocato con malloc, e alla fine il programma deve scorrere tutta la lista chiamando free su ogni nodo. Nella versione in C++, i nodi sono collegati con std::unique_ptr, quindi quando il primo nodo viene distrutto anche tutta la catena successiva viene liberata automaticamente.

C

I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.

C++

Classi e contenitori proteggono la coerenza dei dati e gestiscono da soli le proprie risorse.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Aggiungi test per la struttura vuota e per quando raggiunge la capacità massima.
  • Scrivi la liberazione della memoria e controlla che non ci siano perdite.
  • Confronta la complessità con il contenitore equivalente della libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide