Aller au contenu

TD N°3 : Les listes chaînées

Listes chaînées en C Les listes chaînées en C sont une structure de données dynamique qui permet de gérer des collections d'éléments de manière efficace. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de connaître leur taille à l'avance et permettent d'ajouter ou de supprimer des éléments sans avoir à réallouer de la mémoire pour l'ensemble de la structure.

D'après le document TD N°3 : Les listes chaînées

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

TD N°3 : Les listes chaînées

Programming in C · PDF · 9 pages · 2011

Afficher l'aperçu du document

Consulter le document original →

Listes chaînées en C

Les listes chaînées en C sont une structure de données dynamique qui permet de gérer des collections d'éléments de manière efficace. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de connaître leur taille à l'avance et permettent d'ajouter ou de supprimer des éléments sans avoir à réallouer de la mémoire pour l'ensemble de la structure. Cet article vous guidera à travers la déclaration, l'ajout, la suppression et la recherche d'éléments dans une liste chaînée en C, avec des exemples de code.

Généralités sur les listes chaînées

Une liste chaînée est composée d'éléments qui sont reliés entre eux par des pointeurs. Chaque élément contient deux parties : la valeur à stocker et l'adresse de l'élément suivant. Si un élément est le dernier de la liste, son adresse suivante sera NULL, indiquant la fin de la chaîne. Voici quelques différences clés entre les tableaux et les listes chaînées :

  • Dans un tableau, la taille est fixe et connue, tandis que dans une liste chaînée, la taille peut varier.
  • Les éléments d'un tableau sont stockés de manière contiguë en mémoire, alors que les éléments d'une liste chaînée peuvent être dispersés.
  • Pour ajouter ou supprimer un élément dans un tableau, il faut souvent créer un nouveau tableau, tandis que dans une liste chaînée, il suffit de manipuler les pointeurs.

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

Pour déclarer une liste chaînée en C, vous devez définir une structure qui représente un élément de la liste. Voici un exemple de déclaration d'une liste simplement chaînée d'entiers :

#include <stdlib.h>

typedef struct element element;
struct element
{
    int val;
    struct element *nxt;
};

typedef element* llist;

int main()
{
    llist ma_liste1 = NULL;
    element *ma_liste2 = NULL;
    struct element *ma_liste3 = NULL;

    return 0;
}

Il est essentiel d'initialiser la liste chaînée à NULL pour éviter des comportements indésirables lors de l'ajout d'éléments.

Manipulation des listes chaînées

Une fois la liste chaînée déclarée, vous pouvez commencer à manipuler ses éléments. Voici les opérations de base que vous pouvez effectuer :

Ajouter un élément

Il existe deux manières d'ajouter un élément à une liste chaînée : en tête ou en fin de liste.

Ajouter en tête

Pour ajouter un élément en tête, vous créez un nouvel élément, lui assignez une valeur, puis le reliez à la liste existante :

llist ajouterEnTete(llist liste, int valeur)
{
    element* nouvelElement = malloc(sizeof(element));
    nouvelElement->val = valeur;
    nouvelElement->nxt = liste;
    return nouvelElement;
}

Ajouter en fin de liste

Pour ajouter un élément en fin de liste, vous devez parcourir la liste jusqu'au dernier élément et y relier le nouvel élément :

llist ajouterEnFin(llist liste, int valeur)
{
    element* nouvelElement = malloc(sizeof(element));
    nouvelElement->val = valeur;
    nouvelElement->nxt = NULL;

    if(liste == NULL)
    {
        return nouvelElement;
    }
    else
    {
        element* temp = liste;
        while(temp->nxt != NULL)
        {
            temp = temp->nxt;
        }
        temp->nxt = nouvelElement;
        return liste;
    }
}

Supprimer un élément

La suppression d'un élément peut également se faire en tête ou en fin de liste.

Supprimer un élément en tête

Pour supprimer le premier élément, vous devez stocker l'adresse du second élément avant de libérer le premier :

llist supprimerElementEnTete(llist liste)
{
    if(liste != NULL)
    {
        element* aRenvoyer = liste->nxt;
        free(liste);
        return aRenvoyer;
    }
    else
       return NULL;
}

Supprimer un élément en fin de liste

Pour supprimer le dernier élément, parcourez la liste jusqu'à l'avant-dernier élément et mettez à jour son pointeur :

llist supprimerElementEnFin(llist liste)
{
    if(liste == NULL)
        return NULL;

    if(liste->nxt == NULL)
    {
        free(liste);
        return NULL;
    }

    element* tmp = liste;
    element* ptmp = liste;

    while(tmp->nxt != NULL)
    {
        ptmp = tmp;
        tmp = tmp->nxt;
    }

    ptmp->nxt = NULL;
    free(tmp);
    return liste;
}

Rechercher un élément

Pour rechercher un élément ayant une certaine valeur, parcourez la liste et renvoyez l'adresse du premier élément trouvé :

llist rechercherElement(llist liste, int valeur)
{
    element *tmp = liste;
    while(tmp != NULL)
    {
        if(tmp->val == valeur)
        {
            return tmp;
        }
        tmp = tmp->nxt;
    }
    return NULL;
}

Points clés à retenir

Voici les points essentiels à retenir sur les listes chaînées :

  • Les listes chaînées permettent une gestion dynamique de la mémoire.
  • Chaque élément contient une valeur et un pointeur vers l'élément suivant.
  • Les opérations d'ajout et de suppression sont plus flexibles que dans les tableaux.
  • Il est crucial d'initialiser la liste à NULL lors de sa déclaration.

Questions fréquentes

Comment déclarer une liste chaînée en C ?

Pour déclarer une liste chaînée en C, vous devez définir une structure contenant la valeur et un pointeur vers l'élément suivant. Ensuite, vous créez un type de pointeur pour faciliter la manipulation de la liste.

Comment ajouter un élément à une liste chaînée ?

Vous pouvez ajouter un élément en tête ou en fin de liste. Pour cela, créez un nouvel élément, assignez-lui une valeur, et reliez-le à la liste existante.

Comment supprimer un élément d'une liste chaînée ?

Pour supprimer un élément, vous devez gérer les pointeurs correctement pour ne pas perdre l'accès aux autres éléments. Cela peut se faire en tête ou en fin de liste.

Comment rechercher un élément dans une liste chaînée ?

Pour rechercher un élément, parcourez la liste jusqu'à trouver l'élément avec la valeur recherchée et renvoyez son adresse.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions