Cours d'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 

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