Listes chaînées
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.
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"])
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"]
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.
En pseudocode Cambridge
- L'examen stocke les nœuds dans un tableau ;
NextIndexest l'index du nœud suivant, etNULLmarque la fin.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Erreurs courantes
- Ne perdez jamais le pointeur
head, sinon toute la liste devient inaccessible. - Le dernier nœud pointe vers
None.
À 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.
Nœuds liés par des pointeurs
Chaque nœud pointe vers le suivant ; vous insérez/supprimez en re-liant.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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).
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
É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.
Cliquez sur Exécuter pour voir le résultat ici.