Linked lists · Listes chaînées
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
Nœuds joints par des liens
- Une liste chaînée est une chaîne de nœuds.
- Chaque nœud contient une pièce de données et un lien vers le nœud suivant.
- Le dernier nœud pointe vers
None, ce qui marque la fin.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
Un nœud est un petit enregistrement
- Nous pouvons stocker un nœud dans un dictionnaire :
{"data": ..., "next": ...}. "data"contient la valeur ;"next"contient le nœud suivant (ouNone).- Le premier nœud est appelé la tête de la liste.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
Parcourir la liste
- Commencez à la tête et suivez chaque lien
"next". - Arrêtez-vous lorsque vous atteignez
None. - Cette visite de chaque nœud s'appelle la traversée.
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
Pourquoi une liste chaînée ?
- Vous pouvez insérer ou supprimer un nœud en modifiant les liens — pas de déplacement d'éléments.
- Un tableau aurait dû déplacer chaque élément après le changement.
- Mais une liste chaînée n'a pas d'index : pour atteindre l'élément 5, vous devez marcher depuis la tête.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
En pseudocode Cambridge
- L'examen stocke les nœuds dans un tableau ;
Nextest l'index du nœud suivant, etNULLmarque la fin.
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
Erreurs courantes
- Ne perdez jamais le pointeur
head, sinon toute la liste devient inaccessible. - Le dernier nœud pointe vers
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
À vous maintenant
- Un nœud est un dict
{"data": ..., "next": ...}. Suivez"next"pour parcourir la chaîne. - Appuyez sur Vérifier la réponse pour tester votre code.
Nodes linked by pointers · Nœuds liés par des pointeurs
Each node points to the next; you insert/delete by re-linking. · Chaque nœud pointe vers le suivant ; vous insérez/supprimez en re-liant.
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · Construisez une liste chaînée 1 → 2 → 3 en utilisant des dictionnaires. Créez les trois nœuds, liez chacun au suivant, et pointez head vers le premier. Le "next" du dernier nœud doit être None.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · Parcourez la liste chaînée en partant de head et additionnez le "data" de chaque nœud. Stockez le total dans total (la réponse est 60).
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write length(head) that returns · rendements how many nodes are in the linked list. An empty list (head is None) has length 0. · Écrivez length(head) qui retourne le nombre de nœuds dans la liste chaînée. Une liste vide (head est None) a une longueur de 0.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.