Listes chaînées

Une liste chaînée conserve l’ordre de la séquence dans les références entre des nœuds alloués séparément, plutôt que dans des emplacements contigus.

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: "Node | None" = None

Variantes et invariants

Les nœuds simplement chaînés pointent vers l’avant ; la queue pointe vers None.
Les nœuds doublement chaînés pointent vers l’avant et l’arrière ; les mises à jour doivent préserver les deux directions.
Les listes circulaires relient la queue à une extrémité et exigent une règle d’arrêt explicite pour le parcours.

Conserver les champs tête, queue et taille améliore certaines opérations, mais crée davantage d’invariants que chaque mutation doit préserver.

Modèle de coût

Opération	Liste simplement chaînée
Accès/recherche par position ou valeur	$O(n)$
Insertion après un nœud connu	$O(1)$
Suppression après un prédécesseur connu	$O(1)$
Ajout avec une queue maintenue	$O(1)$
Suppression de la queue	$O(n)$

L’affirmation d’une insertion ou suppression en temps constant exclut le coût de recherche du nœud. Une liste doublement chaînée peut supprimer un nœud connu en $O(1)$ puisqu’elle connaît aussi son prédécesseur.

Compromis

Les listes chaînées offrent une identité stable des nœuds et des raccordements locaux peu coûteux, mais paient les références, l’allocation, le suivi des pointeurs et une moins bonne localité du cache. Elles sont utiles à l’intérieur de structures comme les listes intrusives et les chaînes de tables de hachage, mais un tableau dynamique reste généralement le meilleur choix par défaut pour une séquence.

Raccorder sans perdre la suite

La construction d’une liste simplement chaînée modifie les liens plutôt que de déplacer les valeurs restantes. Avec Node défini plus haut :

head = Node(10, Node(30))
pred = head
pred.next = Node(20, pred.next)
assert head.next.value == 20
assert head.next.next.value == 30

removed = pred.next
if removed is None:
    raise IndexError("no successor to remove")
pred.next = removed.next
removed.next = None
assert head.next.value == 30

Le nouveau nœud doit recevoir l’ancien successeur avant de rediriger le prédécesseur. Sinon, la suite peut devenir inaccessible. La suppression contourne le nœud ; effacer son lien le détache sans détruire les autres références vers lui.

Ce petit exemple ne conserve que la tête. Un conteneur complet doit aussi actualiser la queue lors d’un ajout après l’ancienne queue ou du retrait du dernier nœud, et modifier la taille une seule fois. À vide, tête et queue valent None et la taille vaut zéro ; retirer l’unique élément doit rétablir cet état. L’insertion en tête utilise head = Node(value, head), faute de prédécesseur. Une sentinelle sans valeur métier peut ramener ce cas à un raccordement ordinaire.

Le tableau compte un nombre constant d’opérations sur les liens et suppose un traitement des éléments à coût fixe ; l’allocation et la récupération de mémoire n’ont pas de garantie universelle de latence. Un « nœud connu » doit appartenir à cette liste. Partager un nœud déjà chaîné entre deux listes, ou le relier accidentellement à lui-même, brise la propriété ou la terminaison, même si chaque affectation prend un temps constant.

Source

Open Data Structures : listes chaînées

Explorer les liens

Citée par (4)

Sur les mêmes sujets (7)

Ouvrir le réseau

Variantes et invariants​

Modèle de coût​

Compromis​

Raccorder sans perdre la suite​

Source​