Leçon 10 : Listes chaînées

Imagine une chasse au trésor : chaque indice contient une valeur et une piste vers l'indice suivant, et pour atteindre le cinquième il faut les suivre un par un. C'est une « liste chaînée » (linked list) — une chaîne de « nœuds » (nodes). L'avantage : insérer ou supprimer au milieu est en O(1), il s

Une liste chaînée, c'est comme une chasse au trésor : chaque indice contient une valeur et une piste vers la suite. Pour atteindre le cinquième indice, il faut suivre les pistes une par une — impossible de sauter directement au milieu comme dans un tableau, où on peut accéder à n'importe quelle case instantanément.

classe (class): Un modèle pour une petite boîte avec des champs. class Node définit une boîte à deux champs : val (la valeur) et next (un pointeur vers le nœud suivant). Node(1) crée une telle boîte, et self signifie simplement « cette boîte ».
liste chaînée: Une structure de données faite de nœuds, chacun contenant une valeur et un pointeur next vers le nœud suivant ; insertion/suppression en O(1) à côté d'un nœud connu, mais accès par position en O(n).
nœud (node): L'élément de base d'une liste chaînée : un petit objet qui contient une valeur (val) et un pointeur (next) vers le nœud suivant, ou None à la fin.
localité de cache (cache locality): À quel point les données utilisées ensemble sont stockées proches en mémoire ; un tableau contigu est ami du cache, tandis que des nœuds de liste chaînée dispersés le sont moins.