Chapitre 8 Les listes chaînées

Chapitre 8

Les listes chaînées

1. Introduction
Avant de commencer, nous définissons d’abord le terme structures de données linéaires :
Les structures de données linéaires induisent une notion de séquence entre les éléments lescomposant
(1er, 2ème, 3ème, suivant, dernier…). Parmi les structures de données linéaires il y a :
 Les tableaux,
 Les listes chaînées,
 Les piles,
 Les files.
Vous connaissez déjà la structure linéaire de type tableau pour lequel les éléments de même type le
composant sont placés de façon contigüe en mémoire. Pour créer un tableau, à 1 ou 2 dimensions, il faut
connaître sa taille qui ne pourra être modifiée au cours du programme, et lui associer un indice pour
parcourir ses éléments.
Pour les tableaux la séquence correspond aux numéros des cases du tableau. On accède à un élément du
tableau directement grâce à son indice.
1.1. Problèmes de la structure tableau :
Plus le problème de l’allocation contigüe en mémoire des éléments d’un tableau et le problème de la taille
fixe que doit être réserver à l’avance, la structure de type tableau pose d’autres problèmes concernant
l’insertion ou la suppressiond’un élément car ces actions nécessitent des décalages du contenu des cases
du tableau qui prennent du temps dans l'exécution d'un programme.
Pour bien assimiler le problème :
1) Ecrire un algorithme qui permet d’insérer le mot ‘ BATNA ‘ dans la nième case d’un tableau à une
dimension de chaîne de caractères.
2) Ecrire un algorithme qui permet de supprimer la nième case d’un tableau de N entiers.
Ce type de stockage de valeurs peut donc être coûteux en temps d'exécution. Il existe une autre structure,
appelée liste chaînée, pour stocker des valeurs, cette structure :
 Est une variable à taille dynamique (+/-)
 Permet plus aisément d'insérer et de supprimer des valeurs dans une liste linéaire d'éléments.
 Permet l’allocation non contigüe des éléments de la liste.
1.2. Les listes chaînées
Une liste chaînée est une structure linéaire :
1 Qui n'a pas de dimension fixée à sa création.
2 Ses éléments de même type sont éparpillés dans la mémoire et reliés entre eux par des pointeurs.
3 Sa dimension peut être modifiée selon la place disponible en mémoire.
4 La liste est accessible uniquement par sa tête de liste c’est-à-dire son premier élément.
Chapitre 8 Les listes chaînées
La définition d’une liste linéaire chainée est très semblable aux définitions des structures de données de
type enregistrement. La définition d’une LLC peut être décomposée en deux (02) parties:
 Partie champs d’un élément de LLC (Info): qui détermine le type des éléments de LLC (Ex: liste
d’entiers, d’étudiants …).
 Partie pointeur d’élément (Suivant): contenant un champ adresse (pointeur) de l’élément suivant
dans la liste. La séquence est mise alors en œuvre par ce pointeur. Le dernier élément de la liste ne
pointe sur rien (Nil). On accède à un élément de la liste en parcourant les éléments grâce à leurs
pointeurs.
Infos

Remarque : Chaque élément dans la liste est un enregistrement.

Soit la liste chaînée suivante (@ indique que le nombre qui le suit représente une adresse) :
@:3
Tête
@ :3 Voici 15 @ :15 Une 8 @ :8 Liste 30 @ :30 Chaînée Nil

Adresse Donnée Pointeur

 Pour accéder au troisième élément de la liste il faut toujours débuter la lecture de la liste par son
premier élément dans le pointeur duquel est indiqué la position du deuxième élément. Dans le
pointeur du deuxième élément de la liste on trouve la position du troisième élément…
 Pour ajouter, supprimer ou déplacer un élément il suffit d'allouer une place en mémoire et de
mettre à jour les pointeurs des éléments.
Il existe différents types de listes chaînées :
 Liste chaînée simple constituée d'éléments reliés entre eux par des pointeurs.
 Liste chaînée ordonnée où l'élément suivant est plus grand que le précédent. L'insertion et la
suppression d'élément se font de façon à ce que la liste reste triée.
 Liste doublement chaînée où chaque élément dispose non plus d'un pointeur mais de deux
pointeurs pointant respectivement sur l'élément précédent et l'élément suivant. Ceci permet de
lire la liste dans les deux sens, du premier vers le dernier élément ou inversement.
 Liste circulaire où le dernier élément pointe sur le premier élément de la liste. S'il s'agit d'une liste
doublement chaînée alors de premier élément pointe également sur le dernier.
Ces différents types peuvent être mixés selon les besoins.
On utilise une liste chaînée plutôt qu'un tableau lorsque l'on doit traiter des objets représentés par des
suites sur lesquelles on doit effectuer de nombreuses suppressions et de nombreux ajouts. Les
manipulations sont alors plus rapides qu'avec des tableaux.
Résumé
Structure Dimension Position d'une information Accès à une information
Tableau Fixe Par son indice Directement par l'indice
Liste chaînée Evolue selon les Par son adresse Séquentiellement par le
actions pointeur de chaque élément
1.3. Les piles et les files
Les files et les piles sont des listes chaînées particulières qui permettent l'ajout et la suppression
d'éléments uniquement à une des deux extrémités de la liste.
Structure Ajout Suppression Type de Liste
Chapitre 8 Les listes chaînées
PILE Tête Tête LIFO (Last In First Out)
FILE Queue Tête FIFO (First In First Out)
 La pile est une structure de liste similaire à une pile d'assiettes où l'on pose et l'on prend au
sommet de la pile.
 La file est une structure de liste similaire à une file d'attente à une caisse, le premier client entré
dans la file est le premier sorti de celle-ci (aucun resquillage n'est admis).
2. Listes chaînées
2.1. Définitions
Uneliste linéaire chainée est constituée d’un ensemble de cellules (éléménts) chaînées entre elles.
Un élément d'une liste est l'ensemble (ou structure) formé :
 D’une donnée ou information,
 D'un pointeur nommé Suivant indiquant la position de l'élément le suivant dans la liste.
A chaque élément est associée une adresse mémoire.
Adresse Donnée Suivant
L’adresse de la première de ces cellules détermine la liste, Cette adresse doit être stockée dans une
variable appelée souvent : liste, tête…
Les listes chaînées font appel à la notion de variable dynamique.
Une variable dynamique:
 Estdéclarée au début de l'exécution d'un programme,
 Elley est créée, c'est-à-dire qu'on lui alloue un espace à occuper à une adresse de la mémoire,
 Ellepeut y être détruite, c'est-à-dire que l'espace mémoire qu'elle occupait est libéré,
 L'accèsà la valeur se fait à l'aide d'un pointeur.
Un pointeur est une variable dont la valeur est une adresse mémoire. Un pointeur, noté P, pointe sur une
variable dynamique notée P*.
Le type de base est le type de la variable pointée.
Le type du pointeur est l'ensemble des adresses des variables pointées du type de base. Il estreprésenté
par le symbole * suivi de l'identificateur du type de base.
Exemple:
Info Suivant

3 Essai Nil
P
P* ( P* est l'objet dont l'adresse est rangée dans P )
La variable pointeur P pointe sur l'espace mémoire P* d'adresse 3, cette cellule mémoire contient la valeur
"Essai" dans le champ Info et la valeur spéciale Nil dans le champ Suivant. Le champ Suivant servira à
indiquer quel est l’élément suivant lorsque la cellule fera partie d’une liste, la valeur Nil indique qu’il n’y a
pas d'élément suivant.

Les listes chaînées entraînent l'utilisation de procédures d'allocation et de libération dynamiques de la

mémoire. Ces procédures sont les suivantes :
 Allouer(P) : réserve un espace mémoire P* et donne pour valeur à P l'adresse de cet espace
mémoire. On alloue un espace mémoire pour un élément sur lequel pointe P.
Chapitre 8 Les listes chaînées
 Désallouer(P) : libère l'espace mémoire qui était occupé par l'élément à supprimer P* sur lequel
pointe P.
Pour définir les variables utilisées dans l'exemple ci-dessus, il faut :
1. Définir le type des éléments de liste : Type Cellule= Structure
Info : Chaîne
Suivant : Liste
Fin Structure
2. Définir le type du pointeur : Type Liste = *Cellule
3. Déclarer une variable pointeur : Var P : Liste
4. Allouer une cellule mémoire qui réserve un espace en mémoire et donne à P la valeur de l'adresse de
l'espace mémoire P* : Allouer(P)
5. Affecter des valeur à l'espace mémoire P*:P*.Info "Essai" ; P*.Suivant Nil
Quand P = Nil alors P ne pointe sur rien.
2.2. Listes chaînées simples
Une liste chaînée simple est composée :
 D'un ensemble d'éléments tel que chacun :
 Est rangé en mémoire à une certaine adresse,
 Contient une donnée (Info),
 Contient un pointeur, souvent nommé Suivant, qui contient l'adresse de l'élémentsuivant
 dans la liste,
 D'une variable, appelée Tête, contenant l'adresse du premier élément de la liste chaînée.
Le pointeur du dernier élément contient la valeur Nil. Dans le cas d'une liste vide le pointeur de la tête
contient la valeur Nil. Une liste est définie par l'adresse de son premier élément.
Exemple :
Prenons le tableau suivant :
14 10 34 24
La liste chaînée correspondante pourrait être :
Soit la liste chaînée suivante (@ indique que le nombre qui le suit représente une adresse) :
@ : 15

Tête
@ :15 14 23 @ :23 10 3 @ :3 34 30 @ :30 24 Nil

Si P a pour valeur 3 Si P a pour valeur 23

P*.Info a pour valeur 34 P*.Info a pour valeur 10
P*.Suivant a pour valeur 30 P*.Suivant a pour valeur 3
2.3. Traitements de base d'utilisation d'une liste chaînée simple
Il faut commencer par définir un type de variable pour chaque élément de la chaîne. En langage
algorithmique ceci se fait comme suit :
Type Element = Structure
Info : variant
Suivant : Liste
Chapitre 8 Les listes chaînées
Fin structure
Type Liste = *Element
Variables Tete, P : Liste
Le type de Info dépend des valeurs contenues dans la liste : entier, chaîne de caractères, variant pour un
type quelconque…
Les traitements des listes sont les suivants :
 Créer une liste.
 Ajouter un élément.
 Supprimer un élément.
 Modifier un élément.
 Parcourir une liste.
 Rechercher une valeur dans une liste.
2.3.1. Créer une liste chaînée composée de 2 éléments de type entier
Déclarations des types pour la liste :
Type Element = Structure
Info : entier
Suivant : Liste
Fin structure
Type Liste = *Element
Algorithme CréationListe2Elements
Tete, P : Liste
NombreElt : entier
Début
Tete Nil /* pour l'instant la liste est vide*/
Allouer(P) /* réserve un espace mémoire pour le premier élément */
Lire(P*.Info) /* stocke dans l'Info de l'élément pointé par P la valeur saisie */
P*.Suivant Nil /* il n'y a pas d'élément suivant */
Tete P /* le pointeur Tete pointe maintenant sur P */
/* Il faut maintenant ajouter le 2e élément, ce qui revient à insérer un élément en tête de liste */
Allouer(P) /* réserve un espace mémoire pour le second élément */
Lire(P*.Info) /* stocke dans l'Info de l'élément pointé par P la valeur saisie */
P*.SuivantTete /* élément inséré en tête de liste */
Tete P
Fin
Tete Nil Tète
Nil
Allouer(P) Tète
Nil P

@ : 15

Lire(P*.Info) Tète
Nil P

@ : 15 10

P*.Suivant Nil Tète

Nil P
Chapitre 8 Les listes chaînées

@ : 15 10 Nil

Tete P Tète
15 P

@ : 15 10 Nil

Allouer(P) Tète
15 P

@ : 15 10 Nil @ :7
Lire(P*.Info) Tète
15 P

@ : 15 10 Nil @ :7 23
P*.SuivantTete Tète
15 P

@ : 15 10 Nil @ :7 23 15

Tete P Tète
7 P

@ :7 23 15 @ :15 10 Nil

2.3.2. Créer une liste chaînée composée de plusieurs éléments de type chaîne de caractères
Pour créer une liste chaînée contenant un nombre d'éléments à préciser par l'utilisateur il suffit
d'introduire une variables de type Entier NombreElt.
Déclarations des types pour la liste :
Type Element = Structure
Info : chaîne de carctères
Suivant : Liste
Fin structure
Type Liste = *Element
Algorithme CréationListeNombreConnu
Tete, P : Liste
NombreElt : entier
Compteur : entier
DEBUT
Lire(NombreElt)
Tete _ Nil
POUR Compteur DE 1 A NombreElt FAIRE
Allouer(P) /* réserve un espace mémoire pour l’élément à ajouter */
Lire(P*.Info) /* stocke dans l'Info de l'élément pointé par P la valeur saisie */
P*.SuivantTete /* élément inséré en tête de liste */
Tete P /* le pointeur Tete pointe maintenant sur P */
FIN POUR
FIN
2.3.3. Afficher les éléments d'une liste chaînée
Chapitre 8 Les listes chaînées
Une liste chaînée simple ne peut être parcourue que du premier vers le dernier élément de la liste.
L'algorithme est donné sous forme d'une procédure qui reçoit la tête de liste en paramètre.
ProcedureAfficherListe (Entrée Tete : Liste)
/* Afficher les éléments d’une liste chaînée passée en paramètre*/
Variable locale
P : liste
DEBUT
P Tete /* P pointe sur le premier élément de la liste*/
/* On parcourt la liste tant que l'adresse de l'élément suivant n'est pas Nil */
TANT QUE P <> NIL FAIRE /* si la liste est vide Tete est à Nil */
Ecrire(P*.Info) /* afficher la valeur contenue à l'adresse pointée par P */
P P*.Suivant /* On passe à l'élément suivant */
FIN TANT QUE
FIN
2.3.4. Rechercher une valeur donnée dans une liste chaînée ordonnée
Pour chercher un élément dans une liste, la liste va être parcourue à partir de son premier élément (celui
pointé par le pointeur de tête). Il a deux cas d’arrêt :
 Avoir trouvé la valeur de l'élément,
 Avoir atteint la fin de la liste.
L'algorithme est donné sous forme d'une procédure qui reçoit la tête de liste en paramètre. La valeur à
chercher est lue dans la procédure.
ProcedureRechercherValeurListe (Entrée Tete : Liste, Val : variant)
/* Rechercher si une valeur donnée en paramètre est présente dans la liste passée en paramètre */
Variables locales
P : Liste /* pointeur de parcours de la liste */
Trouve : booléen /* indicateur de succès de la recherche */
DEBUT
SITete<> Nil ALORS /* la liste n'est pas vide on peut donc y chercher une valeur */
P _ Tete
Trouve  Faux
TANTQUE P <> Nil ET Non Trouve
SIP*.Info = Val ALORS /* L'élément recherché est l'élément courant */
Trouve  Vrai
SINON /* L'élément courant n'est pas l'élément recherché */
P P*.Suivant /* on passe à l'élément suivant dans la liste */
FINSI
FIN TANT QUE
SI Trouve ALORS
Ecrire (" La valeur ", Val, " est dans la liste")
SINON
Ecrire (" La valeur ", Val, " n'est pas dans la liste")
FINSI
SINON
Ecrire("La liste est vide")
FINSI
FIN
2.3.5. Supprimer le premier élément d'une liste chaînée
Il y a deux actions, dans cet ordre, à réaliser :
Chapitre 8 Les listes chaînées
 Faire pointer la tête de liste sur le deuxième élément de la liste,
 Llibérer l'espace mémoire occupé par l'élément supprimé.
Il est nécessaire de déclarer un pointeur local qui va pointer sur l'élément à supprimer, et permettre de
libérer l'espace qu'il occupait.
ProcedureSupprimerPremierElement (Entrée/Sortie Tete : Liste)
/* Supprime le premier élément de la liste dont le pointeur de tête est passé en paramètre */
Variables locales
P : Liste /* pointeur sur l'élément à supprimer */
DEBUT
SITete<> Nil ALORS /* la liste n'est pas vide on peut donc supprimer le premier élément */
P Tete /* P pointe sur le 1er élément de la liste */
TeteP*.Suivant /* la tête de liste doit pointer sur le deuxième 'élément */
Desallouer(P) /* libération de l'espace mémoire qu'occupait le premier élément */
SINON
Ecrire("La liste est vide")
FINSI
FIN
P
@ : 15 23
Tête
@ :15 14 23 @ :23 10 3 @ :3 34 30 @ :30 24 Nil

2.3.6. Supprimer d'une liste chaînée un élément portant une valeur donnée
Il faut :
 Si l’élément à supprimer est le premier, alors traiter à part la suppression car il faut
modifier le pointeur de tête,
 Trouver l'adresse P de l'élément à supprimer,
 Sauvegarder l'adresse Prec de l'élément précédant l'élément pointé par P pour connaître l'adresse
de l'élément précédant l'élément à supprimer, puis faire pointer l'élément précédent sur l'élément
suivant l'élément à supprimer,
 Libérer l'espace mémoire occupé par l'élément supprimé.
L'exemple suivant considère que l'on souhaite supprimer l'élément contenant la valeur "34" de la
listeci-dessus.
@ : 15 Pred : P
23
Tête
@ :15 14 23 @ :23 10 3 30 @ :3 34 30 @ :30 24 Nil

ProcedureSupprimerElement (Entrée/Sortie Tete : Liste, Val : variant)

/* Supprime l'élément dont la valeur est passée en paramètre */
Variables locales
P : Liste /* pointeur sur l'élément à supprimer */
Prec : Liste /* pointeur sur l'élément précédant l'élément à supprimer */
Trouvé : Liste /* indique si l'élément à supprimer a été trouvé */
DEBUT
SITete<> Nil ALORS /* la liste n'est pas vide on peut donc y chercher une valeur à supprimer */
SI Tete*.info = Val ALORS /* l'élément à supprimer est le premier */
P Tete
Chapitre 8 Les listes chaînées
TeteTete*Suivant
Desallouer(P)
SINON /* l'élément à supprimer n'est pas le premier */
Trouve  Faux
PrecTete /* pointeur précédent */
P Tete*.Suivant /* pointeur courant */
TANTQUE P <> Nil ET Non Trouve
SIP*.Info = Val ALORS /* L'élément recherché est l'élément courant */
Trouve  Vrai
SINON /* L'élément courant n'est pas l'élément cherché */
Prec P /* on garde la position du précédent */
P* P*.Suivant /* on passe à l'élément suivant dans la liste */
FINSI
FIN TANT QUE
SI Trouve ALORS
Prec*.Suivant P*.Suivant /* on "saute" l'élément à supprimer "/
Desallouer(P)
SINON
Ecrire ("La valeur ", Val, " n'est pas dans la liste")
FINSI
FINSI
SINON
Ecrire("La liste est vide")
FINSI
FIN
2.4. Listes doublement chaînées
Il existe aussi des listes chaînées, dites bidirectionnelles, qui peuvent être parcourues dans les deux sens,
du 1er élément au dernier et inversement.
Une liste chaînée bidirectionnelle est composée :
 D'un ensemble de données,
 De l'ensemble des adresses des éléments de la liste,
 D'un ensemble de pointeurs Suivant associés chacun à un élément et qui contient l'adresse de
l'élément suivant dans la liste,
 D'un ensemble de pointeurs Precedentassociés chacun à un élément et qui contient l'adresse de
l'élément précédent dans la liste,
 Du pointeur sur le premier élément Tete, et du pointeur sur le dernier élément, Queue.

Type Element = Structure

Precedent : ListeDC
Info : variant
Suivant : ListeDC
Fin Structure
Type ListeDC = *Element
Le pointeur Precedent du premier élément ainsi que le pointeur Suivant du dernier élément contiennent la
valeur Nil.

Tete : 4 Queue :15

@:4 @:3 @ :25 @ :7 @ :15

Nil 4 3 25 7
Chapitre 8 Les listes chaînées
20 45 10 213 7
3 25 7 15 Nil

A l'initialisation d'une liste doublement chaînée les pointeurs Tete et Queue contiennent la valeur Nil.

2.4.1. Afficher les éléments d'une liste doublement chaînée

Il est possible de parcourir la liste doublement chaînée du premier élément vers le dernier. Le pointeur de
parcours, P, est initialisé avec l'adresse contenue dans Tete. Il prend les valeurs successives des pointeurs
Suivant de chaque élément de la liste. Le parcours s'arrête lorsque le pointeur de parcours a la valeur Nil.
Cet algorithme est analogue à celui du parcours d'une liste simplement chaînée.
ProcedureAfficherListeAvant (Entrée Tete : ListeDC)
Variables locales
P : ListeDC
DEBUT
P Tete /
TANT QUE P <> NIL FAIRE
Ecrire(P*.Info)
P P*.Suivant
FIN TANT QUE
FIN
Il est possible de parcourir la liste doublement chaînée du dernier élément vers le premier. Le pointeur de
parcours, P, est initialisé avec l'adresse contenue dans Queue. Il prend les valeurs successives des pointeurs
Precedent de chaque élément de la liste. Le parcours s'arrête lorsque\ le pointeur de parcours a la valeur
Nil.

ProcedureAfficherListeArriere (Entrée Queue : ListeDC)

Variables locales
P : ListeDC
DEBUT
P _ Queue
TANT QUE P <> NIL FAIRE
Ecrire(P*.Info)
P _ P*.Precedent
FIN TANT QUE
FIN
2.5. Listes chaînées circulaires
Une liste chaînée peut être circulaire, c'est à dire que le pointeur du dernier élément contientl'adresse du
premier.
Exemple d'une liste simplement chaînée circulaire :

@ : 15
Tête
@ :15 14 23 @ :23 10 3 @ :3 34 30 @ :30 24 15

Le pointeur du dernier élément contient l'adresse du premier.

Chapitre 8 Les listes chaînées
Exemple d'une liste doublement chaînée circulaire :

Tête : 4 Queue :15

@:4 @:3 @ :25 @ :7 @ :15

15 4 3 25 7
20 45 10 213 7
3 25 7 15 4

Le dernier élément pointe sur le premier, et le premier élément pointe sur le dernier.
12