Les listes chaînées : cours de Terminale NSI

Tu connais déjà la liste Python : on écrit t[3] et on obtient directement le quatrième élément. Tu l'utilises sans te demander comment elle est rangée dans la mémoire de l'ordinateur. En Terminale, on change de point de vue : on construit soi-même des structures de données avec des objets, pour comprendre ce qu'elles coûtent et à quoi elles servent.

La liste chaînée est la première de ces structures. Elle te sert ensuite de modèle pour les piles, les files et les arbres, qui reposent sur la même idée : des objets qui se référencent les uns les autres.

En informatique, une liste est un type de données abstrait qui regroupe des données de façon à pouvoir y accéder librement, contrairement aux piles et aux files, dont l'accès est imposé (LIFO ou FIFO) ³. La liste sert de base à des types plus complexes comme la pile, la file ou les arbres ³.

Pour bien situer l'intérêt, comparons avec le tableau. Les données d'un tableau sont contiguës en mémoire, ce qui impose une taille fixe ³. Certains langages de haut niveau proposent des tableaux dont la taille varie, comme la liste Python : ils restent rangés d'un seul bloc en mémoire et, quand la place manque, ils sont recopiés dans une zone plus grande. À l'inverse, la taille d'une liste chaînée n'est limitée que par la mémoire disponible : pour l'agrandir, il suffit de créer une nouvelle cellule et de faire pointer vers elle une cellule déjà présente ³.

Une cellule est un petit objet à deux composantes : la valeur qu'elle transporte et le lien vers la cellule suivante. Autrement dit, en plus de sa donnée, chaque élément porte une référence qui le relie à un voisin dans la liste ².

Représentons la liste $2 \to 7 \to 4 \to 9$ :

tête → [ 2 | • ] → [ 7 | • ] → [ 4 | • ] → [ 9 | None ]

Chaque rectangle est une cellule : à gauche la valeur, à droite le lien. La dernière cellule ne pointe vers rien : son lien vaut None. C'est ce None qui signale « la chaîne s'arrête ici ». Une liste vide, elle, est une tête qui vaut directement None.

Construisons à la main la liste $2 \to 7 \to 4$, en commençant par la fin :

c3 = Cellule(4)          # dernière cellule, suivant = None
c2 = Cellule(7, c3)      # 7 pointe vers 4
c1 = Cellule(2, c2)      # 2 pointe vers 7
l = Liste()
l.tete = c1

Les trois variables c1, c2, c3 ne servent qu'à construire : une fois la liste faite, seule l.tete compte. Avec l.tete.suivant.valeur, on obtient 7.

Comme on ne connaît que la tête, on ne peut pas sauter directement au milieu. Pour voir tous les éléments, on suit les liens de cellule en cellule. C'est l'opération de base : presque tout le reste en dérive.

Voici le calcul de la longueur, méthode de la classe Liste :

def longueur(self):
    n = 0
    courant = self.tete
    while courant is not None:
        n += 1
        courant = courant.suivant
    return n

Sur la liste vide, courant vaut None dès le départ, la boucle ne s'exécute pas et on renvoie 0. Sur $2 \to 7 \to 4$, la boucle tourne trois fois.

Pour accéder au i-ième élément (les indices commencent à 0), on avance $i$ fois :

def acces(self, i):
    courant = self.tete
    for _ in range(i):
        if courant is None:
            raise IndexError("indice trop grand")
        courant = courant.suivant
    if courant is None:
        raise IndexError("indice trop grand")
    return courant.valeur

Il faut suivre $i$ liens avant d'arriver sur la bonne cellule. Plus l'indice est grand, plus le trajet est long. C'est la grande différence avec t[i] sur un tableau, où l'on tombe directement sur la case.

Le même parcours s'écrit de façon récursive, ce qui rejoint la définition récursive de la structure : une liste est soit vide, soit une cellule suivie d'une liste. Les listes chaînées s'appuient justement sur une définition récursive, chaque élément pointant vers d'autres éléments de la liste ³.

def longueur_rec(cellule):
    if cellule is None:
        return 0
    return 1 + longueur_rec(cellule.suivant)

Le cas de base est la chaîne vide (None), le cas récursif traite la première cellule puis la suite.

Ajouter un élément revient à créer une cellule et à réarranger quelques liens. La difficulté n'est pas de coder, mais de choisir l'ordre des affectations.

On recommande souvent la liste chaînée quand l'ordre des éléments compte et qu'on insère ou retire des éléments n'importe où plus souvent qu'on ne les consulte ². C'est cohérent avec ce que tu viens de voir : insérer ne coûte que quelques liens, alors qu'accéder demande de parcourir.

Supprimer, c'est court-circuiter une cellule : on fait pointer sa précédente directement vers sa suivante. La cellule oubliée n'est plus référencée par personne, elle n'appartient plus à la liste.

Avec un seul lien par cellule, impossible de reculer. On peut enrichir la cellule.

La cellule possède alors trois attributs :

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

Cette souplesse a un prix. Il faut stocker un lien de plus par cellule, donc davantage de mémoire, et les mises à jour demandent plus d'instructions : insérer une cellule recopie quatre pointeurs, là où deux suffisent dans une liste simplement chaînée ².

En Terminale, on te demande régulièrement de justifier le choix d'une structure : liste Python, dictionnaire, pile, file, arbre, graphe… et d'expliquer en quoi elle est adaptée à l'exercice ¹. Voici de quoi argumenter sur les listes.

Une remarque sur Python lui-même : la liste Python (list) n'est pas une liste chaînée au sens de ce cours. Elle s'utilise avec des indices, et on distingue ses opérations, une question classique à l'épreuve pratique ¹ : par exemple, tab.append(i) modifie la liste existante, alors que tab = tab + [i] construit une nouvelle liste. De même, sorted(tab) renvoie une nouvelle liste triée, tandis que tab.sort() trie tab sur place. Quand tu écris ta propre classe Liste, tu dois donc programmer explicitement ces opérations.

Un peu d'histoire pour terminer. Les listes chaînées ont été conçues en 1955-1956 par Allen Newell, Cliff Shaw et Herbert Simon, de RAND Corporation ². Elles formaient la structure de base de leur langage IPL, utilisé pour développer des programmes d'intelligence artificielle ². Le langage Lisp, dont le nom vient de list processing, repose lui aussi sur la liste ³.