Liste simplement chaînée-Chapitre
1
9
ENISO – IA1,GTE1, 2024-2025
Dr Ghassen Hamdi ©
G. HAMDI
Définition
2
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.
G. HAMDI
Définition
3
La liaison entre les éléments se fait grâce à un pointeur.
En réalité, dans la mémoire la représentation est
aléatoire en fonction de l'espace alloué.
Le pointeur suivant du dernier élément doit pointer vers
NULL (la fin de la liste). 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.
G. HAMDI
Caractéristiques d’une liste
4
Chaque élément d'une liste chaînée est composé de deux
parties :
la valeur qu’on veut stocker,
l'adresse de l'élément suivant, s'il existe.
S'il n'y a plus d'élément suivant, alors l'adresse sera NULL, et
désignera la fin de la liste.
Voilà deux schémas pour expliquer comment se passent l'ajout
et la suppression d'un élément d'une liste chaînée. Remarquons
le symbole en fin de la liste qui signifie que l'adresse de
l'élément suivant ne pointe sur rien, c'est-à-dire sur NULL.
G. HAMDI
Déclaration d'une liste
5
chainée en C
On doit obligatoirement spécifier le type de l'élément de la
liste chaînée. En effet, on peut créer des listes chaînées de
n'importe quel type d'éléments : entiers, caractères,
structures, tableaux, voir même d'autres listes chaînées. On
peut même combiner plusieurs types dans une même liste.
Exemple : oustruct
bien element {
typedef struct element { int val;
int val; struct element * suivant;
};
struct element *suivant; struct element *
} element; Liste=NULL;
element * Liste=NULL;
G. HAMDI
Déclaration d'une liste
6
chainée en C
On crée le type element qui est une structure contenant un
entier (val) et un pointeur sur élément (suivant), qui contiendra
l'adresse de l'élément suivant.
Ensuite, il nous faut créer la variable Liste qui est en fait un
pointeur sur le type element. Lorsque nous allons déclarer la
liste chaînée, nous devrons déclarer un pointeur sur element,
l'initialiser à NULL, pour pouvoir ensuite allouer le premier
élément.
N'oubliez pas d'inclure stdlib.h afin de pouvoir utiliser la macro
NULL. Il est important de toujours initialiser la liste chaînée à
NULL. Le cas échéant, elle sera considérée comme contenant au
moins un élément. C'est une erreur fréquente.
G. HAMDI
Manipulation des listes
7
chainées
Maintenant que nous savons comment déclarer une liste
chaînée, il serait intéressant d'apprendre à ajouter des éléments
dans cette liste, à supprimer des éléments de cette liste,
rechercher un élément dans cette liste, de compter le nombre
d’éléments que contient cette liste, ainsi que de lire et
d’afficher ce qu'elle contient.
1. Ajouter un élément
Lorsque nous voulons ajouter un élément dans une liste
chaînée, il faut savoir où l'insérer. Les deux ajouts génériques
des listes chaînées sont les ajouts en tête, et les ajouts en fin
de liste.
Ajouter en tête
Lors d'un ajout en tête, nous allons créer un élément, lui
assigner la valeur que l'on veut ajouter, puis pour terminer,
G. HAMDI
raccorder cet élément à la liste passée en paramètre. Lors
Manipulation des listes
8
chainées
On crée un nouvel élément puis on le relie au début de la liste
originale. Si l'original est (vide) c'est NULL qui sera assigné au
champ suivant du nouvel element. La liste contiendra dans ce
cas-là un seul élément. G. HAMDI
Manipulation des listes
9
chainées
Ajouter en fin de liste
Cette fois-ci, c'est un peu plus compliqué. Il nous faut tout
d'abord créer un nouvel élément, lui assigner sa valeur, et
mettre l'adresse de l'élément suivant à NULL. En effet,
comme cet élément va terminer la liste nous devons signaler
qu'il n'y a plus d'élément suivant. Ensuite, il faut faire pointer
le dernier élément de liste originale sur le nouvel élément
que nous venons de créer. Pour ce faire, il faut créer un
pointeur temporaire sur element qui va se déplacer
d'élément en élément, et regarder si cet élément est le
dernier de la liste. Un élément sera forcément le dernier de la
liste si NULL est assigné à son champ suivant.
G. HAMDI
Manipulation des listes
10
chainées
Comme vous remarquez, nous nous déplaçons le long de la liste
chaînée grâce au pointeur tempo. Si l'élément pointé par tempo
n'est pas le dernier (tempo->suivant != NULL), on avance d'un pas
(tempo = tempo->suivant) en assignant à tempo l'adresse de
l'élément suivant. Une fois que l'on est au dernier élément, il ne
reste plus qu'à le relier au nouvel élément crée.
G. HAMDI
Manipulation des listes
11
chainées
Affichage du contenu de la liste
Le programme suivant va nous servir pour afficher le contenu
de la liste.
G. HAMDI
Manipulation des listes
12
chainées
2. Suppression d’un élément de la liste
Supprimer un élément en tête
Il s'agit là de supprimer le premier élément de la liste. Pour ce faire,
il nous faudra utiliser la fonction free que vous connaissez
certainement. Si la liste n'est pas vide, on stocke l'adresse du
premier élément de la liste après suppression (i.e. l'adresse du 2ème
élément de la liste originale), on supprime le premier élément, et on
renvoie la nouvelle liste. Attention quand même à ne pas libérer le
premier élément avant d'avoir stocké l'adresse du second, sans quoi
il sera impossible de la récupérer.
G. HAMDI
Manipulation des listes
13
chainées
Supprimer un élément en fin de liste
Cette fois-ci, il va falloir parcourir la liste jusqu'à son dernier
élément, indiquer que l'avant-dernier élément va devenir le dernier
de la liste et libérer le dernier élément pour enfin retourner le
pointeur sur le premier élément de la liste d'origine..
G. HAMDI
Manipulation des listes
14
chainées
3. Rechercher un élément dans une liste
Le but de cette fonction est de renvoyer l'adresse du premier
élément trouvé ayant une certaine valeur. Si aucun élément
n'est trouvé, on renverra NULL. L'intérêt est de pouvoir, une
fois le premier élément trouvé, chercher la prochaine
occurrence en recherchant à partir de element Trouve-
>suivant. On parcourt donc la liste jusqu'au bout, et dès
qu'on trouve un élément qui correspond à ce que l'on
recherche, on renvoie son adresse.
G. HAMDI
