COURS
Atelier Programmation 2
CHAPITRE :
LES LISTES CHAÎNÉES
Chapitre : Les Listes Chaînées
1 Définition
Une liste chaînée est une structure comportant des champs
contenant des données et un pointeur vers une structure de même
type.
Une liste chaînée est une suite finie (éventuellement vide)
d’éléments de même type repérés selon leur rang dans la liste.
Données Données Données
Pointeur vers Pointeur vers Pointeur vers
l’élément suivant l’élément suivant l’élément suivant
2 Caractéristiques d’une liste chaînée
2.1 Quelques Principes
● Une liste chaînée est utilisée pour stocker des données qui doivent
être traitées de manière séquentielle
● Les éléments de la liste appelés cellule, nœuds ou maillons, ne
sont pas rangés les uns à côté des autres
● On a besoin de connaître, pour chaque élément, la position
(l’adresse) de l’élément qui le suit
2
Chapitre : Les Listes Chaînées
✔ On dispose d’un pointeur de tête qui contient l’adresse du
premier élément de la liste
✔ le dernier nœud ne pointe vers rien, il est nécessaire de renseigner son pointeur
avec la valeur NULL
2.2 Inconvénients
Contrairement au tableau, pour accéder à un élément il faut parcourir
la liste.
2.3 Avantages
Pour déplacer un élément (Ajout, Suppression), il suffit de modifier
ses liens.
3 Création d’une liste chaînée
3.1 Déclaration
Pour créer une liste chaînée en langage C, il s'agit dans un premier
temps de définir la structure de données, ainsi qu'un pointeur vers une
structure du type de celle définie précédemment, afin de pointer vers
la tête de la liste, c'est-à-dire le premier élément.
Syntaxe:
struct <Nom_Cellule>
{
// Déclaration des champs de la cellule
// pointeur sur l’élément suivant
};
struct <Nom_Cellule> * <Pointeur_Sur_Premier_Elément>;
3
Chapitre : Les Listes Chaînées
Exemple: Liste chaînée d’entiers
struct Cellule{
int valeur ;
struct Cellule *suiv ;
};
typedef struct Cellule *Liste;
Liste tete;
15 10 22 6
tete
3.2 Création d’une liste vide
Pour créer une liste vide, il suffit d’affecter la valeur NULL à la
variable de type "pointeur sur Liste" :
tete = NULL ;
tete
NULL
3.3 Création d’une liste contenant un seul élément
Les différentes étapes à suivre sont :
Définir tout d’abord les pointeurs
struct Cellule * tete; //pointeur tête de liste
struct Cellule * Nouveau;
ou Liste tete; //pointeur tête de liste
Liste Nouveau;
Allouer la mémoire nécessaire au nouveau maillon grâce à la fonction malloc
4
Chapitre : Les Listes Chaînées
Nouveau=(struct Cellule *)malloc(sizeof(struct Cellule));
ou
Nouveau=(Liste)malloc(sizeof(Cellule));
Renseigner ce nouveau maillon
Nouveau->valeur = Val ; //Val de type entier
Nouveau->suivant = NULL ;
✔ définir le nouveau maillon comme maillon de tête de liste
tete = Nouveau ;
3.4 Exemple de création
Création d’une liste chaînée d’entiers.
liste Creation_Liste (liste L, int n)
{
int i;
Liste prec;
Liste cour;
if (n>0)
{
//créer la première cellule
cour = (Liste )malloc (sizeof(Cellule ));
printf ("Entrer un entier \n");
scanf ("%d", &(cour->valeur));
cour->suivant = NULL;
*L = cour ; //adresse du premier élément
for (i=1 ; i<n ; i++)
{
prec = cour ;
5
Chapitre : Les Listes Chaînées
cour = (Liste )malloc (sizeof(Cellule ));
printf ("Entrer un entier \n");
scanf ("%d", &(cour->valeur));
cour->suivant = NULL;
prec->suivant = cour;
}
}
else
*L=NULL;
return L;
}
4 Ajout d’un élément
L’opération ajout, appelée aussi insertion, peut être effectuée de
trois manières :
● Insertion en tête de liste,
● Insertion en fin de liste,
● Insertion en milieu de liste.
4.1 Ajout un élément en tête de liste
Exemple 1:
ajouter un élément, puis un 2ème élément, maintenant un 3ème -->
le cas général d'insertion en tête.
Ainsi:
Une fois la structure et les pointeurs définis, il est possible d'ajouter
un premier maillon à la liste chaînée, puis de l'affecter au pointeur
tête de liste. Pour cela il est nécessaire :
✔ d'allouer la mémoire nécessaire au nouveau maillon grâce à la
fonction malloc
6
Chapitre : Les Listes Chaînées
Nouveau=(Liste )
malloc(sizeof(Cellule));
Nouveau->valeur = Val ; //Val de type entier
✔ d'assigner au champ "pointeur" du nouveau maillon, la valeur du
pointeur vers le maillon de tête liste
Nouveau->Suivant = tete;
✔ définir le nouveau maillon comme maillon de tête
tete = Nouveau;
Exemple 2:
reprendre avec un code propre exemple 1 --> passer à l'appel
d'une fonction insertionTete
7
Chapitre : Les Listes Chaînées
4.2 Ajout un élément en fin de liste
L'ajout d'un élément à la fin de la liste chaînée est similaire à celui
de l’ajout en tête de liste, à la différence près qu'il faut définir un
pointeur, (appelé généralement pointeur courant, afin de parcourir
la liste jusqu'à atteindre le dernier maillon (celui dont le pointeur
possède la valeur NULL).
Les étapes à suivre sont donc :
✔ définition d'un pointeur courant
Liste Courant=tete;
✔ parcours de la liste chaînée jusqu'au dernier nœud
while (Courant->Suivant != NULL)
Courant = Courant->Suivant;
✔ allocation de la mémoire pour le nouvel élément
Nouveau=(Liste ) malloc(sizeof(Cellule));
Nouveau->valeur = Val ; //Val de type entier
✔ faire pointer le pointeur courant vers le nouveau noeud, et le
nouveau noeud vers NULL
Courant->Suivant = Nouveau;
Nouveau->Suivant = NULL;
8
Chapitre : Les Listes Chaînées
5 Parcours de liste: Afficher la liste, Rechercher un élément, ...
L’opération de recherche d'un élément dans une liste chaînée consiste
à parcourir cette liste jusqu’à ce qu’on trouve un maillon qui contient la
valeur recherchée.
while (Courant != NULL && Courant->valeur != Val) {
Courant = Courant->Suivant;
}
Exemple:
int Recherche (Liste L , int Val)
{
int trouve=0;
Liste p;
p=L ;
while (p != NULL && !trouve)
{
if (p->valeur == Val)
trouve = 1;
//avancer dans la liste
p = p -> suivant;
return(trouve);
}
9
Chapitre : Les Listes Chaînées
6 Suppression d’un élément
Avant d’entreprendre l’opération de suppression proprement dite, il
faudrait localiser l’élément qui précède celui qui va être supprimé car
cet élément qui va être modifié.
Pour cela et pour effectuer cette opération, il faudrait utiliser deux
pointeurs : un pointeur courant qui va pointer sur l’élément à
supprimer et un pointeur précèdent qui va pointer sur l’élément qui le
précède.
Les étapes à suivre sont donc :
✔ définition d'un pointeur courant et d’un pointeur précèdent
Liste Courant=tete;
Liste Precedent=tete;
✔ parcours de la liste jusqu'à ce qu’on trouve l’élément à supprimer
while (Courant != NULL && Courant->valeur != Val)
{
Precedent = Courant;
Courant = Courant->Suivant;
}
✔ se débarrasser du maillon pointé par le pointeur courant et
ensuite le libérer
Precedent->Suivant = Courant->Suivant;
free(Courant);
10
