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 dudit 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
À l'origine appelée NSS memory, les listes chaînées ont été conçues dans les années 1955-1956, par Allen Newell, (en) Cliff Shaw et Herbert Simon de RAND Corporation. Les listes chaînées étaient la structure de donnée de base de leur langage (en) 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[1]. 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[2]. 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 ».
Types de listes chaînées
Il existe plusieurs types de listes chaînées, caractérisés principalement par deux attributs :
- le chaînage,
- le cycle.
Chaînage
Liste simplement chaînée
Comme on le voit sur le schéma ci-contre, deux informations composent chaque élément 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 nœud sentinelle est aussi possible, notamment pour les listes cycliques.
Liste doublement chaînée
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 nœud 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.
Cycle
Le cycle est la propriété que présente une liste chaînée de former une boucle (ou chaîne fermée). La notion de début de chaîne ou de fin de chaîne disparaît.
Une liste cyclique (ou circulaire) est créée lorsque le dernier élément possède une référence vers le premier élément (si la liste est doublement chaînée, alors le premier élément possède aussi une référence vers le dernier).
L'utilisation de ce type de liste requiert des précautions pour éviter des parcours infinis, par exemple, lors d'une recherche vaine d'élément.
Primitives
On définit un certain nombre de primitives, qui sont des fonctions de test, d'accès en lecture ou en écriture dont la liste permet une exécution efficace.
Il n'existe pas de normalisation pour les primitives de manipulation de liste. Leurs noms sont donc indiqués de manière informelle. Voici la liste des plus couramment utilisées :
- « Placement sur le premier élément » : place l'index sur le premier élément de la liste.
- « Placement sur le dernier élément » : place l'index sur le dernier élément de la liste.
- « Placement sur l'élément suivant » : place l'index sur l'élément qui suit l'élément courant si c'est possible.
- « Placement sur l'élément précédent » : place l'index sur l'élément qui précède l'élément courant si c'est possible.
- « Liste est-elle vide ? » : Retourne vrai si la liste est vide, faux sinon.
- « L'élément courant est-il le premier ? » : Retourne vrai si l'élément courant est le premier élément de la liste, faux sinon.
- « L'élément courant est-il le dernier ? » : Retourne vrai si l'élément courant est le dernier élément de la liste, faux sinon.
- « Nombre d'éléments » : renvoie le nombre d'éléments dans la liste.
- « Ajouter en queue » : ajoute un élément après le dernier élément de la liste (efficace seulement pour une liste doublement chaînée).
- « Ajouter en tête » : ajoute un élément avant le premier élément de la liste.
- « Insertion » : insère un élément avant l'élément courant.
- « Remplacement » : Remplace l'élément courant.
- « Suppression » : Supprime l'élément courant.
Ajout d'un élément
Voici la représentation schématique de l'ajout d'un nouvel élément f après un élément e se trouvant dans une liste simplement chaînée. La procédure se fait en deux étapes :
- le successeur de e devient le successeur de f ;
- f devient le successeur de e.
 |
 |
 |
Implémentation
Voici un exemple d'implémentation d'un élément dans le langage Pascal (liste d'entiers simplement chaînée) :
type
liste = ^jonction;
jonction = record
contenu: longint;
suivant: liste;
end;
Et un autre exemple en C de l'implémentation d'un élément d'une liste d'entiers doublement chaînée :
struct liste {
int donnee;
struct liste * precedent;
struct liste * suivant;
};
Exemple complet
Cet exemple en C++ montre une classe liste, avec un index mobile pouvant être déplacé de manière basique (premier et dernier élément, élément suivant et précédent). Seule l'insertion au début, la suppression à la fin, et la modification sont autorisés. Pour commencer, une structure élément identique à la structure liste précédente mais renommée pour éviter une confusion avec la classe liste:
// Structure element
struct element {
int var;
element * suivant;
element * precedent;
};
Ensuite, la classe liste, qui compte comme seul champ l'index. Pour simplifier cet exemple, la classe n'a pas de destructeur, et causera des fuites de mémoire. De même les constructeurs et opérateurs d'affectation chargés de la copie et du déplacement doivent être écrit dans un code correct. Toutes les fonctions membres autres que le constructeur seront détaillées dans les sections suivantes. Elles doivent être recopiées dans la classe.
// Classe liste, chargée d'accéder aux différents éléments
class liste {
public:
liste() = default;
bool est_vide() const { return index == nullptr; }
private:
element * index = nullptr;
};
Placer l'index au début ou à la fin
La fonction membre début, permet de mettre l'index sur le premier élément de la liste.
void debut() {
if (est_vide())
return;
while (index->precedent != nullptr) {
index = index->precedent;
}
}
La fonction membre fin permet de mettre l'index sur le dernier élément de la liste.
void fin() {
if (est_vide())
return;
while (index->suivant != nullptr) {
index = index->suivant;
}
}
Ajouter ou supprimer une valeur
La fonction membre insertion début, ajoute un élément au début de la liste, et met l'index sur ce nouvel élément.
void insertion_debut(int var) {
element * n = new element;
debut();
n->precedent = nullptr;
n->suivant = index;
n->var = var;
if (not est_vide())
index->precedent = n;
index = n;
}
La fonction membre supprimer fin, supprime le dernier élément de la liste et déplace l'index au dernier élément de la liste.
void supprimer_fin() {
assert(not est_vide());
fin();
index = index->precedent;
delete index->suivant;
index->suivant = nullptr;
}
Déplacer l'index sur l'élément suivant ou précédent
La fonction membre deplacer déplace l'index sur l'élément suivant si son argument est vrai ou sur l'élément précédent si l'argument est faux.
void deplacer(bool en_avant) {
if (est_vide())
return;
if (en_avant) {
if (index->suivant == nullptr)
return;
index = index->suivant;
}
else {
if (index->precedent == nullptr)
return;
index = index->precedent;
}
}
Lire la valeur de l'index
La fonction membre lire retourne la valeur de l'élément.
int lire() const {
if (est_vide())
return 0;
return index->var;
}
Modifier la valeur de l'index
La fonction membre modifier modifie la valeur de l'élément.
void modifier(int var) {
if (est_vide())
return;
index->var = var;
}
Notes
- ↑ Proceedings of the Western Joint Computer Conference en 1957 et 1958 et Information Processing en 1959 (première réunion de l'International Conference on Information Processing de l'UNESCO)
- ↑ Programming the Logic Theory Machine de Allen Newell et Cliff Shaw, Proceedings of the 1957 Western Joint Computer Conference, février 1957
Structures de données associées
Il existe plusieurs structures de données qui peuvent reposer sur une implémentation de liste chainée.
Les piles et les files sont souvent implémentées à l'aide d'une liste chaînée, en n'utilisant que quelques fonctions de cette dernière.
La liste à sauts est constituée de listes chainées sur plusieurs niveaux référençant des cellules du niveau suivant, permettant de parcourir rapidement un grand nombre d'éléments dans une liste, puis de descendre d'un niveau jusqu'au plus bas, qui constitue la liste en tant que telle.
Un arbre binaire peut être vu comme un type de liste chaînée dont les éléments sont eux-mêmes des listes chaînées de même type. Par conséquent, chaque cellule peut contenir une référence vers d'autres listes chainées, qui constituent les sous-arbres de ce nœud.
Une liste chaînée déroulée est une liste chaînée dont chaque cellule contient un tableau de valeurs. Cela améliore les performances du cache, car les éléments sont davantage regroupés en mémoire, et diminue l'usage de la mémoire, car moins de métadonnées sont stockées pour chaque élément.
Une table de hachage peut utiliser des listes chaînées pour stocker les chaînes d'éléments dont la position par l'algorithme de hachage est la même.
Un tas, bien que presque toujours implémenté à l'aide d'un tableau, partage certaines propriétés d'ordonnancement avec une liste chaînée. Au lieu de références directes entre les cellules, les indices des données suivantes et précédentes sont calculés à partir de l'indice de la donnée courante.
Une liste auto-organisée réorganise ses nœuds en fonction d'une heuristique afin de réduire les temps d'accès aux données en gardant les cellules les plus fréquemment consultés en tête de liste.