|
Liste (informatique) Pour les articles homonymes, voir Liste (homonymie). En informatique, une liste est un type de données abstrait 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 types de données plus complexes comme la pile, la file, les arbres, etc. L'importance de la liste comme type 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. PrimitivesVoici 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 :
Primitives auxiliaires fréquemment rencontrées :
Types de listeUne 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 implémentations possibles du type liste :
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 :
À 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. Références |
