2. LISTES CHAINEES

Une liste est une structure qui permet de stocker de manière ordonnée des éléments. Une liste est composée de maillons, un maillon étant une structure qui contient un élément à stocker et un pointeur (au sens large) sur le prochain maillon de la liste.

structure MAILLON:
 ELEMENT  elt;
 POINTEUR suiv;
fin structure;

On parle de pointeur au sens large car il y a principalement deux manières de représenter une liste chaînée, ce qui entraîne deux types de pointeur qui sont précisés par la suite.

Une première façon de modéliser une liste chaînée consiste à allouer à l'avance un certain nombre de maillons. Autrement dit, un tableau de maillons, de taille fixée, est alloué à la création de la liste. Par la suite, la liste est formée en utilisant comme maillons des cases de ce tableau. Avec cette modélisation, un pointeur sur un prochain maillon dans la liste sera tout simplement un indice dans le tableau.

type POINTEUR: ENTIER;

Par convention, un pointeur sur rien aura la valeur VIDE = -1. La figure suivante représente une liste chaînée par cette modélisation. La liste contient les chaînes de caractères suivantes classées dans cet ordre: "Paris", "Marseille", "Bordeaux", "Lyon", "Toulouse".

Voici la structure de données correspondant à une liste chaînée représentée par tableau.

structure LISTE_TAB:
 MAILLON  tab[NMAX];
 ENTIER   n;
 POINTEUR tete;
 POINTEUR fin;
fin structure;

NMAX est une constante représentant la taille du tableau alloué. n est le nombre d'éléments dans la liste. tete et fin pointent respectivement sur la tête (premier élément) et la queue (dernier élément) de la liste.

Une seconde façon de modéliser une liste chaînée consiste à allouer dynamiquement les maillons chaque fois que cela est nécessaire. Dans ce cas, un pointeur sur un maillon sera bien ce que l'on appelle couramment un pointeur, c'est-à-dire un pointeur sur la mémoire centrale de l'ordinateur.

type POINTEUR: MAILLON *;

Un pointeur sur rien aura donc la valeur VIDE = NIL. La figure suivante représente une liste chaînée par cette modélisation. Elle reprend la même liste que pour l'exemple de modélisation par tableau.

Voici la structure de données correspondant à une liste chaînée représentée par pointeurs.

structure LISTE_PTR:
 POINTEUR tete;
 POINTEUR fin;
fin structure;

Comme pour la représentation par tableau, tete et fin pointent respectivement sur la tête et la queue de la liste.

A partir de maintenant, nous allons employer le type LISTE qui représente une liste chaînée au sens général, c'est-à-dire sans se soucier de sa modélisation. LISTE représente aussi bien une liste par tableau (LISTE_TAB) qu'une liste par pointeurs (LISTE_PTR). La présentation des opérations appliquées sur une liste chaînée est divisée en deux parties. Tout d'abord, on présente quelques opérations de base dont l'implémentation (le contenu) est propre à chacune des modélisations.

• initialiserListe(LISTE * l)
  Initialise la liste pointée par l, i.e. fait en sorte que la liste soit vide.

• MAILLON  CONTENU(LISTE l, POINTEUR p)
  Retourne le maillon référencé par le pointeur (au sens large) p dans la liste l. Attention, ceci n'est pas une fonction, CONTENU va seulement remplacer une série d'instructions. Il n'y a donc pas de mécanisme d'appel de fonction mis en jeu. C'est important, car le maillon retourné par CONTENU peut alors être modifié par affectation. On peut comparer cela à une macrocommande en C (e.g. #define).

• POINTEUR  allouerMaillon(LISTE * l)
  Alloue un nouveau maillon pour la liste pointée par l et retourne son adresse. En cas d'échec de cette allocation, la valeur VIDE est retournée.

• libererMaillon(LISTE * l, POINTEUR p)
  Libère l'espace occupé par le maillon pointé par p appartenant à la liste pointée par l.

Néanmoins, quelle que soit la modélisation choisie pour la liste chaînée, ces opérations ont les mêmes prototypes (mêmes paramètres et type de retour), ce qui permet par la suite d'écrire des opérations générales indépendantes de la modélisation choisie.

• BOOLEEN  listeVide(LISTE l)
  Indique si la liste chaînée l est vide.

• POINTEUR  preparerMaillon(LISTE * l, ELEMENT e)
  Alloue un maillon pour la liste pointée par l et y place l'élément e. Si aucun maillon n'a pu être alloué, la valeur VIDE est retournée.

• BOOLEEN  rechercherMaillon(LISTE l, POINTEUR * p)
  Recherche un maillon dans la liste l selon un critère donné. L'adresse du maillon qui précède le maillon trouvé est alors stockée à l'adresse p. Si le maillon trouvé est le premier de la liste, VIDE est stockée à l'adresse p. La fonction retourne VRAI uniquement si un maillon a été trouvé correspondant au critère de recherche.

• insererMaillon(LISTE * l, POINTEUR p1, POINTEUR p2)
  Insère le maillon pointé par p2 dans la liste pointée par l, juste après le maillon pointé par p1. Si p1 = VIDE, alors l'insertion s'effectue en tête de la liste.

• supprimerMaillon(LISTE * l, POINTEUR p)
  Supprime de la liste pointée par l le maillon suivant celui pointé par p. Si p = VIDE, alors la suppression s'effectue en tête de la liste.

• BOOLEEN  ajouterTete(LISTE * l, ELEMENT e)
  Ajoute l'élément e en tête de la liste pointée par l. VRAI est retournée si l'opération a réussi.

• BOOLEEN  ajouterQueue(LISTE * l, ELEMENT e)
  Ajoute l'élément e en queue de la liste pointée par l. VRAI est retournée si l'opération a réussi.

• BOOLEEN  retirerTete(LISTE * l)
  Retire l'élément en tête de la liste pointée par l. VRAI est retournée si l'opération a réussi.

• ELEMENT  teteListe(LISTE l)
  Retourne l'élément en tête de la liste l.

• ELEMENT  queueListe(LISTE l)
  Retourne l'élément en queue de la liste l.

Cette fonction initialise les valeurs de la structure représentant la liste pointée par l pour que celle-ci soit vide. Dans le cas d'une représentation par tableau, une liste est vide lorsque tete et fin pointent sur VIDE. Dans ce cas, il faut également que n soit nul.

fonction initialiserListe(LISTE * l):
 ln  0;
 ltete  VIDE;
 lfin  VIDE;
fin fonction;

Comme nous l'avons précisé précédemment, CONTENU n'est pas une fonction mais un mot-clé qui remplace littéralement un jeu d'instructions. Cette opération retourne donc le contenu d'un pointeur p sur un maillon d'une liste l. Dans le cas d'une représentation par tableau, il s'agit de retourner le maillon d'indice p du tableau représentant la liste l.

macro MAILLON  CONTENU(LISTE l, POINTEUR p):
 rendre (l.tab[p]);
fin macro;

Cette fonction réserve l'espace mémoire nécessaire pour un nouveau maillon dans la liste pointée par l et retourne un pointeur sur ce maillon. Dans le cas d'une représentation par tableau, on prendra comme nouveau maillon un maillon non utilisé dans le tableau ltab. Le plus simple ici est de prendre le maillon pointé par n qui représente le nombre de maillons utilisés par la liste. n est alors augmenté d'une unité. Si n vaut déjà NMAX alors il ne reste plus de maillon disponible dans le tableau. La valeur VIDE est alors retournée.

fonction POINTEUR  allouerMaillon(LISTE * l):
 si (ln < NMAX)
  ln  ln + 1;
  rendre (ln - 1);
 sinon
  rendre VIDE;
 fin si;
fin fonction;

Cette fonction libère l'espace occupé par un maillon à l'adresse p dans une liste pointée par l. Dans le cas d'une représentation par tableau, on supprimera un maillon en décalant d'une case vers la gauche tous les maillons dont l'indice est supérieur à p dans ltab. Bien entendu, n est diminué d'une unité. Ensuite, il faut parcourir tous les maillons pour diminuer d'une unité tous les pointeurs qui sont supérieurs à p. De même si le pointeur sur la tête ou sur la queue est supérieur à p, il faut le diminuer d'une unité.

fonction libererMaillon(LISTE * l, POINTEUR p):
 decalerMaillons(l,p);
 majPointeurs(l,p);

 si (ltete != VIDE et ltete > p) alors
  ltete  ltete - 1;
 fin si;

 si (lfin != VIDE et lfin > p) alors
  lfin  lfin - 1;
 fin si;
fin fonction;

fonction decalerMaillons(LISTE * l, POINTEUR p):
 tant que (p + 1 < ln) faire
  ltab[p]  ltab[p + 1];
  p  p + 1;
 fin tant que;

 ln  ln - 1;
fin fonction;

fonction majPointeurs(LISTE * l, POINTEUR p):
 i  0;

 tant que (i < ln) faire
  si (ltab[i].suiv > p) alors
   ltab[i].suiv  ltab[i].suiv - 1;
  fin si;

  i  i + 1;
 fin tant que;
fin fonction;

Cette fonction initialise les valeurs de la structure représentant la liste pointée par l pour que celle-ci soit vide. Dans le cas d'une représentation par pointeurs, une liste est vide lorsque tete et fin pointent sur VIDE.

fonction initialiserListe(LISTE * l):
 ltete  VIDE;
 lfin  VIDE;
fin fonction;

Comme nous l'avons précisé précédemment, CONTENU n'est pas une fonction mais un mot-clé qui remplace littéralement un jeu d'instructions. Cette opération retourne donc le contenu d'un pointeur p sur un maillon d'une liste l. Dans le cas d'une représentation par pointeurs, il s'agit de retourner le maillon pointé directement par p.

macro MAILLON  CONTENU(LISTE l, POINTEUR p):
 rendre (*p);
fin macro;

Cette fonction réserve l'espace mémoire nécessaire pour un nouveau maillon dans la liste pointée par l et retourne un pointeur sur ce maillon. Dans le cas d'une représentation par pointeurs, l'espace nécessaire est alloué en mémoire centrale.

fonction POINTEUR  allouerMaillon(LISTE * l):
 rendre (ALLOUER(MAILLON,1));
fin fonction;

Cette fonction libère l'espace occupé par un maillon à l'adresse p dans une liste pointée par l. Dans le cas d'une représentation par pointeurs, il suffit de libérer l'espace alloué dans la mémoire centrale.

fonction libererMaillon(LISTE * l, POINTEUR p):
 LIBERER(p);
fin fonction;

Cette fonction indique si la liste l est vide. Une liste est vide si la tête pointe sur VIDE.

fonction BOOLEEN  listeVide(LISTE l):
 rendre (l.tete = VIDE);
fin fonction;

Cette fonction alloue un nouveau maillon pour la liste pointée par l et place un élément e à l'intérieur. Si un maillon a pu être alloué, son adresse est retournée. Sinon, la valeur VIDE est renvoyée.

fonction POINTEUR  preparerMaillon(LISTE * l, ELEMENT e):
 p  allouerMaillon(l);

 si (p != VIDE) alors
  CONTENU(*l,p).elt  e;
 fin si;

 rendre p;
fin fonction;

Cette fonction recherche un maillon dans la liste l. Le critère de recherche est défini par le mot-clé TROUVE(e) qui retourne VRAI si l'élément e correspond au critère de recherche. Une fois l'élément trouvé, l'adresse du maillon qui le précède est stockée à l'adresse p. Dans le cas où le maillon trouvé est le premier de la liste, alors VIDE est stockée à l'adresse p. La fonction renvoie VRAI si elle a trouvé un élément correspondant au critère de recherche.

fonction BOOLEEN  rechercherMaillon(LISTE l, POINTEUR * p):
 *p  VIDE;
 p2  l.tete;

 tant que (p2 != VIDE et non TROUVE(CONTENU(l,p2).elt)) faire
  *p  p2;
  p2  CONTENU(l,p2).suiv;
 fin tant que;

 rendre (p2 != VIDE);
fin fonction;

Cette fonction insère, dans la liste pointée par l, le maillon pointé par p2 juste après le maillon pointé par p1. Si p1 = VIDE, alors l'insertion se fait en tête de la liste. Les liens de chaînage sont modifiés pour intégrer le nouveau maillon. On prend garde de mettre à jour également le pointeur sur la queue de la liste.

fonction insererMaillon(LISTE * l, POINTEUR p1, POINTEUR p2):
 si (p1 = VIDE) alors
  /* Insertion en tête */
  CONTENU(*l,p2).suiv  ltete;
  ltete  p2;
 sinon
  /* Insertion au milieu */
  CONTENU(*l,p2).suiv  CONTENU(*l,p1).suiv;
  CONTENU(*l,p1).suiv  p2;
 fin si;

 si (CONTENU(*l,p2).suiv = VIDE) alors lfin  p2;
fin fonction;

Cette fonction supprime, dans la liste pointée par l, le maillon suivant celui pointé par p. Si p = VIDE, alors c'est l'élément de tête qui est supprimé. Les liens de chaînage sont modifiés et l'espace mémoire occupé par le maillon est libéré. On prend garde de mettre à jour le pointeur sur la queue de la liste.

fonction supprimerMaillon(LISTE * l, POINTEUR p):
 si (p = VIDE) alors
  /* Suppression en tête */
  m  ltete;
  ltete  CONTENU(*l,m).suiv;
  libererMaillon(l,m);
  si (ltete = VIDE) alors lfin  VIDE;
 sinon
  /* Suppression au milieu */
  m  CONTENU(*l,p).suiv;
  CONTENU(*l,p).suiv  CONTENU(*l,m).suiv;
  libererMaillon(l,m);
  si (CONTENU(*l,p).suiv = VIDE) alors lfin  p;
 fin si;
fin fonction;

Cette fonction insère l'élément e en tête de la liste pointée par l. Si l'opération réussit (i.e. il reste de la mémoire pour créer un maillon) alors la valeur VRAI est renvoyée.

fonction BOOLEEN  ajouterTete(LISTE * l, ELEMENT e):
 p  preparerMaillon(l,e);

 si (p != VIDE) alors
  insererMaillon(l,VIDE,p);
  rendre VRAI;
 fin si;

 rendre FAUX;
fin fonction;

Cette fonction insère l'élément e en queue de la liste pointée par l. Si l'opération réussit (i.e. il reste de la mémoire pour créer un maillon) alors la valeur VRAI est renvoyée.

fonction BOOLEEN  ajouterQueue(LISTE * l, ELEMENT e):
 p  preparerMaillon(l,e);

 si (p != VIDE) alors
  insererMaillon(l,lfin,p);
  rendre VRAI;
 fin si;

 rendre FAUX;
fin fonction;

Cette fonction supprime le maillon en tête de la liste pointée par l. Si la liste n'est pas déjà vide, la valeur VRAI est renvoyée.

fonction BOOLEEN  retirerTete(LISTE * l):
 si (non listeVide(*l)) alors
  supprimerMaillon(l,VIDE);
  si (ltete = VIDE) alors lfin  VIDE;
  rendre VRAI;
 sinon
  rendre FAUX;
 fin si;
fin fonction;

Cette fonction retourne le maillon en tête de la liste l. A n'utiliser que si la liste l n'est pas vide.

fonction ELEMENT  teteListe(LISTE l):
 si (non listeVide(l)) alors
  rendre (CONTENU(l,l.tete).elt);
 sinon
  /* Erreur */
 fin si;
fin fonction;

Cette fonction retourne le maillon en queue de la liste l. A n'utiliser que si la liste l n'est pas vide.

fonction ELEMENT  queueListe(LISTE l):
 si (non listeVide(l)) alors
  rendre (CONTENU(l,l.fin).elt);
 sinon
  /* Erreur */
 fin si;
fin fonction;

La représentation par tableau d'une liste chaînée n'a finalement que peu d'intérêt par rapport à un tableau, si ce n'est au niveau de l'insertion. En effet, pour insérer un élément à n'importe quelle position dans une liste chaînée par tableau, il suffit d'ajouter un élément à la fin du tableau et de faire les liens de chaînage. Alors que dans un tableau, l'insertion d'un élément implique le décalage vers la droite d'un certain nombre d'éléments. Cependant au niveau de la suppression, la liste chaînée par tableau a le même défaut qu'un tableau: il faut décaler un certain nombres d'éléments vers la gauche.

Dans le cas d'une liste chaînée par pointeurs, le défaut constaté au niveau de la suppression d'un élément disparaît. En résumé, une liste chaînée par pointeurs permet une insertion et une suppression rapide des éléments. Cependant, contrairement au tableau, une liste chaînée interdit un accès direct aux éléments (mis à part la tête et la queue).