C Academy · Lezione

Liste concatenate semplici

Nodi e puntatori

Liste concatenate semplici è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Che cos'è una lista concatenata?

Una lista concatenata è una catena di piccole strutture chiamate nodi. Ogni nodo contiene un valore e un puntatore al nodo successivo.

A differenza degli array, gli elementi non devono essere contigui in memoria e la lista può crescere o ridursi facilmente.

#include <stdio.h>

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

int main(void) {
    printf("A node holds a value and a next pointer\n");
    return 0;
}

Definire un nodo

La struct del nodo contiene i dati e un struct Node *next che punta al nodo successivo.

Il tipo puntatore fa riferimento alla stessa struct, permettendo di collegare tra loro gli elementi della catena.

#include <stdio.h>

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

int main(void) {
    struct Node n;
    n.value = 42;
    n.next = NULL;
    printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
    return 0;
}

Il puntatore head

Una lista è identificata da un unico puntatore al primo nodo, chiamato head.

Una lista vuota è semplicemente una head uguale a NULL.

#include <stdio.h>

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

int main(void) {
    struct Node *head = NULL;
    printf("List is empty: %d\n", head == NULL);
    return 0;
}

Allocare un nodo

I nodi vengono generalmente creati nell'heap con malloc, così sopravvivono alla funzione che li crea.

Controlli sempre il valore restituito e ricordi di liberare i nodi in seguito.

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

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 7;
    n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Operatore freccia

Quando dispone di un puntatore a una struct, usi -> per accedere ai membri. n->value equivale a (*n).value.

Utilizzerà continuamente l'operatore freccia con le liste concatenate.

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

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 99;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Collegare due nodi

Per collegare i nodi, imposti il campo next del primo in modo che punti al secondo. Il campo next dell'ultimo nodo rimane NULL per indicare la fine.

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

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

int main(void) {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->value = 1; a->next = b;
    b->value = 2; b->next = NULL;
    printf("%d -> %d\n", a->value, a->next->value);
    free(a); free(b);
    return 0;
}

Un helper per creare nodi

Allocare ripetutamente i nodi è noioso, quindi racchiuda l'operazione in una funzione helper che alloca, inizializza e restituisce un nuovo nodo.

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

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

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v;
    n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(5);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Creare una piccola lista

Usando l'helper, crei una lista di tre nodi 1 -> 2 -> 3 collegando i puntatori next.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
    return 0;
}

Stampare la lista

Per stampare ogni valore, parta dalla head e segua i puntatori next finché non raggiunge NULL.

Questo modello di attraversamento è alla base di quasi tutte le operazioni sulle liste.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    for (struct Node *p = head; p; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

Array e liste concatenate a confronto

Gli array offrono un accesso rapido tramite indice, ma hanno dimensione fissa. Le liste concatenate consentono inserimenti e rimozioni semplici, ma offrono un accesso più lento, perché è necessario attraversarle per raggiungere un elemento.

Scelga in base alle operazioni più frequenti nel Suo programma.

#include <stdio.h>

int main(void) {
    printf("Array: O(1) index, costly resize\n");
    printf("List:  O(n) index, cheap insert/delete\n");
    return 0;
}

Liberare l'intera lista

Ogni nodo allocato con malloc deve essere liberato. Scorra la lista, ma salvi il puntatore successivo prima di liberare ogni nodo, altrimenti perderà il resto della catena.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) {
        struct Node *nxt = p->next;
        free(p);
        p = nxt;
    }
    printf("freed all nodes\n");
    return 0;
}

Verifica rapida

Verifichi la Sua comprensione della struttura delle liste concatenate.

Riepilogo

Ha appreso le basi delle liste semplicemente concatenate:

Un nodo contiene un valore e un puntatore next; la testa punta al primo nodo.
Allochi i nodi con malloc e acceda ai membri con ->.
Il next dell'ultimo nodo è NULL; attraversi la lista seguendo i puntatori.
Liberi sempre ogni nodo con free, salvando next prima della liberazione.

Domande Frequenti

La lezione «Liste concatenate semplici» è gratuita?

Sì — il testo completo di «Liste concatenate semplici» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Liste concatenate semplici»?

Nodi e puntatori Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Liste concatenate semplici»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy