Linked lists · Listes chaînées
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
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.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
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 and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
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;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
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.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
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.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
À 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.
Nodes and pointers · Nœuds et pointeurs
Each node points to the next; insert/delete by re-linking. · Chaque nœud pointe vers le suivant ; insérer/supprimer en re-liant.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.