Cours algorithmique : LISTES CHAINEES

MODELISATION DE LA STRUCTURE 

Introduction

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. 

Modélisation par tableau

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. 

Modélisation par pointeurs

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.  

OPERATIONS SUR LA STRUCTURE 

Introduction

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 pointé 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.  

Opérations pour la modélisation par tableau

Initialiser une liste 

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 tête et fin pointent sur VIDE. Dans ce cas, il faut également que n soit nul. 

fonction initialiserListe(LISTE * l):
 l --> n <-- 0;
 l --> tete <-- VIDE;
 l --> fin <-- VIDE;
fin fonction; 

Contenu d'un pointeur

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;

Allouer un maillon 

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 l tab. 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 (l --> n < NMAX)
  l --> n  <-- l --> n + 1;
  rendre (l --> n - 1);
 sinon
  rendre VIDE;
 fin si;
fin fonction;

Libérer un maillon 

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 l tab. 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 (l --> tete != VIDE et l --> tete > p) alors
  l --> tete <-- l --> tete - 1;
 fin si;

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

fonction decalerMaillons(LISTE * l, POINTEUR p):
 tant que (p + 1 < l --> n) faire
  l --> tab[p] <--  l --> tab[p + 1];
  p <-- p + 1;
 fin tant que;

 l --> n <-- l--> n - 1;
fin fonction;

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

 tant que (i < l --> n) faire
  si (l --> tab[i].suiv > p) alors
   l --> tab[i].suiv <-- l --> tab[i].suiv - 1;
  fin si;

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

Opérations pour la modélisation par pointeurs

Initialiser une liste

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 tête et fin pointent sur VIDE. 

fonction initialiserListe(LISTE * l):
 l --> tete <-- VIDE;
 l --> fin  <-- VIDE;
fin fonction;

Contenu d'un pointeur 

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;

Allouer un maillon

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;

Libérer un maillon

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;

Opérations générales

Liste vide ?

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;

Préparer un maillon 

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; 

Rechercher un maillon

  
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;

Insérer un maillon

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 <-- l --> tete;
  l --> tete <-- 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 l --> fin <-- p2;
fin fonction;

Supprimer un maillon

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 <-- l --> tete;
  l --> tete <-- CONTENU(*l,m).suiv;
  libererMaillon(l,m); 

  si (l --> tete = VIDE) alors l --> fin  <-- 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 l --> fin <-- p;
 fin si;
fin fonction;

Ajouter en tête de liste

Cette fonction  insère  l'élément e en  tête de  la  liste pointée par  l. Si l'opération réussi (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;

Ajouter en queue de liste 

Cette fonction insère l'élément e en queue de la liste pointée par l. Si l'opération réussi (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,l fin,p);
  rendre VRAI;
 fin si;

 rendre FAUX;
fin fonction;

Retirer la tête de liste

     
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 (l tete = VIDE) alors l --> fin <-- VIDE;
  rendre VRAI;
 sinon
  rendre FAUX;
 fin si;
fin fonction; 

Elément en tête de liste

    
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;

Elément en queue de liste

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;

CONCLUSION 

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 disparait. 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).  

 

------------------------------------------------------------------------------------------------------
 <<< CHAPITRE I : LISTE TABLEAUX

                >>> CHAPITRE III : LES PILES