Listes chaînées
Nœuds joints par des pointeurs
- Une liste chaînée est une chaîne de petits structs appelés nœuds, éparpillés dans le tas.
- Chaque nœud contient une valeur et un pointeur vers le nœud suivant. Suivez les pointeurs pour parcourir la liste.
- Contrairement à un tableau, une liste peut grandir d'un nœud à la fois sans déplacer les autres.
Un struct autoréférentiel
- Un nœud est un struct qui contient un pointeur vers son propre type :
struct Node { int data; struct Node *next; };—dataest la valeur,nextpointe vers le nœud suivant.- Cela vous est donné sous la forme de
Nodedans chaque modèle de départ. Lenextdu dernier nœud estNULL.
head et la fin NULL
- Un seul pointeur, le head (tête), pointe vers le premier nœud. De là, vous accédez au reste.
- Le tout dernier nœud pointe vers
NULL, ce qui marque la fin de la liste. - Une liste vide est juste
head == NULL— il n'y a aucun nœud du tout.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Ajouter un nœud à l'avant
- Pour ajouter à l'avant, créez un nouveau nœud, pointez son
nextvers l'ancien head, et retournez le nouveau nœud comme nouveau head. - C'est rapide — cela ne touche aucun autre nœud.
- Comme le head change, la fonction retourne le nouveau head, et l'appelant le sauvegarde.
Erreurs courantes
- Ne perdez jamais le pointeur
head, sinon toute la liste devient inaccessible. - Libérez tous les nœuds ; le dernier nœud pointe vers
NULL.
À vous maintenant
- Parcours une liste avec un pointeur
curetcur = cur->next, en s'arrêtant àNULL. - Les nouveaux nœuds viennent de
malloc(sizeof(Node)); le vérificateur libère la liste. Ne pas écrire unmain.
Nœuds et pointeurs
Chaque nœud pointe vers le suivant ; insérer/supprimer en re-liant.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez int length(const Node *head) pour qu'il compte les nœuds dans la liste (0 pour une liste vide). Parcourez avec ->next jusqu'à NULL. Le type Node est donné. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez int sum_list(const Node *head) pour qu'il retourne le total de chaque data de nœud (0 pour une liste vide). Le type Node est donné. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez Node *push_front(Node *head, int value) pour qu'il crée un nouveau nœud (avec malloc), pointe son next vers l'ancien head, et le retourne comme nouvelle tête. Le vérificateur libérera la liste. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.