Listes

Listes chaînées

Introduction

Une liste chaînée ou liste liée (en anglais linked list) désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type, dont la représentation en mémoire de l'ordinateur est une succession de cellules faites d'un contenu et d'un pointeur vers une autre cellule. De façon imagée, l'ensemble des cellules ressemble à une chaîne dont les maillons seraient les cellules.

L'accès aux éléments d'une liste se fait de manière séquentielle : chaque élément permet l'accès au suivant (contrairement au tableau dans lequel l'accès se fait de manière directe, par adressage de chaque cellule du tableau).

Principe

Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, un pointeur vers un élément qui lui est contigu dans la liste. L'usage d'une liste est souvent préconisé pour des raisons de rapidité de traitement, lorsque l'ordre des éléments est important et que les insertions et les suppressions d'éléments quelconques sont plus fréquentes que les accès.

En effet, les insertions en début ou fin de liste et les suppressions se font en temps constant car elles ne demandent au maximum que deux écritures. En revanche, l'accès à un élément quelconque nécessite le parcours de la liste depuis le début jusqu'à l'index de l'élément choisi.

Histoire

A l'origine appelée NSS memory, les listes chaînées ont été conçues dans les années 1955-1956, par Allen Newell, Cliff Shaw et Herbert Simon de RAND Corporation. Les listes chaînées étaient la structure de donnée de base de leur langage Information Processing Language (IPL). IPL était utilisé par ses auteurs pour le développement de plusieurs programmes d'intelligence artificielle, comme Logic Theory Machine, General Problem Solver et un jeu d'échecs. Leurs travaux sur les listes chaînées sont publiés dans IRE Transactions on Information Theory en 1956 et plusieurs conférences organisées durant la période 1957 à 1959. La représentation désormais célèbre des listes chaînées, où les nœuds sont des blocs reliés ensemble par des flèches, est publiée en février 1957 dans l'article Programming the Logic Theory Machine. Allen Newell et Herbert Simon se voient décerner en 1975 le Prix Turing pour « leurs contributions fondamentales à l'intelligence artificielle, la psychologie de la compréhension humaine et la manipulation des listes ».

Les différents types de listes chaînées

Il existe plusieurs types de listes chaînées :

• les listes simplement chaînées ;
• les listes doublement chaînées ;
• les chaînes cycliques ;
• etc...

Listes simplement chaînées

Deux informations composent chaque élément (maillon, cellule ou noeud) de la liste chaînée :

• la valeur associée à l'élément (ou donnée d'exploitation) ;
• un pointeur vers l'élément suivant (ou successeur).

Comme un seul élément de la liste est pointé, l'accès se fait uniquement dans un sens. La fin de la liste est marquée par une valeur sentinelle, ici NULL. L'usage d'un noeud sentinelle est aussi possible, notamment pour les listes cycliques.

Listes doublement chaînées

La différence avec une liste simplement chaînée est que, cette fois-ci, un pointeur vers l'élément précédent (ou prédécesseur) est ajouté. Ainsi l'accès peut se faire indifféremment dans les deux sens : de successeur en successeur, ou de prédécesseur en prédécesseur.

Cette structure est plus coûteuse en mémoire (un pointeur supplémentaire par élément) et en nombre d'instructions pour la mise à jour : une insertion coûte quatre copies de pointeurs, contre deux dans le cas d'une liste simplement chaînée.

En revanche, cela permet d'opérer une insertion avant ou après un élément, sans nécessairement disposer d'un pointeur sur un voisin, alors qu'une liste simplement chaînée n'autorise une insertion qu'à une seule position par rapport à un élément : en successeur ou (exclusivement) en prédécesseur.

Il est également possible de contrôler l'intégrité d'une liste doublement chaînée en vérifiant le chaînage double.

L'usage d'un noeud sentinelle est peut être utilisée pour les listes doublement chaînée, cyclique ou pas, afin d'éviter les parcours infinis et les erreurs d'accès mémoire.

Vidéo sur les listes chaînées

Les listes chaînées par Foxxpy : Mathématiques et algorithmie (32:01)

Interface (primitives)

Il n’existe pas de normalisation pour les primitives de manipulation de listes. Les plus fréquentes sont :

• est_vide(L) : renvoie vrai si la liste L est vide ;
• taille(L) : renvoie le nombre d’éléments de la liste L;
• get_dernier_maillon(L) : renvoie le dernier élément de la liste L;
• get_maillon_indice(L, i) : renvoie le maillon d’indice i ;
• ajouter_debut(L, d) : : ajoute un maillon d au début de la liste L ;
• ajouter_fin(L, d) : ajoute un maillon d à la fin de la liste L ;
• inserer_apres(L, i, M) : insère un maillon M à l’indice i
• supprimer_apres(L, M) : supprime le maillon qui suit le maillon M ;
• etc ...

Implémentation en Python

On peut implémenter un maillon de liste chaînée en Python à l’aide d’une classe Maillon :

🐍 Editeur

class Maillon:
    def __init__(self):
        self.val = None
        self.suiv = None  # Pas de maillon suivant

Son attribut suiv est de type Maillon, ou bien vaut None si le maillon est le dernier de la liste.

Et une liste chaînée s’implémente par une classe ListeChainee :

🐍 Editeur

class ListeChainee:

    def __init__(self):
        self.tete = None  # Liste vide

Son attribut tete est de type Maillon, ou bien vaut None si la liste est vide.

On peut alors créer une liste ainsi :

🐍 Editeur

L = ListeChainee()
M1, M2 = Maillon(), Maillon()
M1.suiv = M2
L.tete = M1

On implémente la fonction est_vide(L) simplement de cette manière :

🐍 Editeur

def est_vide(L):
    """
    Fonction
    """
    return L.tete is None

On peut aussi implémenter la méthode est_vide de la classe ListeChainee ainsi :

🐍 Editeur

    def est_vide(self):
        """
        Méthode de la classe ListeChainee
        """
        return self.tete is None

Implémentations de listes

Liste implémentée avec un tableau (applet Java)

Liste implémentée avec une liste chaînée (applet Java)

Tri d'une liste avec une pile

Octave flush

Tri d'une liste avec 3 files

Décade flush