Module: ALGORITHMIQUE 2

Chapitre : Les Listes

Simplement Chaînées
Niveaux: 1A
Équipe ALGO
Année universitaire:
2022/2023 1
Objectifs Spécifiques
À la fin de ce chapitre, l’étudiant sera capable de :

▪ Comprendre le type Liste simplement chaînée.

▪ Stocker des données avec les Listes simplement chaînées.
▪ Manipuler une Liste simplement chaînée.
▪ Utiliser une Liste simplement chaînée en paramètre d’une fonction.
▪ Appliquer sur une Liste simplement chaînée différentes opérations
d’insertion/suppression d’éléments.

2
 Plan

1- Introduction
2- Définition et Déclaration des Liste simplement chaînées
3- Opérations basiques sur les Liste simplement chaînées
4- Opérations d’insertion/suppression sur les Liste simplement chaînées
5- Conclusion

2
 Introduction

▪ Un tableau représente en mémoire une collection de données de même type.

▪ Un tableau est manipulé sous forme linéaire:
La donnée à l’indice i+1 est consécutive en mémoire à la donnée d’indice i.

🡺 Cette Contiguïté peut ne pas être satisfaisante!

 Problématique 1

Supposons que vous êtes 9 étudiants et vous allez partir déjeuner. Deux d’entre
vous ont une voiture.

⇨ Est-ce que vous pouvez tous monter dans la même voiture??

Pareil si vous souhaitez utiliser un tableau et vous avez suffisamment d'espace mais qui
n'est pas forcément contiguë!

⇨ Comment profiter de l’espace mémoire valable mais non contiguë ?!

 Problématique 2
Vous êtes en train de jouer à un jeu de tours en bois. Retirer la dernière
pièce est une tâche triviale. Cependant, prendre la première pièce est une
tâche impossible!!

⇨ Il faut décaler toutes les pièces ajoutées, puis retirer la première, puis
reconstruire la tour!!!

Pareil si vous souhaitez supprimer une case à la fin d’un tableau, alors l’opération n’est
pas coûteuse. Par contre, insérer un élément au début nécessite un décalage du contenu de
toutes cases.

⇨ Traitement coûteux en terme de temps d'exécution d'un programme!

 Solution
Comme la notion d’élément suivant dans un tableau est une notion implicite, on a besoin de:

⇨ Expliciter la notion du suivant: utiliser l’adresse mémoire afin de désigner de façon unique
un élément.

On a besoin d’une structure de données qui:

- n'exige pas une contiguïté des éléments à stocker en mémoire.
- organise une série de données en mémoire et assemble des structures en les liant entre
elles à l'aide de pointeurs.

Les listes simplement chaînées (LSC) 2

 Connaissances Requises

● Une liste chaînée est une application typique de l’allocation dynamique de mémoire.

● Connaissances Requises:
▪ Les types de données, Les Structures de donnée, Les Enregistrements
▪ Les Pointeurs, L’Allocation Dynamique
▪ Les Fonctions et les Procédures

2
Définition et Déclaration d’une Liste
Simplement Chaînées (LSC)

9
 Définition

▪ Les listes chaînées sont des structures de données semblables aux tableaux sauf que
l'accès à un élément ne se fait pas par index mais à l'aide d'un pointeur.
▪ L'allocation de la mémoire est faite au moment de l'exécution.

▪ En ce qui concerne l'emplacement, en revanche, par rapport aux tableaux où les éléments
sont contigus dans la mémoire, les éléments d'une liste sont éparpillés dans la mémoire.
En réalité, dans la mémoire la représentation est aléatoire en fonction de l'espace alloué.

▪ En ce qui concerne l'enchaînement, les éléments sont contigus dans une liste. La liaison
entre les éléments se fait grâce à un pointeur.
 Description
▪ Une liste simplement chaînée est une suite d'un nombre variable d'objets de même
type et chaque élément, sauf le dernier, pointe vers son successeur.

▪ Une liste simplement chaînée est une structure de donnée constituée d’éléments
contenant chacun:
- une donnée
- une référence (adresse ou pointeur) de l’élément suivant

Élément :
Données Pointeur sur l’élément suivant
 Description

● La liste est elle-même totalement déterminée par la référence (adresse) de son premier élément
⇒ premier élément = tête de liste
● Une liste chaînée est une succession d’éléments, dont le dernier élément doit pointer vers NULL (la
fin de la liste) ⇒ le dernier élément n’a pas de successeur (son successeur est la constante NULL).
L

Premier Élément Dernier Élément

(tête de la liste) (pointe vers NULL)

● Pour accéder à un élément, la liste est parcourue en commençant avec la tête, le pointeur suivant
permettant le déplacement vers le prochain élément.
● Le déplacement se fait dans une seule direction, du premier vers le dernier élément.
 Déclaration

Chaque élément d’une liste simplement chaînée (LS) est un enregistrement composé de
deux parties:
a. Données (un ou plusieurs champs)
b. Pointeur sur le même enregistrement (il s’agit d’une déclaration récursive)

Syntaxe
Type
<nom_element> = Enregistrement
champ_1: type_1
champ_2: type_2
…
<suivant_pointeur> : pointeur sur <nom_element> // ou *<nom_element>
FinEnregistrement
<nom_type> = pointeur sur <nom_element> // ou *<nom_element>
 Déclaration
Exemple
Type
Element= Enregistrement
val: entier
suivant : pointeur sur Element // ou *Element
FinEnregistrement
LSC = pointeur sur Element // ou *Element
Var L: LSC

L @20FA

12 @1020
30 @75AB
42 @66CC
99 NULL
@20FA @1020 @75AB @66CC

Premier Élément
Dernier Élément
(tête de la liste)
(pointe vers NULL)
 Opérations sur les listes LSC

● Initialisation (ou création) d’une liste (en général, liste vide)

● Test permettant de déterminer si une liste est vide
● Passage à l’élément suivant
● Parcours d’une liste
● Recherche d’un élément dans une liste
● Ajout d’un élément dans une liste
● Suppression d’un élément dans une liste
Opérations élémentaires sur les LSC

16
 Création de LSC vide
(initialisation)

Procédure CREATION_LSC( L : *LSC)

Début
*L ← NULL
Fin
 Affichage d’une LSC
Procédure AFFICHAGE(L : LSC)
Var P : LSC
Début
P←L
Si (P = NULL) Alors
écrire("Liste vide !")
Sinon
Tant que (P != NULL) Faire
écrire(*P.val)
P ← *P.suivant
Fin tant que
Fin si
Fin
 Recherche d’élément dans une LSC

Fonction RECHERCHE(L : LSC, x : entier) : LSC // ou *Element

Var P : LSC
Début
P←L
Tant que ((P != NULL) ET (*P.val != x)) Faire
P ← *P.suivant
Fin tant que
RECHERCHE ← P

Fin
 Application 1

● Exercice 1:

Taille d’une LSC

● Exercice 2:

Recherche du dernier élément d’une LSC

Recherche du prédécesseur d’un élément donné

Opérations d’Insertion
sur les LSC

21
 Ajout en tête d’une LSC
L
3

P 12 30 42 99

2
10

1 Allocation du nouvel élément et affectation de la nouvelle valeur

2 Chaînage avec l’ancienne tête de liste

3 Mise à jour la tête de la liste

 Ajout en tête d’une LSC

Fonction AJOUT_TETE(L : LSC, x : entier) : LSC

Var P : LSC
Début
P ← allouer(taille(Element))
1
*P.val ← x
*P.suivant ← L // chaînage avec ancienne liste 2
L←P // mise à jour de la nouvelle tête de liste 3
AJOUT_TETE ← L
Fin
 Pred
Ajout en queue d’une LSC
L 2

12 30 42 99

10 1
P

1 Allocation du nouvel élément pointée par P, affectation de la nouvelle valeur et mise à jour du
champ suivant qui pointe vers NULL

2 Accès au dernier élément (via Pred)

3 Chaînage du dernier élément pointé par (Pred) avec le nouvel élément (P)

ATTENTION: Cas particulier si Liste est vide au départ!!

 Ajout en queue d’une LSC
Fonction AJOUT_QUEUE(L : LSC, x : entier) : LSC
Var P, Pred: LSC
Début
P ← allouer(taille(Element))
*P.val ← x 1
*P.suivant ← NULL
Si (L = NULL) Alors // Cas particulier: Liste vide
L←P
Sinon // Cas général: Ajout à la fin de la liste
Pred ← L
Tant que (*Pred.suivant != NULL) Faire 2
Pred ← *Pred.suivant
Fin tant que
Remarque
*Pred.suivant ← P 3
Fin si Vérifier toujours les cas particuliers :
dans ce cas si la liste L initialement
AJOUT_QUEUE ← L
vide Sinon risque de bug (plantage)
Fin lors de l’exécution
 Application 2

● Exercice 3:

- insertion d’une valeur x après une valeur y

- insertion d’une valeur x avant une valeur y

Opérations de suppression
sur les LSC

27
 Suppression en tête dans une LSC
2
L

12 30 42 99

3
P
1

1 Mémorisation de l’ancienne tête de liste dans P

2 Avancement de la tête de liste

3 Libération de l’ancienne tête de liste

 Suppression en tête dans une LSC

Fonction SUPP_TETE(L : LSC) : LSC

Var P: LSC
Début
Si (L <> NULL) Alors
P←L 1
L ← *L.suivant 2
libérer(P) 3
Finsi
SUPP_TETE ← L
Fin
 Suppression en queue dans une LSC
P 2
L

12 30 42 99

1
Pred 3

1 Accès à l’avant dernière cellule pointée par Pred

2 Mise à jour du lien suivant de l’élément Pred vers NULL

3 Libération du dernier élément P

ATTENTION: Discuter le(s) cas particuliers (cas d’une liste avec un seul élément )!!
 Suppression en queue dans une LSC
Fonction SUPP_QUEUE(L : LSC) : LSC
Var P, Pred: LSC Libérer(P) 3
Début Finsi
Si (L <> NULL) Alors //liste non vide SUPP_QUEUE ← L
P←L Fin
Pred ← NULL
Tant que (*P.suivant <> NULL) Faire
1
Pred← P
P ← *P.suivant
Fin tant que
Si (Pred = NULL) alors //liste contenant 1 seul élément
Remarque
P←L
L ← NULL Vérifier toujours les cas particuliers : dans ce cas si la liste L
Sinon initialement vide, si la liste contient un seul élément , Sinon
risque de bug (plantage) lors de l’exécution
*Pred.suivant ← NULL 2
Fin si
 Application 3

● Exercice 3:

- suppression d’une valeur x d’une liste simplement chaînée

Conclusion

33
 Avantages et Inconvénients
Avantages Problèmes
● Manipulation (e.g. ajout, suppression) ● Absence de pointeur sur l’élément qui
sans décalage précède l'élément courant.

● Allocation dynamique ● Parcours séquentiel du début vers la fin.

● Les structures qui composent une liste ● Identification par sa tête (Si perte de
simplement chaînée peuvent ne pas pointeur de début ⇒ Perte de toute la
être placées dans l’ordre en mémoire liste).
et encore moins de façon contiguë.