Cours :

« Algorithmique et complexité »
Enseignante : Fatma Hermès
Niveau : 1ière année CS
Groupes : 1&2
Semèstre : 2
Année universitaire : 2020-2021

1
Chapitre 3 : Les listes
chainées
Listes simplement chainées :
◦ Définition
◦ Description
◦ Manipulation : Fonctions utilisées
Listes doublement chainées
Introduction
 Une liste chaînée est une suite d’un nombre
variable d’objets de même type appelés
éléments de la liste.
Elément Elément … Elément
1 2 n
 Elle est enregistrée sur un support adressable et il
existe une action simple permettant de passer
d’un élément à l’élément suivant s’il existe.
 La liste chaînée est une application typique de
l’allocation dynamique de mémoire.
 Ainsi, il est judicieux d’avoir des connaissances sur
les pointeurs, les structures et l’allocation
dynamique de mémoire pour aborder aux
listes chaînées.
Listes simplement chainées
Définition
Une liste simplement chaînée est
une suite d’un nombre variable
d’objets de même type.
Chaque élément, sauf le dernier,
pointe vers son successeur.
Elément 1 : Elément … Elément n :
Tete 2 Queue NULL
 Listes simplement chainées :
Description
Pour décrire une liste simplement chainée on a
besoin de connaitre :
 Chaque élément d’une liste simplement
chaînée est de type composé par :
◦ Une partie information(s)
◦ Une partie pointeur Exemple :
Elément =
enregistrement
Adresse : num : entier
106 
x suivant : pointeur
sur Elément
 Définir un pointeur de tête Fin enregistrement
qui permet
d’accéder au premier élément de la liste
Tête : pointeur sur Elément
Listes simplement chainées :
Description Pour décrire une liste
simplement chainée il
faut :
 Disposer des primitives d’allocation et de
libération pour créer ou supprimer des éléments.
◦ Création : p  ALLOUER ( Taille(Elément))
// ALLOUER (p)
 Rechercher dans la zone dynamique le
premier emplacement capable de contenir un
objet de type considéré.
 Réserver cet emplacement.
 Donner à la variable pointeur la valeur égale à
l’adresse mémoire de cet emplacement.
◦ Suppression : LIBERER (p)
 Listes simplement chainées :
Description
 Pourdécrire une liste simplement chainée, il faut
aussi un moyen pour repérer le dernier
élément de la liste.
 Cet élément n’ayant pas de successeur, le
champ lien devra avoir la valeur NULL
Adresse : Adresse
indiquant :
l’adresse Adresse
du :
pointage. Adresse :
x100 1 1
201 2 2
51 3 3
74 NULL

L:x
Tete de la TYPE Elément = enregistrement
liste INFO : Type_info
Environnement Suivant : pointeur sur
TYPE d’une Liste Elément
Simplement Fin enregistrement
Chainée (LSC) LISTE = pointeur sur Elément
VAR L : LISTE
Manipulation d’une LSC :
Fonctions utiliséesAu vu de
 Initialisation l'utilisation des
listes chaînées,
 Ajout d'un élément
il se dessine
 Suppression d'un élément clairement
 Accès à l'élément suivant quelques fonctio
 Accès aux données utilisateur ns

indispensables :
Accès au premier élément de la liste
 Accès au dernier élément de la liste
 Calcul de la taille de la liste
 Suppression de la liste entière
 Trier une liste
 Fusionner deux listes
 Eclatement d’une liste
…
Fonctions de base Type :
Elément = enregistrement
num : entier
 Initialisation : suivant : pointeur sur
Création d’une liste vide Elément
Fin enregistrement
Liste = pointeur
Procédure CREATION_LISTE sur Elément
(VAR L : LISTE)
DEBUT
L ← NULL
FIN

 Ajout d’un élément

◦ Ajout en tête
◦ Ajout en queue L
 Affichage NULL
 Suppression d’un élément
◦ Suppression en tête
◦ Suppression en queue
◦ Suppression d’un élément donné.
 Fonctions de base : Ajout
Type
Elément = enregistrement
num : entier
 Ajout d’un élément suivant : pointeur sur
Elément
◦ Ajout en tête
Fin enregistrement
Liste :=LISTE
Fonction AJOUT_TETE (L : LISTE) pointeur sur Elément
VAR P : LISTE ; x: entier
DEBUT
Ecrire ("Donner un entier : " )
Lire (x)
P ← ALLOUER (taille (Elément)) ou /* ALLOUER
(P)*/
P → num ← x //(*P).num ← x
P → suivant ← L //(*P). suivant ← L /*L
est l’adresse
de la tête de la liste*/
◦ Ajout L← enP queue
AJOUT_TETE ← L
 Ajout en tête : Exemple
NULL 2
51 L:
3
3
74 L: NULL 1
201 L:
2

L : 0
100 L:
1
L:
Adresse = Adresse = Adresse = Adresse =
0
100 1 1
201 2 2
51 3 3
74 NULL
Fonctions de base : Ajout en queue
Fonction AJOUT_QUEUE (L : LISTE) :
LISTE P ← ALLOUER (taille
VAR (Elément))
Plast, P1 : LISTE // ou /* ALLOUER (P1)*/
x : entier P → num ← x
DEBUT P → suivant ← NULL
Ecrire ("Donner un entier : " ) Plast → suivant ← P
Lire (x)
Si (L = NULL) alors Fin Si
P ← ALLOUER (taille (Elément)) AJOUT_QUEUE ← L
P → num ← x FIN
P → suivant ← NULL
L←P
Si non NB : Le dernier
/*Plast est la valeur du pointeur sur élément d’une liste
le dernier Elément*/ non vide est non
Plast ← L
NULL mais son
Tant que ( Plast → suivant ≠
successeur est
NULL) faire
NULL
Plast ← Plast → suivant
Fin Tant que
 Ajout en queue : Exemple
L
NULL

L: P : plast= 0
100 1

P = 1 : plast
201 2

P= P=
3 74 NULL
2 51 3
L:
Adresse Adresse = Adresse = Adresse =
=x
100 1 1
201 2 2
51 3 3
74 NULL
Fonctions de base : Affichage
Parcours de liste simplement chainé
Version itérative
Procédure AFFICHE_ITER (L :
LISTE) Version
VAR récursive(L :
Procédure AFFICHE_REC
P : LISTE LISTE)
DEBUT DEBUT
P←L Si (L ≠ NULL) alors
Si (P = NULL) alors Ecrire (L → num)
Ecrire ("Liste vide " ) AFFICHE_REC (L→
suivant)
Si non Fin Si
Tant que ( P ≠ NULL) FIN
faire
Ecrire (P → num)
P ← P → suivant
Fin Tant que
Note
 Le principal problème des listes simplement
chaînées est l'absence de pointeur sur
l'élément précédent d’un Elément de liste,
 Il est donc possible de parcourir la
chaîne uniquement du début vers la
fin !
 C’est pourquoi il ne faut pas perdre l’adresse
de la tête de la liste ni l’adresse d’un
élément suivant.
 Si on perd une adresse d’un élément alors
tous les éléments suivants sont perdus.
Fonctions de base :
Suppression
Suppression d’un élément
◦ Suppression en tête
Fonction SUPP_TETE (L : LISTE) :
LISTE
VAR P : LISTE
DEBUT
P←L
L ← L → suivant
LIBERER (P)
SUPP_TETE ← L
FIN

◦ Suppression en queue
 Suppression en Tête :
Exemple
P: L:
Adresse Adresse = Adresse = Adresse =
=0
100 1 1
201 2 2
51 3 3
74 NULL
 Fonctions de base :
Suppression
Fonction en
SUPP_QUEUE (L :queue
LISTE) : LISTE
VAR Preced, P : LISTE
DEBUT
P←L
Si (P → suivant = NULL) alors // La liste contient un
seul élément
LIBERER (P)
L ← NULL
Si non // La liste contient au moins deux éléments
Preced NULL
P←L
Tant que ( (P→ suivant ≠ NULL) faire
PrecedP
P ← P → suivant
Fin Tant que
LIBERER (P)
Preced → suivant ← NULL
Fin Si
SUPP_QUEUE ← L
FIN
 Suppression en queue :
Exemple
L: Preced : P:
Adresse Adresse = Adresse = Adresse =
=x
100 1 1
201 2 2
51 NULL 3
74 NULL

Au départ :
Preced : NULL
P:L
 Fonctions de base :
Suppression d’un élément donné
Fonction SUPP_ELEMENT (L : Si (P → num = x) alors
LISTE) trouve ← vrai
: LISTE Sinon
VAR Preced, P : LISTE ; x : entier PrecedP
trouve : booléen P ← P → suivant
DEBUT Fin Si
Ecrire ("Donner l’élément à Fin Tant que
supprimer : " ) Si ( trouve = vrai ) alors
Lire (x) Preced → suivant ← P →
P←L suivant
trouve ← faux LIBERER (P)
Si (L → num = x) alors Si Non
/* suppression en tête*/ Ecrire ("élément inexistant
L ← L → suivant ")
LIBERER (P) Fin Si
Si non Fin Si
PrecedNULL SUPP_ELEMENT ← L
Tant que ( P ≠ NULL et trouve = FIN
 Suppression d’un élément
donné : Exemple

(Preced )L : preced p:
Adresse = Adresse = Adresse =
0
100 1 1
20 3 2
51 3
1 Preced Psuivant :
suivant
Adresse =
Au départ : 3
74 NULL
Preced : NULL
P:L
X=51