Liste chaînée : Déclaration et structure en C

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.

Qu’est-ce qu’une liste chaînée ?

Une liste chaînée est un ensemble de cellules liées entre elles par des pointeurs. Chaque cellule est une structure contenant :

• une ou plusieurs données, comme dans n’importe quelle structure ;
• un pointeur 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.

Déclaration d’une liste chaînée

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.).

Fonctions d’entrée-sortie pour TypeDonnee (float)

void AfficheDonnee(TypeDonnee donnee) {
  printf("%f ", donnee);
}

TypeDonnee SaisieDonnee(void) {
  TypeDonnee donnee;
  scanf("%f", &donnee);
  return donnee;
}

Insertion en tête de liste

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.

Exemple d’insertion en tête

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.

Construction d’une liste chaînée par saisie

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.

Parcours 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("");
}

Insertion en queue de liste

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;
}

Construction d’une liste dans l’ordre de saisie

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.

Libération de mémoire

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.

Exemple d’utilisation

int main(void) {
  TypeCellule *L;
  L = SaisieListeEndroit();
  Affichage(L);
  Liberation(&L);
  return 0;
}

Glossaire des termes clés

• Liste chaînée : structure de données composée de cellules liées par des pointeurs.
• Cellule : élément de la liste contenant des données et un pointeur vers la cellule suivante.
• Pointeur suivant : champ d’une cellule pointant vers la cellule suivante dans la liste.
• Tête de liste : pointeur vers la première cellule de la liste.
• Insertion en tête : ajout d’une cellule au début de la liste.
• Insertion en queue : ajout d’une cellule à la fin de la liste.
• Parcours de liste : action de visiter chaque cellule de la liste en suivant les pointeurs.
• Libération de mémoire : destruction des cellules pour éviter les fuites mémoire.
• Code générique : code utilisant un type abstrait (ici TypeDonnee) pour pouvoir être adapté à différents types de données.

Points clés à retenir

• Une liste chaînée est une suite de cellules liées par des pointeurs, terminée par un pointeur NULL.
• La déclaration d’une cellule utilise une structure contenant les données et un pointeur vers la cellule suivante.
• Les insertions peuvent se faire en tête (simple et rapide) ou en queue (plus coûteuse sans optimisation).
• Le parcours de liste s’effectue avec un pointeur auxiliaire qui avance jusqu’à NULL.
• La libération de mémoire doit être soigneusement effectuée cellule par cellule pour éviter les fuites.
• Le passage du pointeur de tête par adresse est nécessaire pour modifier la liste dans certaines fonctions (libération notamment).
• Utiliser un typedef pour le type de données permet de rendre le code réutilisable pour différents types.