Ajouter un élément dans une liste chaînée en langage C

Les listes chaînées sont des structures de données dynamiques offrant une gestion très flexible des éléments, contrairement aux tableaux à taille fixe. Elles permettent d’ajouter et de supprimer des éléments facilement, sans avoir besoin de déplacer ou réallouer toute la structure. En langage C, les listes chaînées sont couramment utilisées pour gérer des collections évolutives et faciliter les opérations d’insertion et de suppression.

Comprendre les listes chaînées

Une liste chaînée est un assemblage de structures (noeuds) liées entre elles par des pointeurs. Chaque élément de la liste contient deux parties :

La donnée : ce que vous souhaitez stocker (un entier, un caractère, ou une structure plus complexe).
Un pointeur vers l'élément suivant : il relie les éléments entre eux, formant une chaîne déroulante jusqu'à la fin de la liste.

Le dernier élément de la liste pointe vers NULL, indiquant la fin de la chaîne.

Contrairement aux tableaux où les éléments sont stockés de manière contiguë, dans une liste chaînée les éléments peuvent être dispersés en mémoire, mais sont reliés par des pointeurs. Cela permet d’ajouter ou d’enlever des éléments sans nécessité de déplacer toute la structure.

Différences entre tableaux et listes chaînées

Tableaux : Taille fixe connue à la déclaration. Accès direct à un élément via son indice. Modification (ajout/suppression au milieu) nécessitant souvent une réallocation mémoire.
Listes chaînées : Taille dynamique inconnue au départ, peuvent croître ou rétrécir selon les besoins. Pas d’accès direct à un élément donné, on doit parcourir la liste à partir du début.

Déclaration d'une liste chaînée en C

Une liste chaînée s’appuie sur une structure C contenant la donnée et un pointeur vers le suivant :

typedef struct element { int val; // donnée (exemple entier) struct element *nxt; // pointeur vers l'élément suivant} element;typedef element* llist; // pointeur vers le début de la liste

Pour gérer cette liste, on utilise un pointeur llist initialisé à NULL représentant une liste vide, puis on alloue dynamiquement chaque noeud.

Ajouter un élément dans une liste chaînée

L’insertion d’éléments dans une liste chaînée peut se faire :

En tête (au début) de la liste
En fin de liste
Au milieu, après un noeud donné

Ajouter en tête

C’est l'insertion la plus simple. On alloue un nouvel élément, on lui assigne la valeur désirée, puis on le relie au début de la liste existante :

element* ajouterEnTete(element* liste, int val) { element* nouv = malloc(sizeof(element)); if (!nouv) exit(EXIT_FAILURE); nouv->val = val; nouv->nxt = liste; // le nouvel élément pointe vers l'ancien premier return nouv; // le nouvel élément devient la tête de la liste}

Si la liste était vide (NULL), la nouvelle tête pointe alors vers NULL.

Ajouter en fin de liste

L'insertion en fin nécessite de parcourir la liste pour trouver le dernier élément (celui dont nxt == NULL), puis de lier ce dernier au nouvel élément qui pointera à NULL :

Lire aussi: INPI et Micro-Entreprise : Démarches

element* ajouterEnFin(element* liste, int val) { element* nouv = malloc(sizeof(element)); if (!nouv) exit(EXIT_FAILURE); nouv->val = val; nouv->nxt = NULL; if (liste == NULL) { return nouv; // liste vide : nouvel élément devient la tête } element* temp = liste; while (temp->nxt != NULL) { temp = temp->nxt; } temp->nxt = nouv; // ajout en fin return liste; // la tête ne change pas}

Ajouter au milieu

Pour insérer un élément au milieu, il faut :

Parcourir la liste jusqu’au noeud après lequel insérer.
Créer le nouvel élément.
Changer les pointeurs pour insérer correctement ce nouvel élément.

Le code est similaire, mais nécessite un pointeur vers le noeud précédent :

void ajouterAuMilieu(element* precedent, int val) { if (precedent == NULL) return; element* nouv = malloc(sizeof(element)); if (!nouv) exit(EXIT_FAILURE); nouv->val = val; nouv->nxt = precedent->nxt; // le nouvel élément pointe sur l'ancien suivant precedent->nxt = nouv; // on relie l'élément précédent au nouveau}

Supprimer un élément dans une liste chaînée

La suppression demande de modifier les pointeurs pour « sauter » l’élément à supprimer et de libérer la mémoire :

Supprimer en tête :

element* supprimerPremier(element* liste) { if (liste == NULL) return NULL; element* temp = liste->nxt; free(liste); return temp; // nouvelle tête}

Supprimer au milieu ou fin :

element* supprimerApres(element* precedent) { if (precedent == NULL || precedent->nxt == NULL) return NULL; element* aSupprimer = precedent->nxt; precedent->nxt = aSupprimer->nxt; free(aSupprimer); return precedent->nxt;}

Le cas particulier de supprimer un élément donné nécessite de parcourir la liste pour trouver le noeud avant le noeud ciblé.

Parcourir et afficher une liste chaînée

Pour afficher les données d’une liste chaînée, on parcourt la liste avec un pointeur temporaire et on affiche chaque élément :

Lire aussi: Comment Calculer la TVA ?

void afficherListe(element* liste) { element* temp = liste; while (temp != NULL) { printf("%d -> ", temp->val); temp = temp->nxt; } printf("NULL\n");}

Fonctions complémentaires

Tester si la liste est vide :

int estVide(element* liste) { return (liste == NULL);}

Compter le nombre d’éléments :

int tailleListe(element* liste) { int compteur = 0; element* temp = liste; while (temp != NULL) { compteur++; temp = temp->nxt; } return compteur;}

Rechercher un élément par valeur :

element* rechercher(element* liste, int val) { element* temp = liste; while (temp != NULL) { if (temp->val == val) return temp; temp = temp->nxt; } return NULL;}

Avantages et limites des listes chaînées

Les listes chaînées offrent une flexibilité remarquable pour des opérations dynamiques :

Insertion et suppression facilités sans réallocations massives.
Pas besoin de connaître la taille initiale.
Permettent de manipuler des structures complexes.

Cependant, elles présentent aussi quelques inconvénients :

Accès séquentiel lent : pas d’accès direct par indice.
Consommation mémoire supplémentaire liée aux pointeurs.

Structures de contrôle et pratiques avancées

Pour simplifier la gestion des listes, on peut créer une structure de contrôle qui contient l’adresse du premier élément :

typedef struct Liste { element* premier;} Liste;

Cette structure permettra d’encapsuler la liste et de gérer plus facilement ses opérations (ajout, suppression, affichage, libération mémoire).

Exemple complet : création, ajout, affichage et suppression

#include <stdio.h>#include <stdlib.h>typedef struct element { int val; struct element* nxt;} element;element* ajouterEnTete(element* liste, int val) { element* nouv = malloc(sizeof(element)); if (!nouv) exit(EXIT_FAILURE); nouv->val = val; nouv->nxt = liste; return nouv;}void afficherListe(element* liste) { element* temp = liste; while (temp != NULL) { printf("%d -> ", temp->val); temp = temp->nxt; } printf("NULL\n");}element* supprimerPremier(element* liste) { if (liste == NULL) return NULL; element* temp = liste->nxt; free(liste); return temp;}int main(void) { element* liste = NULL; liste = ajouterEnTete(liste, 10); liste = ajouterEnTete(liste, 20); liste = ajouterEnTete(liste, 30); afficherListe(liste); // Affiche 30 -> 20 -> 10 -> NULL liste = supprimerPremier(liste); afficherListe(liste); // Affiche 20 -> 10 -> NULL // Libération de la mémoire restante while (liste != NULL) { liste = supprimerPremier(liste); } return 0;}

Qu'est ce qu'une Liste chaînée

Exercices proposés pour approfondir

Écrire une fonction qui insère un élément à une position donnée dans la liste.
Écrire une fonction qui supprime un élément donné dans la liste (par valeur ou par position).
Écrire une fonction qui efface complètement la liste en libérant toute la mémoire allouée.
Écrire une fonction pour compter le nombre d'occurrences d'une valeur donnée.
Écrire une fonction récursive pour calculer la taille de la liste ou pour supprimer tous les éléments d'une certaine valeur.

Extensions possibles

Après avoir maîtrisé les listes simplement chaînées, vous pouvez explorer :

Les listes doublement chaînées : chaque élément possède deux pointeurs, vers l’élément suivant et vers l’élément précédent, ce qui facilite le parcours dans les deux sens et la suppression en fin de liste.
Les listes triées : insertion automatique des éléments dans l’ordre croissant/décroissant.
Les piles et files : implémentées par des listes chaînées avec des règles spécifiques d’insertion et suppression (LIFO, FIFO).

Conclusion

Programmer une liste chaînée en C est un excellent exercice pour approfondir votre connaissance des pointeurs et de la gestion dynamique de mémoire. Vous gagnez en compréhension de structures de données fondamentales, ce qui est essentiel pour tout développeur C travaillant sur des applications nécessitant une gestion évolutive et efficace des données.

Ce tutoriel vous a permis de découvrir les concepts clés, comment déclarer une liste, ajouter, supprimer et parcourir les éléments, ainsi que les différences majeures avec les tableaux. Poursuivez avec les exercices et les variantes plus avancées pour maîtriser parfaitement les listes chaînées.

balises: