Chapitre 3

Listes chaînées

Azzeddine Mazroui
Licence MIP S4
2024-2025
Définitions
❑Une liste est une séquence finie formée de plusieurs
éléments de même type.
❑Chaque élément dans une liste est repéré par son rang (sa
place) dans cette liste.
❑Le nombre d’éléments dans une liste représente sa
longueur (sa taille).
❑Exemples :
➢La listes des entiers naturels impairs ≤ 20 :
{1, 3, 5, 7, 9, 11, 13, 15, 17, 19} ;
➢La liste des mois ayant moins de 31 jours :
{ février, avril, juin, septembre, novembre } ;
➢La liste des étudiants de MIP S4 classés par ordre
alphabétique.
Structures de données 2024-2025 A. Mazroui 2
Opérations sur les listes
❑ Opérations fondamentales :

➢ Implémentation d’une liste

➢ Insertion d’un élément dans la liste ;

➢ Suppression d’un élément de la liste ;

➢ Affichage de la liste.

❑ Autres opérations :

➢ Recherche d’un élément dans la liste ;

➢ Tri de la liste.

Structures de données 2024-2025 A. Mazroui 3

 Implémentation des listes
❑ On peut implémenter une liste selon deux approches :
➢Implémentation contiguë : Elle repose sur l'utilisation
d'un tableau pour stocker les éléments de la liste. Les
données sont placées dans des emplacements de
mémoire consécutifs.
➢Implémentation non contiguë : Elle utilise des
structures de données dynamiques, où chaque élément
contient une donnée et un pointeur vers le suivant. Les
données ne sont pas nécessairement stockées dans des
emplacements de mémoire consécutifs.
Structures de données 2024-2025 A. Mazroui 4
 Implémentation contiguë

❑ L'implémentation contiguë utilise un seul bloc de mémoire

contiguë pour stocker tous les éléments de la liste.

❑ Elle consiste à créer une structure Liste composée de deux

champs :

➢Un tableau A qui stocke les différents éléments de la

liste ;

➢Une variable taille qui mémorise le nombre d’éléments

présents dans la liste.

Structures de données 2024-2025 A. Mazroui 5

Implémentation contiguë :
Déclaration d’une liste
Exemple :

Max-1
#define Max 100

Typedef struct {

int A[Max]; /* Conteneur des éléments*/ taille-1

int taille; /* Nombre réel d’éléments de A*/
} Liste1;

&taille A
Liste1
Structures de données 2024-2025 A. Mazroui 6
Implémentation contiguë :
Déclaration d’une liste vide
❑ La contiguïté signifie que les éléments du tableau A
associé à la liste sont stockés dans la mémoire un à côté
de l’autre.
❑ Elle offre un accès rapide aux éléments par leur indice,
et il est possible d’accéder à tous les éléments de la
liste à partir de l’adresse du tableau A.
❑ En effet, si les éléments du tableau A sont des entiers,
alors : &A[i] = &A[0]+4i = A+4i
i 0 1 2 3 4
A[i] 38 19 71 20 24
Adresse @144 @148 @152 @156 @160
Structures de données 2024-2025 A. Mazroui 7
Implémentation contiguë :
Création d’une liste vide
❑ L’initialisation de la liste consiste à affecter la
valeur 0 au champs taille.

void InitialiserListe (Liste1 *LV) {

LV->taille = 0 ; }

Structures de données 2024-2025 A. Mazroui 8

Implémentation contiguë :
Insertion

❑ Dans une liste, on peut insérer un Max-1

élément

➢ à la fin de la liste ;
taille-1
➢ à un rang k de la liste ;

➢ au début de la liste.

&taille A
Liste1
Structures de données 2024-2025 A. Mazroui 9
Implémentation contiguë :
Insertion en fin de liste
❑ Algorithme :
Max-1
1. Tester si la liste n’est pas pleine.
2. Si c’est le cas, stocker le nouveau
élément à l’emplacement [taille].
taille-1
3. Incrémenter taille.

❑ Code C :
void insererFin(Liste1 *L, int valeur){
if(L->taille < Max) {
&taille A
L->A[L->taille] = valeur;
L->taille++; } } Liste1
Structures de données 2024-2025 A. Mazroui 10
 Implémentation contiguë :
Insertion au rang k
Exemple : k=2 , taille= 5
Max-1
Algorithme :
❑ Tester si la liste n’est pas pleine.
Si oui :
1. Décaler vers le haut les éléments
⋮
A[k], …, A[taille-1];
[Link] le nouveau élément (NE) taille-1 A[4]
dans A[k]; A[3]
[Link]émenter taille. A[2]
A[1]
A[0]
Structures de données 2024-2025 A. Mazroui 11
 Implémentation contiguë :
Insertion au rang k
Exemple : k=2 , taille= 5
Code C : Max-1

void insererMilieu(Liste1 *L, int NE, int k) {

if(L->taille < Max) {
int i;
⋮
taille-1 A[5]=A[4]
for(i = L->taille; i > k; i--) {
taille-1 A[4]=A[3]
L->A[i] = L->A[i - 1]; }
A[3]=A[2]
L->A[k] = NE; A[2]=NE
L->taille++; } A[1]=A[1]
A[0]=A[0]
}
Structures de données 2024-2025 A. Mazroui 12
 Implémentation contiguë :
Insertion au début de la liste

❑ Cette opération est un cas particulier de l’insertion

au rang k avec k = 0.

Structures de données 2024-2025 A. Mazroui 13

 Implémentation contiguë :
Suppression de la fin de la liste
Exemple : k=2 , taille= 6
Algorithme :
Max-1
❑ Tester si la liste n’est
pas vide.
❑ Si c’est le cas, ⋮
décrémenter taille.
taille-1 A[5]
taille-1 A[4]
Code C : A[3]
void supprimerFin(Liste1 *L) { A[2]
if (L->taille > 0) A[1]
A[0]
L->taille--; }
Structures de données 2024-2025 A. Mazroui 14
 Implémentation contiguë :
Suppression au rang k
Exemple : k=2 , taille= 6

Algorithme : Max-1

❑ Tester si la liste n’est pas vide.

Si oui : ⋮
➢ Décaler vers le bas les éléments taille-1 A[5]
taille-1 A[4]=A[5]
A[k], A[k+1], …, A[taille-1] ;
A[3]=A[4]
➢ Décrémenter taille. A[2]= A[3]
A[1]=A[1]
A[0]=A[0]
Structures de données 2024-2025 A. Mazroui 15
 Implémentation contiguë :
Suppression au rang k
Exemple : k=2 , taille= 6
Max-1
Code C :
void supprimerMilieu(Liste1 *L, int k) {
if(L->taille > 0) {
⋮
int i; taille-1 A[5]
for(i = k; i < L->taille; i++) taille-1 A[4]=A[5]

{ L->A[i] = L->A[i+1];} A[3]=A[4]

A[2]= A[3]
L->taille--; }
A[1]=A[1]
} A[0]=A[0]
Structures de données 2024-2025 A. Mazroui 16
Implémentation contiguë :
Suppression au début de la liste

❑ Cette opération est un cas particulier de la

suppression au rang k avec k = 0.

Structures de données 2024-2025 A. Mazroui 17

Implémentation contiguë :
Affichage de la liste

void afficherListe(Liste1 *L){

int i;
for(i = 0; i < L->taille ; i++)

printf ("%d", L->A[i]);

Structures de données 2024-2025 A. Mazroui 18

Implémentation contiguë :
Avantages

❑Simplicité du code.

❑L’opération d’accès à un élément est très rapide.

❑Très utile pour représenter des structures linéaires

statiques telles que les vecteurs et les Matrices.

Structures de données 2024-2025 A. Mazroui 19

Implémentation contiguë :
Inconvénients

❑ La taille d’un tableau statique est fixe. D’où la

nécessité de spécifier une borne supérieure de cette
taille au moment de la compilation, ce qui entraîne
d’allouer une quantité de mémoire qui peut ne pas être
utilisée totalement.

❑ L’insertion en une position intermédiaire d’un nouvel

élément est coûteuse car elle nécessite le décalage des
éléments existants.

Structures de données 2024-2025 A. Mazroui 20

Implémentation non contiguë :
Listes chainées

❑A la différence de l’implémentation contiguë, la

représentation en mémoire des éléments de la liste dans
l’implémentation non contiguë n’est pas ordonnée (c.à.d.
les éléments ne sont pas placés dans la mémoire les uns
après les autres).
Eléments
38 19 71 20 24
de la liste
Adresses @404 @1248 @152 @556 @2160

❑ Pour pouvoir accéder à un élément de la liste, il suffit

de disposer de son adresse.
Structures de données 2024-2025 A. Mazroui 21
 Implémentation non contiguë :
Listes chainées
❑ Dans une liste chainée, les éléments sont composés de
deux parties : la valeur de l’élément et l’adresse de
l’élément suivant.

Un élément Valeur de l’élément

d’une liste = Adresse de l’élément suivant
chainée

Valeurs 38 19 71 20 24
@1248 @152 @566 @2160 NULL
Vraies adresses @404 @1248 @152 @566 @2160

Structures de données 2024-2025 A. Mazroui 22

Implémentation non contiguë :
Listes simplement chainées
❑ Une liste simplement chainée est un ensemble d’éléments reliés.
❑ Chaque élément de la liste est appelé nœud (node en anglais).
❑ Chaque nœud contient :
➢ un champs contenant des informations sur l’objet (données).
➢ un pointeur sur le nœud suivant de la liste égal à :
o L’adresse du nœud suivant si ce dernier existe ;
o NULL s’il n’y a pas de nœud suivant.

Données

⋯
Adresse
⋯ NULL

Nœud du suivant

Structures de données 2024-2025 A. Mazroui 23

Implémentation non contiguë :
Listes simplement chainées

❑ Pour définir une liste simplement chainée, on

commence par définir la structure qui représente les
éléments (les nœuds) de la liste.
❑ Exemple : Structure d’un élément identifiée par sa
valeur entière.

typedef struct {
int valeur;
struct Node *suivant;
} Node ;
Structures de données 2024-2025 A. Mazroui 24
Implémentation non contiguë :
Listes simplement chainées

❑ Ensuite, on définit la fonction qui permet de créer un

nouveau nœud.

Node* creerNode(int valeur) {

Node *nouveauNode = (Node*)malloc(sizeof(Node));
if (nouveauNode == NULL)
exit(EXIT_FAILURE);
nouveauNode->data = valeur;
nouveauNode->suivant = NULL;
return nouveauNode; }
Structures de données 2024-2025 A. Mazroui 25
Implémentation non contiguë :
Insertion au début d’une liste
❑ Étapes:
[Link] pointer le pointeur suivant du nouveau nœud vers
la tête de la liste.
[Link]érer le nouveau nœud comme tête de liste.

tete tete
valeur valeur valeur
suivant suivant suivant
⋯⋯

Nouveau valeur
nœud Null
suivant

Structures de données 2024-2025 A. Mazroui 26

Implémentation non contiguë :
Insertion au début d’une liste
Node* ins_Debut (Node* tete, Node* nouv_Node){
nouv_Node ->suivant = tete;
return nouv_Node;
}

tete tete
valeur valeur valeur
suivant suivant suivant
⋯⋯

Nouveau valeur
nœud Null
suivant

Structures de données 2024-2025 A. Mazroui 27

Implémentation non contiguë :
Insertion en fin de liste

❑ Étapes :
[Link] le dernier nœud de la liste.
[Link] pointer le pointeur le pointeur suivant du dernier
nœud vers le nouveau nœud.

valeur valeur valeur

⋯ ⋯ suivant suivant NULL suivant

valeur Nouveau
NULL nœud
Structures de données 2024-2025 A. Mazroui 28
Implémentation non contiguë :
Insertion en fin de liste
Node* ins_Fin(Node* tete, Node* nouv_Node){
Node *temp = tete;
while (temp->suivant != NULL) {
temp = temp->suivant; }
temp->suivant = nouv_Node;
return tete;
}

valeur valeur valeur

⋯ ⋯ suivant suivant NULL suivant

valeur Nouveau
NULL nœud
Structures de données 2024-2025 A. Mazroui 29
Implémentation non contiguë :
Insertion au rang k de la liste
❑ Étapes:
[Link] le nœud à la position k (l'insertion se fera
après ce nœud).
[Link] pointer le pointeur suivant du nouveau nœud vers
le nœud à la position k+1.
[Link] pointer le pointeur suivant du nœud à la position k
vers le nouvel nœud.
Rang k
valeur valeur valeur valeur
⋯⋯ ⋯⋯
suivant suivant suivant NULL

Nouvel valeur
élément suivant 30
 Implémentation non contiguë :
Insertion au rang k de la liste
Node* ins_Dans_Liste (Node* tete, Node* nouv_Node, int k){
Node *courant = tete;
int i;
for(i=1; i<k; i++)
courant = courant->suivant;
nouv_Node ->suivant = courant->suivant;
courant->suivant = nouv_Node;
return tete; }
Rang k
valeur valeur valeur valeur
⋯⋯ ⋯⋯
suivant suivant suivant NULL

Nouvel valeur
élément suivant 31
 Implémentation non contiguë :
Suppression au début de la liste

Node* supp_Debut(Node* tete) {

if (tete == NULL)
Étape : Considérer le printf("La liste est déjà vide.\n");
deuxième nœud comme else {
Node* temp = tete;
tête de liste.
tete = temp -> suivant;
free(temp); }
return tete; }

tete tete

valeur valeur valeur valeur

⋯⋯
suivant suivant suivant NULL 32
Implémentation non contiguë :
Suppression au rang k
❑ Étapes:
[Link] le nœud à la position k-1.
[Link]éer un pointeur temp qui contient l'adresse du nœud à
supprimer (le nœud à la position k).
[Link] pointer le pointeur suivant du nœud courant sur le
nœud sur lequel pointe le pointeur suivant du nœud à
supprimer.
[Link]érer la mémoire occupée par temp.

temp
valeur valeur valeur valeur valeur
⋯⋯ ⋯⋯
suivant suivant suivant suivant NULL
Rang k-1 33
Implémentation non contiguë :
Suppression au rang k
Node* supp_Dans_Liste (Node *tete, int k){
Node *courant = tete;
int i;
for (i = 1; i < k-1; ++i)
courant = courant->suivant;
Node * temp = courant->suivant;
courant->suivant = temp->suivant;
temp = NULL; free (temp);
return tete;
}
temp
valeur valeur valeur valeur valeur
⋯⋯ ⋯⋯
suivant suivant suivant suivant NULL
Rang k-1 34
Implémentation non contiguë :
Affichage d’une liste chainée
void afficher (Node *tete) {
if (tete == NULL)
printf("La liste est vide \n");
else {
Node * courant ;
courant = tete;
while (courant != NULL) {
printf("%d \n", courant->valeur);
courant = courant->suivant;
}
}
} 35
 Implémentation non contiguë :
Avantages des listes chainées

❑Flexibilité : Les listes chainées peuvent facilement être

agrandies ou réduites, car la taille n'est pas définie à l'avance.

❑Insertion et suppression d'éléments : Ces opérations sont

généralement plus rapides que dans les tableaux, car elles ne
nécessitent pas de décalage des éléments.

❑Efficacité de la mémoire : Elles sont plus économes en

mémoire que les tableaux, car elles n'allouent de la mémoire
que pour les éléments effectivement présents dans la liste.

Structures de données 2024-2025 A. Mazroui 36

 Implémentation non contiguë :
Inconvénients des listes chainées

❑ Accès aux éléments : L'accès à un élément n'est pas

direct, car il nécessite de parcourir la liste depuis le début,
ce qui peut entraîner une complexité temporelle élevée
dans certaines situations.

❑ Utilisation de la mémoire : Les pointeurs stockés dans

chaque nœud peuvent consommer une quantité
importante de mémoire.

Structures de données 2024-2025 A. Mazroui 37

 Comparaison entre listes chainées
et tableaux

Tableau Liste chainée

Mémoire Statique Dynamique

Accès à un À l’aide de son indice Par un pointeur

élément (O(1)) (O(n))

Déplacement couteux Pas besoin de déplacer

insertion/ lors des les éléments lors des
suppression insertions/suppressions insertions/suppressions
(O(n)) (O(1))

Structures de données 2024-2025 A. Mazroui 38

Implémentation non contiguë :
Destruction de la liste

❑ Pour détruire la liste entière, on peut utiliser la

suppression au début de la liste tant que la tête de la liste
n’est égale à NULL.

Node* detruire (Node *tete){

while (tete != NULL)

supp_Debut (tete);

return tete;

} 39