Liste (informatique)
En informatique, une liste est une structure de données permettant de regrouper des données de manière à pouvoir y accéder librement (contrairement aux files et aux piles, dont l'accès se fait respectivement en mode FIFO et LIFO).
La liste est à la base de structures de données plus complexes comme la pile, la file, les arbres, etc. L'importance de la liste comme structure de données est telle qu'elle est à la base du langage de programmation Lisp (de l'anglais list processing). Certains langages de programmation font la distinction entre les listes, les arrays ou encore les tuples, avec des différences notables pour chacun de ces types[1].
Primitives
Voici les primitives communément utilisées pour manipuler des listes ; il n'existe pas de normalisation pour les primitives de manipulation de listes, leurs noms respectifs sont donc indiqués de manière informelle.
Primitives de base :
- « Insérer » : ajoute un élément dans la liste. Terme anglais correspondant : « Add » ;
- « Retirer » : retire un élément de la liste. Terme anglais correspondant : « Remove » ;
- « La liste est-elle vide ? » : renvoie « vrai » si la liste est vide, « faux » sinon. Terme anglais correspondant : « IsNull » ;
- « Nombre d'éléments dans la liste » : renvoie le nombre d'éléments dans la liste. Terme anglais correspondant : « Length » dans d'autre langage <<Count>>.
Primitives auxiliaires fréquemment rencontrées :
- « Premier » : retourne le premier élément dans la liste. Terme anglais correspondant : « First » ;
- « Dernier » : retourne le dernier élément dans la liste. Terme anglais correspondant : « Last » ;
- « Prochain » : retourne le prochain élément dans la liste. Terme anglais correspondant : « Next » ;
- « Précédent » : retourne l'élément qui précède dans la liste. Terme anglais correspondant : « Previous » ;
- « Cherche » : cherche si un élément précis est contenu dans la liste et retourne sa position. Terme anglais correspondant : « Find ».
Types de liste
Une liste est un conteneur d'éléments, où chaque élément contient la donnée, ainsi que d'autres informations permettant la récupération des données au sein de la liste. La nature (les types) de ces informations caractérise un type différent de liste.
On peut distinguer, de manière générale, deux types de liste :
- les tableaux ;
- les listes chaînées.
Tableau
L'accès à un élément se fait à l'aide d'un index qui représente l'emplacement de l'élément dans la structure.
Les données présentes dans un tableau sont contiguës en mémoire. Cela induit une taille de tableau fixe, c'est-à-dire ne changeant pas ; cependant, certains langages de haut niveau fournissent des tableaux qui modifient leur taille en fonction de leur utilisation : on parle alors de tableau à taille dynamique. Mais leur implémentation utilise le principe des listes chaînées (voir plus bas).
Les tableaux peuvent également avoir plusieurs dimensions, représentées par une séquence d'indices. Dans ce cas, si n est la dimension du tableau (où n est un entier naturel non nul), les éléments du tableau de dimension 1 (le 1er indice de la séquence) pointent chacun vers un autre (sous-)tableau de dimension n-1.
Liste chaînée
Contrairement à un tableau, la taille d'une liste chaînée n'a pas de limite autre que celle de la mémoire disponible. Cette limitation est franchie par le fait que chaque élément peut pointer, suivant le type de liste chaînée, vers un ou plusieurs éléments de la liste en utilisant une définition récursive. Ainsi, pour augmenter la taille d'une liste chaînée, il suffit de créer un nouvel élément et de faire pointer certains éléments, déjà présents au sein de la liste, vers le nouvel élément.
Il existe deux grands types de liste chaînée :
- les listes simplement chaînées : chaque élément dispose d'un pointeur sur l'élément suivant (ou successeur) de la liste. Le parcours se fait dans un seul sens ;
- les listes doublement chaînées : chaque élément dispose de deux pointeurs, respectivement sur l'élément suivant (ou successeur) et sur l'élément précédent (ou prédécesseur). Le parcours peut alors se faire dans deux sens, mutuellement opposés : de successeur en successeur, ou de prédécesseur en prédécesseur.
À cela on peut ajouter une propriété : le cycle. Cette fois-ci, la liste chaînée forme une boucle. Dès qu'on atteint la « fin » de la liste et qu'on désire continuer, on se retrouve sur le « premier » élément de la liste. Dans ce cas, la notion de début ou de fin de chaîne n'a plus de raison d'être.