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 liste 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 1 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.