Listes comme structures abstraites et listes chaînées

La liste abstraite et son organisation concrète

Une liste abstraite représente une suite ordonnée d’éléments. Son interface peut permettre de consulter une position, d’insérer ou de retirer un élément. Elle ne doit pas être confondue automatiquement avec le type list de Python. Celui-ci possède sa propre réalisation ; la liste chaînée étudiée ici constitue une autre manière de représenter une suite.

Dans une liste simplement chaînée, chaque maillon conserve une valeur et une référence au suivant. Une référence de tête donne accès au premier maillon. Le dernier pointe vers une absence de maillon, représentée ici par None. Une liste vide possède directement une tête égale à None.

Suivre les références pour accéder aux valeurs

Pour atteindre la troisième valeur, on part de la tête et on suit deux liens. Le troisième maillon n’est pas nécessairement placé physiquement près des autres en mémoire. L’ordre de la liste est défini par les références, pas par les adresses croissantes ou par les noms dessinés sur le schéma.

L’accès à un rang demande donc un parcours depuis la tête dans cette réalisation simple. On ne bénéficie pas de l’accès direct par indice d’un tableau. Cette différence de coût est importante pour choisir une structure adaptée : une liste chaînée n’est pas universellement plus rapide qu’une liste Python.

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

tete = Maillon(7, Maillon(12, Maillon(5)))

Pour atteindre le rang k compté à partir de zéro, il faut suivre k références depuis la tête, à condition que ce rang existe. Le nom du maillon ne code pas nécessairement ce rang. Après une insertion, les rangs changent mais les anciens maillons peuvent conserver leur identité et leur position physique. Le schéma doit représenter les liens logiques plutôt qu’un déplacement imaginaire de toutes les valeurs.

Insérer en préservant l’accès à la suite

Pour insérer 9 en tête, on construit un nouveau maillon dont le suivant est l’ancienne tête, puis on remplace la tête par ce nouveau maillon. La suite précédente reste accessible. Pour insérer après un maillon p, on relie le nouveau maillon à p.suivant avant de faire pointer p vers lui.

L’ordre des affectations compte. Remplacer d’abord p.suivant sans conserver son ancienne valeur peut faire perdre l’accès à la suite. Une représentation graphique des références avant et après l’opération permet de vérifier que chaque élément attendu reste atteignable.

Retirer un maillon et traiter les limites

Retirer la tête revient à remplacer la référence de tête par celle du maillon suivant. Retirer un maillon intérieur consiste à faire pointer son prédécesseur vers son successeur. Cela supprime le maillon du parcours de la liste, sans nécessairement effacer immédiatement son objet si d’autres références le désignent.

Les cas vide, un seul élément et insertion en fin demandent une attention particulière. L’insertion elle-même nécessite peu de modifications quand le prédécesseur est déjà connu ; le trouver par un parcours peut néanmoins avoir un coût linéaire. Il faut donc distinguer la localisation de la position et la modification des liens.

Un retrait rompt le chemin depuis la tête vers un maillon. Si une autre variable conserve une référence sur ce maillon, son objet peut encore être accessible par cette variable. Dire « supprimé de la liste » ne signifie donc pas automatiquement « objet immédiatement détruit ». Cette distinction apparaît dès qu’on raisonne sur les références, sans avoir besoin d’étudier la gestion détaillée de mémoire.

Exemple suivi : insérer entre deux maillons

La tête pointe vers A(7), A vers B(12), B vers C(5) et C vers None. Pour insérer N(9) après A, on écrit d’abord N.suivant=A.suivant : N pointe alors vers B. Puis A.suivant=N place N sur le chemin principal. Le parcours donne A,N,B,C, soit 7,9,12,5.

Deux contrôles suffisent pour comprendre cette opération locale : tous les maillons attendus restent accessibles depuis la tête, et le parcours atteint toujours la fin. Si l’on inverse les affectations sans sauvegarde, N risque de pointer vers lui-même et B,C ne sont plus accessibles par ce chemin. Dessiner les références avant chaque affectation permet de repérer l’erreur avant même d’écrire une boucle de parcours.

Rangs autorisés, vide et insertion en fin

Une liste de taille n possède des éléments aux rangs 0 à n-1, mais n+1 positions d’insertion, de 0 à n inclus. Le rang n désigne un ajout après le dernier élément ; il ne désigne aucun élément à retirer. Pour une liste vide, seul le rang d’insertion 0 est valide, et aucun retrait ne l’est.

Sur la liste 7,12,5, insérer au rang 3 ajoute en fin. Le nouveau maillon pointe vers None et l’ancien dernier pointe vers lui. Retirer au rang 0 modifie la tête ; retirer au rang 2 nécessite le prédécesseur de ce rang. Dans une réalisation sans référence supplémentaire, rechercher ce prédécesseur demande un parcours. Le coût de localisation peut dominer la modification de deux liens, même si l’opération finale sur les références est courte.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Confondre liste Python et liste chaînée.

Elles peuvent représenter une suite, mais leurs organisations et coûts diffèrent. Précisez la réalisation étudiée.

Modifier un lien avant de conserver sa destination.

La partie suivante peut devenir inaccessible ou former un cycle involontaire.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2025 · Asie · Jour 1 - Remplacement : Pseudo-tri dictatorial : listes, maillons et piles

Le prochain pas

• Les piles : comprendre le fonctionnement LIFO
• Les files : comprendre le fonctionnement FIFO
• Mutabilité, références et effets de bord

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.