Liste chaînée : Déclaration et structure en C
Liste chaînée : Déclaration et structure en C
Programming, Math, etc. · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce matériel couvre les listes chaînées en langage C, destiné aux étudiants en informatique ou en programmation souhaitant comprendre la déclaration, la manipulation et la gestion mémoire de cette structure de données fondamentale. Il présente la définition, la déclaration, les opérations d’insertion, de parcours, ainsi que des fonctions utilitaires et des exercices corrigés pour approfondir la compréhension.
Une liste chaînée est un ensemble de cellules liées entre elles par des pointeurs. Chaque cellule est une structure contenant :
suivant vers la cellule suivante.On accède à la liste par un pointeur L sur la première cellule, puis on parcourt la liste en suivant les pointeurs suivant. Le dernier pointeur vaut NULL, indiquant la fin de la liste.
Pour créer une liste chaînée, on déclare une nouvelle structure représentant une cellule. Par exemple, pour une liste de flottants :
typedef float TypeDonnee;
typedef struct Cell {
TypeDonnee donnee; /* données stockées */
struct Cell *suivant; /* pointeur vers la cellule suivante */
} TypeCellule;
TypeCellule *L; /* pointeur sur la tête de liste (NULL si liste vide) */
Le pointeur suivant est déclaré avec struct Cell * car le type TypeCellule est en cours de définition. Cette technique permet au compilateur d’accepter la référence récursive.
On utilise un typedef pour TypeDonnee afin de rendre le code générique et adaptable à différents types de données (int, float, structures, etc.).
void AfficheDonnee(TypeDonnee donnee) {
printf("%f ", donnee);
}
TypeDonnee SaisieDonnee(void) {
TypeDonnee donnee;
scanf("%f", &donnee);
return donnee;
}
La fonction suivante insère une donnée en tête de liste et retourne la nouvelle tête :
TypeCellule* InsereEnTete(TypeCellule *ancienL, TypeDonnee donnee) {
TypeCellule *nouveauL;
nouveauL = (TypeCellule*)malloc(sizeof(TypeCellule));
nouveauL->donnee = donnee;
nouveauL->suivant = ancienL;
return nouveauL;
}
On utilise -> pour accéder aux champs d’un pointeur sur structure, et . pour une variable structure.
Si la liste initiale est L pointant sur la cellule contenant 1.0, après L = InsereEnTete(L, 2.0);, la nouvelle tête contient 2.0 et pointe vers l’ancienne liste.
La fonction suivante construit une liste par insertions successives en tête, à partir de la saisie utilisateur :
TypeCellule* SaisieListeEnvers() {
char choix;
TypeDonnee donnee;
TypeCellule *L = NULL; /* liste vide */
puts("Voulez-vous entrer une liste non vide ?");
choix = getchar();
getchar();
while (choix == 'o') {
puts("Entrez une donnée");
donnee = SaisieDonnee();
getchar();
L = InsereEnTete(L, donnee);
puts("Voulez-vous continuer ?");
choix = getchar();
getchar();
}
return L;
}
Remarque : la liste obtenue est inversée par rapport à l’ordre de saisie car on insère en tête. Pour conserver l’ordre, il faut insérer en queue de liste.
Pour parcourir une liste chaînée, on utilise un pointeur auxiliaire p initialisé à la tête. On avance avec p = p->suivant jusqu’à ce que p == NULL.
void Affichage(TypeCellule* L) {
TypeCellule *p = L;
while (p != NULL) {
AfficheDonnee(p->donnee);
p = p->suivant;
}
puts("");
}
On peut aussi utiliser une boucle for :
void AffichageBis(TypeCellule* L) {
TypeCellule *p;
for (p = L; p != NULL; p = p->suivant)
AfficheDonnee(p->donnee);
puts("");
}
Pour insérer une cellule en queue, il faut parcourir la liste pour trouver la dernière cellule, puis chaîner la nouvelle cellule :
TypeCellule *InsereEnQueue(TypeCellule *L, TypeDonnee donnee) {
TypeCellule *p, *nouveau;
nouveau = (TypeCellule*)malloc(sizeof(TypeCellule));
nouveau->donnee = donnee;
nouveau->suivant = NULL;
if (L == NULL)
L = nouveau;
else {
for (p = L; p->suivant != NULL; p = p->suivant) {}
p->suivant = nouveau;
}
return L;
}
TypeCellule* SaisieListeEndroit() {
char choix;
TypeDonnee donnee;
TypeCellule *L = NULL;
puts("Voulez-vous entrer une liste non vide ?");
choix = getchar();
getchar();
while (choix == 'o') {
puts("Entrez une donnée");
donnee = SaisieDonnee();
getchar();
L = InsereEnQueue(L, donnee);
puts("Voulez-vous continuer ?");
choix = getchar();
getchar();
}
return L;
}
Note : cette méthode a une complexité quadratique O(n²) car chaque insertion en queue nécessite un parcours. On peut optimiser en maintenant un pointeur sur la dernière cellule.
Pour libérer la mémoire d’une liste chaînée, il faut libérer chaque cellule avec free. La fonction suivante détruit la liste et réinitialise la tête à NULL :
void Liberation(TypeCellule **pL) {
TypeCellule *p;
while (*pL != NULL) {
p = *pL;
*pL = (*pL)->suivant;
free(p);
}
*pL = NULL;
}
Le pointeur est passé par adresse (TypeCellule **pL) pour permettre la modification de la tête de liste.
int main(void) {
TypeCellule *L;
L = SaisieListeEndroit();
Affichage(L);
Liberation(&L);
return 0;
}
TypeDonnee) pour pouvoir être adapté à différents types de données.NULL.NULL.