Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020

Cours Informatique 2 : Listes chainées 1ère année

Chapitre V : Structures de données complexes

Partie 01 : Les Listes Chainées

 Généralités sur les listes chainées

 Déclaration en C d'une liste chainée
 Manipuler les listes chainées

1. Généralités sur les listes chainées

Lorsqu'on crée un tableau, les éléments de celui-ci sont placés de façon contiguë en mémoire. Pour pouvoir le
créer, il faut connaître sa taille. Si on veut supprimer un élément au milieu du tableau, il nous faut recopier les
éléments temporairement, réallouer de la mémoire pour le tableau, puis le remplir à partir de l'élément
supprimé. En bref, ce sont beaucoup de manipulations coûteuses en ressources.
Une liste chaînée est différente dans le sens où les éléments de notre liste sont répartis dans la mémoire et reliés
entre eux par des pointeurs (chaque élément possède l'adresse de l'élément suivant). On peut ajouter et enlever
des éléments d'une liste chaînée à n'importe quel endroit, à n'importe quel instant, sans devoir recréer la liste
entière.

Nous allons essayer de voir ceci plus en détail sur ces schémas :

19 11 2 35

Tableau d'entiers

19 svt 11 svt 2 svt 35 svt

Liste chainée d'entiers

Nous avons sur ce schéma la représentation que l'on pourrait faire d'un tableau et d'une liste chaînée. Chacune
de ces représentations possède ses avantages et inconvénients. C'est lors de l'écriture de notre programme que
nous devons nous poser la question de savoir laquelle des deux méthodes est la plus intéressante.

 Dans un tableau, la taille est connue, l'adresse du premier élément aussi. Lorsqu'on déclare un tableau, la
variable contiendra l'adresse du premier élément de notre tableau. Comme le stockage est contigu, et la
taille de chacun des éléments est connue, il est possible d'atteindre directement la case i d'un tableau.
 Pour déclarer un tableau, il faut connaître sa taille.

 Pour supprimer ou ajouter un élément à un tableau, il faut créer un nouveau tableau et supprimer
l'ancien
 Dans une liste chaînée, la taille est inconnue au départ, la liste peut avoir autant d'éléments que la
mémoire le permet. Il est en revanche impossible d'accéder directement à l'élément i de la liste chainée.
Pour ce faire, il nous faudra parcourir les i-1 éléments précédents de la liste.
 Pour déclarer une liste chaînée, il suffit de créer le pointeur qui va pointer sur le premier élément de
notre liste chaînée, aucune taille n'est donc à spécifier.

S. Boumediene Page 1
 Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020
Cours Informatique 2 : Listes chainées 1ère année
 Il est possible d'ajouter, de supprimer, d'intervertir des éléments d'une liste chaînée sans avoir à recréer
la liste en entier, mais en manipulant simplement leurs pointeurs.

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 le bout de la chaîne.

Voilà deux schémas pour expliquer comment se passent l'ajout et la suppression d'un élément d'une liste chaînée.
Remarquez le symbole en bout de chaîne qui signifie que l'adresse de l'élément suivant ne pointe sur rien, c'est-à-
dire sur NULL.

Supprimer un élément dans une liste chainée

19 svt 11 svt 2 svt 35 svt

Ajouter un élément dans une liste chainée

19 svt 11 svt 2 svt 35 svt

7 svt

2. Déclaration en C d'une liste chainée

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... Il est même possible de combiner plusieurs types dans une même liste.
Voici la déclaration d'une liste simplement chaînée d'entiers :
Code : C

#include <stdlib.h>
typedef struct element element;
struct element
{
int val;
struct element *suiv;
};

typedef element* lch;

On crée le type element qui est une structure contenant un entier (val) et un pointeur sur élément (suiv), qui
contiendra l'adresse de l'élément suivant. Ensuite, il nous faut créer le type lch (liste chaînée) 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. Afin de pouvoir utiliser la macro
NULL, on doit inclure stdlib.h. Nous avons juste crée le type lch afin de simplifier la déclaration.
Voilà comment déclarer une liste chaînée (vide pour l'instant) :

S. Boumediene Page 2
 Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020
Cours Informatique 2 : Listes chainées 1ère année

Code : C

#include <stdlib.h>

typedef struct element element;

struct element
{
int val;
struct element *suiv;
};

typedef element* lch;

int main(int argc, char **argv)

{
/* Déclarons 3 listes chaînées de façons différentes mais équivalentes */
lch ma_liste1 = NULL;
element *ma_liste2 = NULL;
struct element *ma_liste3 = NULL;

return 0;
}
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. De manière générale, il est plus sage de toujours
initialiser nos pointeurs.

3. Manipuler les listes chainées (1/2)

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, ainsi que de lire ce qu'elle contient. C'est ce que nous allons étudier dans cette
première partie sur la manipulation des listes chaînées. Dans tous les cas (ou presque), nous renverrons la
nouvelle liste, c'est-à-dire un pointeur sur element contenant l'adresse du premier élément de la liste.

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. Nous allons étudier ces deux
moyens d'ajouter un élément à une liste.

Ajouter en tête de liste

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, raccorder cet élément à la liste passée en paramètre. Lors d'un ajout en tête, on devra donc assigner à
suiv l'adresse du premier élément de la liste passé en paramètre. Visualisons tout ceci sur un schéma :

S. Boumediene Page 3
Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020
Cours Informatique 2 : Listes chainées 1ère année
Code :

lch ajouterEnTete(lch liste, int valeur)

{
/* On crée un nouvel élément */
element* nouvelElement = malloc(sizeof(element));

/* On assigne la valeur au nouvel élément */

nouvelElement->val = valeur;

/* On assigne l'adresse de l'élément suivant au nouvel élément */

nouvelElement->suiv = liste;

/* On retourne la nouvelle liste, i.e. le pointeur sur le premier élément */

return nouvelElement;
}

C'est l'ajout le plus simple des deux. Il suffit de créer un nouvel élément puis de le relier au début de la liste
originale. Si l'originale est, (vide) c'est NULL qui sera assigné au champ suiv du nouvel element. La liste contiendra
dans ce cas-là un seul élément.

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 voir 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 suiv.

Ajouter un élément en fin de liste

19 svt 11 svt 2 svt 35 svt

7 svt

Code : C

S. Boumediene Page 4
Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020
Cours Informatique 2 : Listes chainées 1ère année
lch ajouterEnFin(lch liste, int valeur)
{
/* On crée un nouvel élément */
element* nouvelElement = malloc(sizeof(element));

/* On assigne la valeur au nouvel élément */

nouvelElement->val = valeur;

/* On ajoute en fin, donc aucun élément ne va suivre */

nouvelElement->suiv = NULL;

if(liste == NULL)
{
/* Si la liste est videé il suffit de renvoyer l'élément créé */
return nouvelElement;
}
else
{
/* Sinon, on parcourt la liste à l'aide d'un pointeur temporaire et on
indique que le dernier élément de la liste est relié au nouvel élément */
element* temp=liste;
while(temp->suiv != NULL)
{
temp = temp->suiv;
}
temp->suiv = nouvelElement;
return liste;
}
}
Comme vous pouvez le constater, nous nous déplaçons le long de la liste chaînée grâce au pointeur temp. Si
l'élément pointé par temp n'est pas le dernier (temp->suiv != NULL), on avance d'un cran (temp = temp->suiv) en
assignant à temp 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.

Affichage d’une liste

void afficherListe(lch liste)
{
element *tmp = liste;
/* Tant que l'on n'est pas au bout de la liste */
while(tmp != NULL)
{
/* On affiche */
printf("%d ", tmp->val);
/* On avance d'une case */
tmp = tmp->suiv;
}
}

Vérifier si la liste est vide

int estVide(lch liste)
{
if(liste == NULL)
return 1;
else
return 0;
}

S. Boumediene Page 5
Ecole Supérieure des Sciences Appliquées d'Alger 2019/2020
Cours Informatique 2 : Listes chainées 1ère année

Rechercher un élément dans une liste

lch rechercherElement(lch liste, int valeur)
{
element *tmp=liste;
/* Tant que l'on n'est pas au bout de la liste */
while(tmp != NULL)
{
if(tmp->val == valeur)
{
return tmp; /* Si l'élément a la valeur recherchée, on renvoie son adresse*/
}
tmp = tmp->suiv;
} return NULL;
}

Suppression d’une liste

lch effacerListe(lch liste)
{
element* tmp = liste;
element* tmpsuiv;

while(tmp != NULL) /* Tant que l'on n'est pas au bout de la liste */

{ tmpsuiv = tmp->suiv; /* On stocke l'élément suivant pour pouvoir avancer */

/* On efface l'élément courant */
free(tmp) ;
/* On avance d'une case */
tmp = tmpsuiv;
} /* La liste est vide : on retourne NULL */
return NULL;
}

En utilisant la récursivité :
lch effacerListe(lch liste)
{
if(liste == NULL) /* Si la liste est vide, il n'y a rien à effacer, on retourne
une liste vide i.e. NULL */
{
return NULL;
}
Else /* Sinon, on efface le premier élément et on retourne le reste de la liste
{ element *tmp; à effacée */
tmp = liste->suiv;
free(liste);
return effacerListe(tmp);
}
}
int main(int argc, char **argv)
{
lch ma_liste = NULL;
int i;
for(i=1;i<=10;i++)
{
ma_liste = ajouterEnTete(ma_liste, i);
ma_liste = ajouterEnFin(ma_liste, i);
}
afficherListe(ma_liste);
effacerListe(ma_liste);
return 0;
}

S. Boumediene Page 6