Vue d'ensemble
Jusqu'ici, une variable C contenait un seul nombre. Mais un point du plan, c'est deux nombres qui vont ensemble ; une liste de valeurs, c'est un nombre variable de cases reliées entre elles. Les structures permettent de regrouper plusieurs champs sous un même nom, et les listes chaînées — des maillons reliés par des pointeurs — sont la première structure de données dynamique du programme : elles grandissent et rétrécissent pendant l'exécution, sans qu'on ait à fixer leur taille à l'avance comme pour un tableau.
- Type structuré : déclaration d'une
struct, accès à un champ par l'opérateur point.champ. - Alias de type avec
typedefpour alléger l'écriture. - Maillon d'une liste chaînée : structure contenant une valeur et un pointeur vers le maillon suivant (structure récursive).
- Liste chaînée = pointeur vers le premier maillon, ou
NULLsi la liste est vide. - Opérateur flèche
p->champ, équivalent à(*p).champ. - Opérations : création dynamique (
malloc), insertion en tête, parcours, longueur, libération (free).
Prérequis
- Pointeurs et allocation dynamique (fiche
c-pointeurs-allocation) : déréférencement*p,malloc/free,sizeof, la constanteNULL. - Boucle
whileet test de condition. - Notion de fonction qui prend et renvoie un pointeur.
Les listes chaînées font peur au début, puis tout s'éclaire. Le déclic vient quand on dessine les flèches entre maillons. Nos mentors alumni X · Centrale · Mines t'apprennent à visualiser la mémoire pour ne plus jamais confondre pointeur et valeur.
Trouver un mentor →Les structures : regrouper des champs
Une structure est un type composé qui rassemble plusieurs variables — appelées champs — sous un seul nom. L'exemple canonique est le point du plan, formé d'une abscisse et d'une ordonnée.
Une structure est un type de données regroupant un nombre fixe de champs, chacun ayant son propre nom et son propre type. On accède au champ c d'une variable de structure v par l'écriture v.c (opérateur point).
struct Point { int x; int y; }; // declaration du type
int main(void) {
struct Point a; // a est une variable de type struct Point
a.x = 2; // on remplit le champ x
a.y = 5; // on remplit le champ y
printf("a.x = %d, a.y = %d\n", a.x, a.y);
return 0;
}struct Point { int x; int y; };déclare un nouveau type nommé struct Point composé de deux champs entiers x et y. Le point-virgule final est obligatoire. Cette ligne ne réserve aucune mémoire : elle décrit seulement la forme du type.struct Point a;crée une variable a de ce type. Elle occupe en mémoire la place de ses deux champs (deux int). Le nom complet du type est struct Point, en deux mots.a.x = 2;affecte 2 au champ x de a. L'opérateur point . désigne le champ d'une structure quand on manipule la structure elle-même (pas un pointeur vers elle).a.y = 5;même chose pour le champ y. Les deux champs sont indépendants.printf(...a.x...a.y);lit les deux champs pour les afficher. La sortie est a.x = 2, a.y = 5.Alléger l'écriture avec typedef
Répéter struct Point partout est lourd. Le mot-clé typedef crée un alias de type : un nom plus court qui désigne exactement le même type.
typedef struct { int x; int y; } Point; // Point est maintenant un alias
int main(void) {
Point b; // plus besoin d'ecrire "struct"
b.x = 4;
b.y = 7;
printf("b.x = %d, b.y = %d\n", b.x, b.y);
return 0;
}typedef struct { ... } Point;déclare une structure anonyme (sans nom après struct) et lui donne l'alias Point. Désormais, écrire Point revient exactement à écrire cette structure.Point b;déclare b avec le nom court. C'est strictement équivalent à déclarer une variable du même type composé ; on gagne juste en lisibilité.b.x = 4; b.y = 7;l'accès aux champs se fait toujours avec le point : typedef ne change que le nom du type, pas la façon d'atteindre les champs. Sortie : b.x = 4, b.y = 7.Point c = b; copie tous les champs de b dans c (copie par valeur). Modifier ensuite c.x ne touche pas b.x : ce sont deux blocs mémoire distincts. C'est différent des tableaux, qu'on ne peut pas copier ainsi.Le maillon et la liste chaînée
Un tableau a une taille figée à sa création. Pour manipuler une collection dont la taille varie à l'exécution, on relie des cases entre elles : chaque case connaît la suivante. Cette case s'appelle un maillon.
Un maillon est une structure contenant deux champs : une valeur (la donnée stockée) et un pointeur vers le maillon suivant. Comme ce pointeur désigne un objet du même type, on parle de structure récursive.
typedef struct Maillon {
int valeur; // la donnee stockee dans ce maillon
struct Maillon *suivant; // pointeur vers le maillon d'apres
} Maillon;typedef struct Maillon {on donne cette fois un nom, Maillon, juste après struct. Ce nom est indispensable ici : sans lui, on ne pourrait pas parler du type à l'intérieur de sa propre déclaration.int valeur;premier champ : l'entier stocké dans le maillon.struct Maillon *suivant;second champ : un pointeur vers un struct Maillon. On écrit struct Maillon (pas seulement Maillon) car l'alias Maillon n'existe pas encore à ce point : il n'est défini qu'à la dernière ligne. Ce pointeur permet de « connaître le suivant ».} Maillon;ferme la structure et crée enfin l'alias Maillon, qu'on utilisera dans tout le reste du code.Une liste chaînée d'entiers est représentée par un pointeur vers son premier maillon (la tête). Une liste vide est représentée par le pointeur NULL. Le champ suivant du dernier maillon vaut NULL, ce qui marque la fin de la chaîne.
[3, 5, 8] se lit ainsi : la tête pointe vers un maillon 3, dont le suivant pointe vers 5, dont le suivant pointe vers 8, dont le suivant vaut NULL. Suivre les flèches de suivant en suivant jusqu'à NULL, c'est parcourir toute la liste.L'opérateur flèche p vers champ
Quand on manipule une structure via un pointeur p, on veut accéder à un champ de la structure pointée. On pourrait écrire (*p).valeur — déréférencer d'abord, puis prendre le champ — mais c'est lourd. C'est pourquoi C fournit un raccourci.
Si p est un pointeur vers une structure, p->champ désigne le champ champ de la structure pointée. C'est un raccourci strictement équivalent à (*p).champ.
. est prioritaire sur l'étoile *. Sans parenthèses, *p.champ est interprété comme *(p.champ), ce qui n'a pas de sens ici et provoque une erreur. La flèche p->champ évite ce piège : préfère-la systématiquement.Construire et parcourir une liste
On assemble maintenant tout : créer des maillons dynamiquement, les enchaîner par insertion en tête, parcourir la liste, compter ses éléments, puis libérer la mémoire. Voici le programme central de la fiche.
#include <stdio.h>
#include <stdlib.h>
typedef struct Maillon {
int valeur;
struct Maillon *suivant;
} Maillon;
Maillon *inserer_en_tete(Maillon *tete, int v) {
Maillon *nouveau = malloc(sizeof(Maillon));
nouveau->valeur = v;
nouveau->suivant = tete;
return nouveau;
}
int longueur(Maillon *tete) {
int n = 0;
Maillon *p = tete;
while (p != NULL) {
n++;
p = p->suivant;
}
return n;
}
void afficher(Maillon *tete) {
Maillon *p = tete;
while (p != NULL) {
printf("%d ", p->valeur);
p = p->suivant;
}
printf("\n");
}
void liberer(Maillon *tete) {
Maillon *p = tete;
while (p != NULL) {
Maillon *tmp = p->suivant;
free(p);
p = tmp;
}
}
int main(void) {
Maillon *liste = NULL; // liste vide
liste = inserer_en_tete(liste, 8);
liste = inserer_en_tete(liste, 5);
liste = inserer_en_tete(liste, 3);
afficher(liste); // 3 5 8
printf("longueur = %d\n", longueur(liste));
liberer(liste);
return 0;
}Maillon *nouveau = malloc(sizeof(Maillon));réserve sur le tas la place d'un maillon et récupère son adresse dans nouveau. sizeof(Maillon) donne la taille exacte à allouer ; on ne devine pas le nombre d'octets.nouveau->valeur = v;range la valeur reçue dans le champ valeur du maillon fraîchement créé, via la flèche puisque nouveau est un pointeur.nouveau->suivant = tete;cœur de l'insertion en tête : le nouveau maillon pointe vers l'ancienne tête. Il se place donc devant tous les autres.return nouveau;renvoie l'adresse du nouveau maillon, qui devient la nouvelle tête. C'est pourquoi on écrit liste = inserer_en_tete(liste, ...) : la variable liste doit être mise à jour.Maillon *p = tete;dans le parcours, on copie la tête dans une variable de travail p pour ne pas perdre l'adresse de départ.while (p != NULL)on avance tant qu'on n'a pas atteint la fin. Le test p != NULL garantit qu'on ne déréférence jamais un pointeur nul.p = p->suivant;on saute au maillon suivant en suivant la flèche suivant. Sans cette ligne, p ne bougerait jamais et la boucle tournerait sans fin.Maillon *tmp = p->suivant;dans liberer, on mémorise l'adresse du suivant avant de libérer p : une fois free(p) exécuté, lire p->suivant serait interdit.free(p);rend au système la mémoire du maillon courant, puis on avance avec p = tmp;. On libère ainsi chaque maillon un par un.Maillon *liste = NULL;on part d'une liste vide. Chaque inserer_en_tete ajoute un maillon devant. Comme on insère 8 puis 5 puis 3, la liste finale est 3 5 8 : l'ordre est inversé par rapport à l'ordre d'insertion.| Étape | Instruction | État de la liste (tête → … → NULL) |
|---|---|---|
| 0 | liste = NULL | (vide) |
| 1 | inserer_en_tete(liste, 8) | 8 → NULL |
| 2 | inserer_en_tete(liste, 5) | 5 → 8 → NULL |
| 3 | inserer_en_tete(liste, 3) | 3 → 5 → 8 → NULL |
| 4 | parcours : p = tete | p sur 3, affiche 3 |
| 5 | p = p->suivant | p sur 5, affiche 5 |
| 6 | p = p->suivant | p sur 8, affiche 8 |
| 7 | p = p->suivant | p == NULL → fin, sortie 3 5 8 ✓ |
- Prendre une variable de travail :
Maillon *p = tete;(ne jamais déplacerteteelle-même, on la perdrait). - Boucler tant que
p != NULL: ce test protège tout déréférencement. - Traiter le maillon courant via
p->valeur(afficher, compter, comparer…). - Avancer avec
p = p->suivant;— sans oublier cette ligne, sinon boucle infinie.
Le schéma « tête → maillon → NULL » est la clé de 90 % des exos de listes. Une fois qu'on sait le dessiner et le tracer, l'insertion, la suppression et le renversement deviennent des variations simples. Nos mentors alumni X · Centrale · Mines t'entraînent sur les sujets de concours en TP d'info.
Trouver un mentor →Les trois pièges à éviter
tete->valeur quand tete vaut NULL lit à l'adresse nulle : le programme plante (segmentation fault). Avant tout accès à tete->…, vérifie if (tete != NULL), et dans les boucles garde toujours la condition while (p != NULL).3 5 8, et non 8 5 3 : chaque nouvel élément se place devant. Si tu veux conserver l'ordre d'insertion, il faut insérer en queue (plus coûteux) ou insérer les valeurs dans l'ordre inverse.malloc réserve de la mémoire qui n'est pas rendue automatiquement. Si on abandonne une liste sans la libérer maillon par maillon, cette mémoire reste occupée jusqu'à la fin du programme : c'est une fuite. Et attention à l'ordre : on mémorise p->suivant avant de faire free(p), jamais après.Exercices corrigés
On dispose du type typedef struct { int x; int y; } Point;. On crée Point p = {3, 4}; puis un second point q tel que q.x = p.x + 1 et q.y = p.y * 2. Qu'affiche printf("%d %d\n", q.x, q.y); ?
Voir la correction détaillée
p = {3, 4} initialise p.x = 3 et p.y = 4 (les champs sont remplis dans l'ordre de déclaration).q.x = p.x + 1 = 3 + 1 = 4.q.y = p.y * 2 = 4 * 2 = 8.4 8. Modifier q ne touche pas p : ce sont deux structures distinctes.Écris une fonction int somme(Maillon *tete) qui renvoie la somme des valeurs de la liste (0 si la liste est vide). Applique-la à la liste [3, 5, 8].
Voir la correction détaillée
p, une boucle tant que p != NULL, un accumulateur.
int somme(Maillon *tete) {
int s = 0;
Maillon *p = tete;
while (p != NULL) {
s += p->valeur; // on ajoute la valeur courante
p = p->suivant; // on avance
}
return s;
}tete == NULL, la boucle ne s'exécute pas et on renvoie s = 0.[3, 5, 8] : s vaut 0, puis 3, puis 8, puis 16. Résultat : somme = 16 (vérifié à la compilation).Écris int contient(Maillon *tete, int cible) qui renvoie 1 si cible apparaît dans la liste, 0 sinon. La fonction doit s'arrêter dès qu'elle a trouvé la valeur (pas de parcours inutile). Teste-la sur [3, 5, 8] avec les cibles 5 puis 4.
Voir la correction détaillée
1 immédiatement au premier maillon qui contient la cible. Si la boucle se termine sans rien trouver, on renvoie 0.
int contient(Maillon *tete, int cible) {
Maillon *p = tete;
while (p != NULL) {
if (p->valeur == cible) return 1; // trouve : arret immediat
p = p->suivant;
}
return 0; // fin de liste atteinte sans succes
}return 1 à l'intérieur de la boucle interrompt le parcours dès le succès : c'est l'optimisation demandée. Le return 0 final n'est atteint que si p est devenu NULL.p passe sur 3 (non), puis 5 (oui) → renvoie 1. Cible 4 : p passe sur 3, 5, 8 (aucun), puis p == NULL → renvoie 0. Sortie du test : 1 0 (vérifié à la compilation).Récap final — Ce qu'il faut absolument retenir
Structures pour regrouper des champs, listes chaînées pour une collection dynamique. Coche mentalement chaque point avant de passer à la suite.
- Sais-tu déclarer une
struct, y accéder parv.champ, et créer un alias avectypedef? - Sais-tu pourquoi le maillon a besoin de
struct Maillon *suivantet pasMaillon *suivantà l'intérieur de sa propre déclaration ? - Sais-tu qu'une liste est un pointeur vers le premier maillon, et que
NULLreprésente la liste vide ? - Sais-tu que
p->champest exactement(*p).champ, et pourquoi les parenthèses sont obligatoires dans la seconde forme ? - Sais-tu écrire l'insertion en tête (nouveau maillon → ancienne tête, on renvoie la nouvelle tête) ?
- Sais-tu parcourir une liste avec
Maillon *p = tete; while (p != NULL) { …; p = p->suivant; }? - Sais-tu que l'insertion en tête inverse l'ordre d'insertion ?
- Sais-tu libérer une liste en mémorisant
p->suivantavant chaquefree(p), pour éviter la fuite mémoire ?