Listes chaînées

Introduction

Une liste chaînée permet de stocker un ensemble de valeur du même type, comme un tableau. Contrairement au tableau, en revanche, la taille de la liste chaînée peut varier au cours du temps. En effet, contrairement au tableau, la liste n'est pas allouée en une seule fois, mais chaque élément est alloué indépendamment, sous la forme d'un maillon ayant la structure suivante :

struct Télément
    flottant  valeur
    Télément* suivant
fin struct

(bien sûr, le type de l'attribut valeur peut varier selon les valeurs que l'on souhaite stocker dans la liste)

Chaque élément pointe, à l'aide de l'attribut suivant vers l'élément suivant dans la liste ; le dernier élément, par définition, n'a pas de suivant, donc son attribut suivant vaut null. Pour manipuler une liste chaînée, on manipulera un simple pointeurs sur le premier élément; comme chaque élément « connaît » l'élément suivant, on peut ainsi accéder à tous les éléments de la liste. Notons enfin que si le pointeur premier vaut null, on considérera naturellement que la liste est vide (elle ne contient aucun élément).

Allocation et libération du premier élément

Comme on l'a dit, une liste chaînée est allouée élément par élément. L'algorithme suivant insère un élément en début d'une liste. Le pointeur premier est donc un paramètre d'entrée/sortie (passé par référence) puisque le premier élément est modifié.

proc insère_en_tête (premier, val)
    entrée/sortie Télément* premier
    entrée        flottant  val
    post-relation la liste pointée par premier contient un nouvel élément,
                  dont la valeur est val

début
    /* allocation du nouvel élément */
    Télément* nouv ← nouveau Télément

    /* initialisation du nouvel élément */
    (*nouv).valeur  ← val
    (*nouv).suivant ← premier

    /* mise à jour du premier élément */
    premier ← nouv
fin

On remarquera que tous les éléments précédemment accessibles par premier restent accessibles après la modification de ce dernier, car l'ancien élément pointé par premier est maintenant accessible par (*premier).suivant.

On s'intéresse maintenant à la suppression du premier élément d'une liste chaînée non vide. La difficulté consiste à ne pas perdre l'accès aux éventuels éléments qui sont pointés par le premier.

proc libère_premier (premier)
    entrée/sortie Télément* premier
    pré-condition premier ≠ null
    post-relation premier pointe vers la même liste, privée de son premier
                  élément

début
    /* sauvegarde pour pouvoir libérer la mémoire */
    Télément* tmp ← premier

    /* on court-circuite le premier élément */
    premier ← (*premier).suivant

    /* on libère l'élément désormais inutilisé */
    libérer tmp
fin

Les procédures ci-dessus ne s'intéresse qu'au premier élément de la liste. On verra par la suite qu'elles peuvent en fait servir à allouer ou à libérer n'importe quel élément.

Vision itérative / vision récursive

Une liste chaînée est manipulée à l'aide d'un pointeur vers son premier élément. Plus généralement, tout pointeur vers Télément peut donc être vu de deux manière :

comme pointant vers un élément d'une liste,
comme pointant vers une liste, via son premier élément.

Ces deux lectures, lorsqu'on les applique à l'attribut suivant de Télément, font considérer que

Télément représente un élément, avec une valeur, et pointant vers l'élément suivant,
Télément représente une liste, avec sa première valeur, et pointant vers la liste des éléments suivants.

La première interprétation, qui est celle qu'on a utilisée en introduction, donne une vue itérative des listes chaînées. La seconde, en revanche, en donne une vue récursive. Par la suite, on montrera que tout algorithme parcourrant une liste chaînée peut être écrit de manière itérative ou récursive.

La vision récursive montre bien, par ailleurs, comment on va pouvoir utiliser les procédures d'allocation et de libération, présentées ci-dessus, pour allouer ou libérer n'importe quel élément d'une liste, en considérant que cet élément est le premier d'une sous-liste.

Recherche d'élément

Les deux fonctions suivantes n'ont pas vocation à être utilisées directement, mais consitutent plutôt une boîte à outil pour les procédures et fonctions qui vont suivre. Elles permettent de trouver dans une liste chaînée l'élément répondant à un certain critère, et retournent un pointeur vers la structure Télément correspondante. Les deux critères de recherche sont la position de l'élément dans la liste ou sa valeur.

En terme de complexité, ces deux fonctions s'exécutent dans le pire des cas en O(n) opération, où n est le nombre d'éléments contenus dans la liste.

Recherche par position

Cette fonction retourne un pointeur vers l'élément à la position pos où le premier élément a la position 1. Si la liste contient moins de pos éléments, le pointeur null est retourné.

fonc Télément* recherche_par_position (premier, pos)
    entrée Télément* premier
    entrée entier    pos
    pré-condition p > 0
    post-relation cf. ci-dessus

/* version itérative */
début
    Télément* c ← premier
    entier    p ← 1
    tant que c ≠ null et p < pos faire
        c ← (*c).suivant
        p ← p + 1
    fin tant
    retourne c
fin

/* version récursive */
début
    si premier = null ou pos = 1 alors
        retourne premier
    sinon
        retourne recherche_par_position ((*premier).suivant, pos - 1)
    fin si
fin

La version récursive mérite un commentaire.

La clause alors traite d'un coup deux cas simples : la liste vide (premier = null) et la liste non-vide dont on recherche le premier élément (pos = 1). Dans les deux cas, c'est bien le pointeur premier qu'il convient de retourner, soit parcequ'il est nul, soit parcequ'il pointe vers le premier élément.

La clause sinon traite le cas complexe. Si l'on cherche, par exemple, le deuxième élément de la liste, on cherche donc le premier élément de la liste des suivants si l'on cherche le troisième, c'est le deuxième de la liste des suivants, et ainsi de suite. Cela justifie de passer l'argument pos - 1 dans l'appel récursif.

Recherche par valeur

Cette fonction retourne un pointeur vers le premier élément trouvé dont la valeur est val, ou le pointeur null si aucun élément n'a cette valeur.

fonc Télément* recherche_par_valeur (premier, val)
    entrée Télément* premier
    entrée flottant  val
    post-relation cf. ci-dessus

/* version itérative */
début
    Télément* c ← premier
    tant que c ≠ null et (*c).valeur ≠ val faire
        c ← (*c).suivant
    fin tant
    retourne c
fin

/* version récursive */
début
    si premier = null ou (*premier).valeur = val alors
        retourne premier
    sinon
        retourne recherche_par_valeur ((*premier).suivant, val)
    fin si
fin

Manipulation de listes chaînées

On présente ici différentes fonctions et procédures permettant de consulter et modifier une liste chaînée. Il est important de constater que toutes ces procédures ont une complexité dans le pire des cas en O(n), où n est le nombre d'éléments contenus dans la liste. En comparaison, les mêmes opérations sur un tableaux sont en O(1), c'est à dire qu'elles ne dépendent pas de la taille du tableau. Cette complexité est la contrepartie de la souplesse qu'offrent les listes chaînées en terme de gestion de la mémoire (possibilité de réduire et surtout d'agrandir leur taille).

Taille d'une liste chaînée

fonc entier taille (premier)
    entrée Télément* premier
    post-relation retourne le nombre d'éléments dans cette liste

/* version itérative */
début
    Télément* c ← premier
    entier    n ← 0
    tant que c ≠ null faire
        c ← (*c).suivant
        n ← n + 1
    fin tant
    retourne n
fin

/* version récursive */
début
    si premier = null alors
        retourne 0
    sinon
        retourne 1 + taille ((*premier).suivant)
    fin si
fin

Lecture de la valeur à une position donnée

proc lire_valeur (premier, pos, val, trouvé)
    entrée Télément* premier
    entrée entier    pos
    sortie flottant  val
    sortie logique   trouvé
    pré-condition pos > 0
    post-relation si pos > taille (premier), trouvé vaut FAUX
                  sinon, trouvé vaut VRAI, val a la valeur de l'élément n° pos

début
    Télément* e ← recherche_par_position (premier, pos)
    si e = null alors
        trouvé ← FAUX
    sinon
        trouvé ← VRAI
        val    ← (*e).valeur
    fin si
fin

Modification de la valeur à une position donnée

proc change_valeur (premier, pos, val, trouvé)
    entrée Télément* premier
    entrée entier    pos
    entrée flottant  val
    sortie logique   trouvé
    pré-condition pos > 0
    post-relation si pos > taille (premier), trouvé vaut FAUX
                  sinon, trouvé vaut VRAI, l'élément n° pos prend la valeur val

début
    Télément* e ← recherche_par_position (premier, pos)
    si e = null alors
        trouvé      ← FAUX
    sinon
        trouvé      ← VRAI
        (*e).valeur ← val
    fin si
fin

Pré-condition portant sur la position

On peut remarquer que les pré-conditions des algorithmes ci-dessus (et de ceux qui suivront) imposent à la position d'être supérieure à zéro, mais pas d'être inférieure à la taille de la liste. Ce dernier cas est testé à l'intérieur des algorithmes eux-mêmes (généralement en testant que le pointeur retourné par recherche_par_position n'est pas nul).

Il pourrait sembler judicieux d'ajouter cette condition aux pré-conditions, déléguant à l'utilisateur de l'algorithme cette vérification, mais ce serait une erreur car :

ce test ne « coûte » rien dans nos algorithmes, qui doivent de toute manière parcourir la liste ;
s'il était délégué à l'utilisateur, celui-ci devrait appeler la fonction taille, qui effectuerait un parcours supplémentaire de la liste.

Il est donc plus « économique » de garder ce test à l'intérieur de nos algorithmes.

Allocation et libération d'un élément quelconque

On peut maintenant utiliser les procédures recherche_par_position et recherche_par_valeur pour insérer ou supprimer n'importe quel élément d'une liste chaînée. Ces opérations sont en O(p) ou p est la position de l'élément à insérer ou supprimer. Notons que ces opérations n'ont pas de contrepartie exacte sur les tableaux puisque ceux-ci contiennent un nombre fixe d'éléments.

Insertion d'un élément à une position donnée

Cette procédure insère un nouvel élément à la position pos et avec la valeur val. La position peut-être comprise entre 1 (insertion en tête) et taille (premier) + 1 (insertion après le dernier élément). Si la position est trop élevée, le paramètre inséré vaudra FAUX (dans tous les autres cas, il vaudra VRAI).

proc insère_pos (premier, pos, val, inséré)
    entrée/sortie Télément* premier
    entrée        entier    pos
    entrée        flottant  val
    sortie        logique   inséré
    pré-condition pos > 0
    post-relation cf. ci-dessus

début
    inséré ← VRAI
    si pos = 1 alors
        insère_en_tête (premier, val)
    sinon
        Telt* précédent ← recherche_par_position (premier, pos - 1)
        si précédent ≠ null alors
            insère_en_tête ((*précédent).suivant, val)
        sinon
            inséré ← FAUX
        fin si
    fin si
fin

On notera bien que le premier paramètre de insère_en_tête est un paramètre d'entrée/sortie. Lorsqu'on lui passe (*précédent).suivant, l'attribut suivant de l'élément pointé par précédent sera donc modifié (pour pointer vers l'élément nouvellement créé).

Insertion d'un élément à une position donnée

Cette procédure supprime l'élément à la position pos. La position peut-être comprise entre 1 et taille (premier). Si la position est trop élevée, le paramètre supprimé vaudra FAUX (dans tous les autres cas, il vaudra VRAI).

proc libère_pos (premier, pos, val, supprimé)
    entrée/sortie Télément* premier
    entrée        entier    pos
    sortie        logique   supprimé
    pré-condition pos > 0
    post-relation cf. ci-dessus

début
    supprimé ← VRAI
    si pos = 1 alors
        libère_premier (premier)
    sinon
        Telt* précédent ← recherche_par_position (premier, pos - 1)
        si précédent ≠ null alors
            libère_premier ((*précédent).suivant)
        sinon
            supprimé ← FAUX
        fin si
    fin si
fin

On notera bien que le premier paramètre de libère_premier est un paramètre d'entrée/sortie. Lorsqu'on lui passe (*précédent).suivant, l'attribut suivant de l'élément pointé par précédent sera donc modifié (pour pointer vers le successeur de l'élément supprimé).