Pour l'instant, le seul moyen dont vous disposez pour représenter un ensemble de données est le tableau. Dans un tableau chaque donnée (de même type) possède un indice définissant sa position dans le tableau.
Les listes sont une autre manière de représenter un ensemble de données n'utilisant pas d'indice et basée sur les pointeurs.
Il serait assez difficile et peu pédagogique de présenter les listes chainées dans un cas général abstrait. Nous allons donc baser toutes nos explications sur un exemple qui sera facile à généraliser: une liste de structures de type Ville dont voici la déclaration:
Type
PVille = ^Ville;
Ville = record
Nom : String;
CodePostal : String;
Suivant : PVille;
end;
Le champ Suivant sert à mémoriser l'adresse de l'élément suivant de la liste. Dans le cas général, il peut porter n'importe quel nom, mais il doit exister un champ jouant ce rôle.
La liste, quand à elle, est également un pointeur qui contient l'adresse du premier élément de la liste.
Dans notre exemple, on pourrait donc représenter une liste de ville par une variable L de type PVille.
Voici par exemple une liste simplement chainée contenant quatre villes.
L contient l'adresse de la première ville (Ribeauvillé). Le champ Suivant de la première ville contient l'adresse de la seconde (Kingersheim) etc...
Le dernier élément de la liste (Nancy) n'a pas d'élément suivant. Son champ Suivant contient la valeur NIL, qui représente en Pascal une adresse inexistante.
Remarque: une liste vide se représente simplement par un pointeur de liste égal à NIL (L = NIL dans notre exemple).
Pour effectuer un traitement sur chaque élément d'une liste, il est nécessaire de savoir parcourir ses éléments. On utilisera pour cela un pointeur, qui prendra successivement la valeur des adresses de chaque élément de la liste. Voici par exemple comment parcourir une liste de villes dont l'adresse est contenue dans le pointeur L:
Var p : PVille;
p := L ;
While p <> NIL Do
begin
Traitement de l'élément pointé par p
p := p^.Suivant;
end;
Considérons le problème suivant: on dispose d'une liste de villes L et d'une structure de type ville pointée par un pointeur p. Comment procéder pour ajouter cette structure dans la liste ?
Ajouter l'élément p^ au début de liste L, il suffit de faire:
p^.Suivant := L ; L := p ;
La première affectation 'accroche' la structure à la liste et la deuxième met à jour l'adresse de la liste qui devient celle de p.
Remarque: cette méthode fonctionne également avec une liste vide. En effet, dans ce cas L vaut NIL avant l'adjonction. Après l'adjonction, en aura bien une liste d'un élément (p^) avec L = p et p^.Suivant = NIL.
La figure suivante illustre l'adjonction en début de liste de la ville Ribeauvillé.
Avant l'adjonction:
Après l'adjonction:
Supposons à présent que la liste n'est pas vide et que l'on souhaite insérer un élément après un certain élément de la liste.
Soit p l'adresse du nouvel élément que l'on souhaite insérer et Curseur, l'adresse de l'élément après lequel on souhaite insérer p^. Les instructions suivantes permettent d'obtenir ce que l'on souhaite:
p^.Suivant := Curseur^.Suivant; Curseur^.Suivant := p;
La figure suivante illustre l'insertion d'une structure représentant Strasbourg, après la structure représentant Kingersheim.
Pour supprimer le premier élément d'une liste simplement chainée, il suffit de remplacer l'adresse de la liste par l'adresse de l'élément qui suit le premier.
Avec notre exemple, cela se traduit par l'instruction suivante:
L := L^.Suivant ;
Remarque: si la liste ne contient qu'un seul élément, ce dernier n'a pas d'élément suivant, mais l'instruction précédente convient également car dans ce cas L^.Suivant contient NIL et la liste devient par conséquent vide.
La figure suivante illustre la suppression du premier élément dans une liste de ville.
Avant la suppression L pointe sur Ribeauvillé et la liste contient quatre villes.
Après la suppression L pointe sur la ville qui suivait Ribeauvillé, c'est à dire Kingersheim. De ce fait, elle ne contient plus que les trois villes Kingersheim, Strasbourg et Nancy.
Supposons à présent que l'on souhaite supprimer l'élément qui suit un certain élément de la liste d'adresse donnée.
Appelons Curseur, l'adresse de cet élément. L'instruction suivante permet de supprimer l'élément qui suit Curseur^:
Curseur^.Suivant := Curseur^.Suivant^.Suivant;
La figure suivante illustre ce mécanisme. On supprime ici la ville Strasbourg, en faisant pointer la ville précédente (Kingersheim) sur la ville qui suit Strasbourg(Nancy). De ce fait, Strasbourg n'existe plus dans la liste.