Apprenez à programmer en C

Un tableau peut être représenté en mémoire comme ceci :

Le problème des tableaux est qu'ils sont figés. Impossible de les agrandir (à moins d'en créer de nouveaux, plus grands) ; ou d'y insérer une case au milieu (à moins de décaler tous les autres éléments) :

Le langage C ne propose pas d'autre système de stockage de données, mais il est possible de le créer soi-même de toutes pièces. Encore faut-il savoir comment s'y prendre : c'est justement ce que ce chapitre et les suivants vous proposent de découvrir.

On pourrait les représenter comme ceci :

Chaque élément peut contenir ce que l'on veut : un ou plusieurs int, double… En plus de cela, chaque élément possède un pointeur vers l'élément suivant :

Retenez comment les éléments sont agencés entre eux : ils forment une chaîne de pointeurs, d'où le nom de "liste chaînée".

Construisez une liste chaînée

Nous allons essayer de créer une structure qui fonctionne sur le principe que nous venons de découvrir.

Tout ce que nous allons faire ici fait appel à des techniques du langage C que vous connaissez déjà. Il n'y a aucun élément nouveau, nous allons nous contenter de créer nos propres structures et fonctions, et les transformer en un système logique, capable de se réguler tout seul.

Créez la structure de la liste des éléments

Nous allons créer une liste chaînée de nombres entiers.

Chaque élément de la liste aura la structure suivante :

typedef struct Element Element;
struct Element
{
    int nombre;
    Element *suivant;
};

• Une donnée, ici un nombre de type int: on pourrait remplacer cela par n'importe quelle autre donnée (un double, un tableau…). Cela correspond à ce que vous voulez stocker, c'est à vous de l'adapter en fonction des besoins de votre programme.

• Un pointeur vers un élément du même type appelé suivant. C'est ce qui permet de lier les éléments les uns aux autres : chaque élément sait où se trouve l'élément suivant en mémoire. Souvenez-vous : les cases ne sont pas côte à côte en mémoire ; c'est la grosse différence par rapport aux tableaux. Cela offre davantage de souplesse car on peut plus facilement ajouter de nouvelles cases par la suite au besoin.

Créez également la structure de contrôle

En plus de la structure qu'on vient de créer (que l'on dupliquera autant de fois qu'il y a d'éléments), nous allons avoir besoin d'une autre structure pour contrôler l'ensemble de la liste chaînée. Elle aura la forme suivante :

typedef struct Liste Liste;
struct Liste
{
    Element *premier;
};

Cette structure Liste contient un pointeur vers le premier élément de la liste. En effet, il faut conserver l'adresse du premier élément pour savoir où commence la liste. Si on connaît le premier élément, on peut retrouver tous les autres en "sautant" d'élément en élément à l'aide des pointeurs suivant.

Nous n'aurons besoin de créer qu'un seul exemplaire de la structure Liste. Elle permet de contrôler toute la liste :

Retenez le dernier élément de la liste

Il faudra bien arrêter de parcourir la liste à un moment donné.

Il suffit de faire pointer le dernier élément de la liste vers NULL, c'est-à-dire de mettre son pointeur suivant à NULL :

Nous avons créé deux structures qui permettent de gérer une liste chaînée :

1. Element, qui correspond à un élément de la liste et que l'on peut dupliquer autant de fois que nécessaire.

2. Liste, qui contrôle l'ensemble de la liste. Nous n'en aurons besoin qu'en un seul exemplaire.

C'est bien, mais il manque encore l'essentiel : les fonctions qui vont manipuler la liste chaînée. En effet, on ne va pas modifier "à la main" le contenu des structures à chaque fois qu'on en a besoin ! Il vaut mieux passer par des fonctions qui automatisent le travail.

Gérez la liste à l'aide de fonctions

À première vue, on peut dire qu'on aura besoin de fonctions pour :

• initialiser la liste ;

• ajouter un élément ;

• supprimer un élément ;

• afficher le contenu de la liste ;

• supprimer la liste entière.

Initialisez la liste

La fonction d'initialisation est la toute première que l'on doit appeler. Elle crée la structure de contrôle et le premier élément de la liste :

Liste *initialisation()
{
    Liste *liste = malloc(sizeof(*liste));
    Element *element = malloc(sizeof(*element));

    if (liste == NULL || element == NULL)
    {
        exit(EXIT_FAILURE);
    }

    element->nombre = 0;
    element->suivant = NULL;
    liste->premier = element;

    return liste;
}

On commence par créer la structure de contrôle liste.

On alloue dynamiquement la structure de contrôle avec un malloc. La taille à allouer est calculée automatiquement avec sizeof(*liste). L'ordinateur saura qu'il doit allouer l'espace nécessaire au stockage de la structureListe.

On alloue ensuite de la même manière la mémoire nécessaire au stockage du premier élément. On vérifie si les allocations dynamiques ont fonctionné. En cas d'erreur, on arrête immédiatement le programme en faisant appel à exit().

Si tout s'est bien passé, on définit les valeurs de notre premier élément :

• la donnée nombre est mise à 0 par défaut ;

• le pointeur suivant pointe vers NULL car le premier élément de notre liste est aussi le dernier pour le moment. Rappel : le dernier élément doit pointer vers NULL pour signaler qu'il est en fin de liste.

Nous avons créé en mémoire une liste composée d'un seul élément :

Ajoutez un élément

On a le choix. Pour l'instant, je propose de l'ajouter en début de liste parce que c'est simple à comprendre.

Nous devons créer une fonction capable d'insérer un nouvel élément en début de liste. Imaginons un cas où la liste est composée de trois éléments et on souhaite en ajouter un nouveau au début :

Il va falloir adapter le pointeur premier de la liste ainsi que le pointeur suivant de notre nouvel élément pour "insérer" correctement celui-ci dans la liste :

void insertion(Liste *liste, int nvNombre)
{
    /* Création du nouvel élément */
    Element *nouveau = malloc(sizeof(*nouveau));
    if (liste == NULL || nouveau == NULL)
    {
        exit(EXIT_FAILURE);
    }
    nouveau->nombre = nvNombre;

    /* Insertion de l'élément au début de la liste */
    nouveau->suivant = liste->premier;
    liste->premier = nouveau;
}

La fonction insertion() prend en paramètres :

• l'élément de contrôle liste(qui contient l'adresse du premier élément) ;

• et le nombre à stocker dans le nouvel élément que l'on va créer.

Dans un premier temps, on alloue l'espace nécessaire au stockage du nouvel élément et on y place le nouveau nombre nvNombre. Il reste alors une étape délicate : l'insertion du nouvel élément dans la liste chaînée.

Nous avons ici choisi pour simplifier d'insérer l'élément en début de liste. Pour mettre à jour correctement les pointeurs, nous devons procéder dans cet ordre précis :

1. Faire pointer notre nouvel élément vers son futur successeur, qui est l'actuel premier élément de la liste.

2. Faire pointer le pointeur premier vers notre nouvel élément.

Cela aura pour effet d'insérer correctement notre nouvel élément dans la liste chaînée :

Supprimez un élément

La suppression ne pose pas de difficulté supplémentaire. Il faut cependant adapter les pointeurs de la liste dans le bon ordre pour ne perdre aucune information :

void suppression(Liste *liste)
{
    if (liste == NULL)
    {
        exit(EXIT_FAILURE);
    }

    if (liste->premier != NULL)
    {
        Element *aSupprimer = liste->premier;
        liste->premier = liste->premier->suivant;
        free(aSupprimer);
    }
}

1. On vérifie que le pointeur qu'on nous envoie n'est pas NULL, sinon on ne peut pas travailler.

2. On vérifie ensuite qu'il y a au moins un élément dans la liste, sinon il n'y a rien à faire.

3. Ces vérifications effectuées, on peut sauvegarder l'adresse de l'élément à supprimer dans un pointeur aSupprimer.

4. On adapte ensuite le pointeur premier vers le nouveau premier élément, qui est actuellement en seconde position de la liste chaînée.

5. On supprime l'élément correspondant à notre pointeur aSupprimer avec un free :

Affichez la liste chaînée

Il suffit de partir du premier élément et d'afficher chaque élément un à un en "sautant" de bloc en bloc :

void afficherListe(Liste *liste)
{
    if (liste == NULL)
    {
        exit(EXIT_FAILURE);
    }

    Element *actuel = liste->premier;

    while (actuel != NULL)
    {
        printf("%d -> ", actuel->nombre);
        actuel = actuel->suivant;
    }
    printf("NULL\n");
}

1. On part du premier élément et on affiche le contenu de chaque élément de la liste (un nombre).

2. On se sert du pointeur suivant pour passer à l'élément qui suit à chaque fois.

On peut tester la création de notre liste chaînée et son affichage avec un main:

int main()
{
    Liste *maListe = initialisation();

    insertion(maListe, 4);
    insertion(maListe, 8);
    insertion(maListe, 15);
    suppression(maListe);

    afficherListe(maListe);

    return 0;
}

En plus du premier élément (que l'on a laissé ici à 0), on en ajoute trois nouveaux à cette liste. Puis on en supprime un.

Au final, le contenu de la liste chaînée sera donc :

8 -> 4 -> 0 -> NULL

À vous de jouer

Nous venons de faire le tour des principales fonctions nécessaires à la gestion d'une liste chaînée. Voici d'autres fonctions que je vous invite à écrire, ce sera un très bon exercice !

• Insertion d'un élément en milieu de liste : si on veut pouvoir ajouter un élément au milieu, il faut créer une fonction spécifique qui prend un paramètre supplémentaire : l'adresse de celui qui précèdera notre nouvel élément dans la liste. Votre fonction va parcourir la liste chaînée jusqu'à tomber sur l'élément indiqué. Elle y insèrera le petit nouveau juste après.

• Suppression d'un élément en milieu de liste : le principe est le même que pour l'insertion en milieu de liste. Cette fois, vous devez ajouter en paramètre l'adresse de l'élément à supprimer.

• Destruction de la liste : il suffit de supprimer tous les éléments un à un !

• Taille de la liste : cette fonction indique combien il y a d'éléments dans votre liste chaînée. L'idéal, plutôt que d'avoir à calculer cette valeur à chaque fois, serait de maintenir à jour un entier nbElements dans la structureListe. Il suffit d'incrémenter ce nombre à chaque fois qu'on ajoute un élément, et de le décrémenter quand on en supprime un.

En résumé

• Les listes chaînées constituent un nouveau moyen de stocker des données en mémoire. Elles sont plus flexibles que les tableaux car on peut ajouter et supprimer des « cases » à n'importe quel moment.

• Il n'existe pas en langage C de système de gestion de listes chaînées, il faut l'écrire nous-mêmes ! C'est un excellent moyen de progresser en algorithmique et en programmation en général.

• Dans une liste chaînée, chaque élément est une structure qui contient l'adresse de l'élément suivant.

• Il est conseillé de créer une structure de contrôle (du type Liste dans notre cas) qui retient l'adresse du premier élément.

• Il existe une version améliorée – mais plus complexe – des listes chaînées appelée « listes doublement chaînées », dans lesquelles chaque élément possède en plus l'adresse de celui qui le précède.

Vous en savez maintenant un peu plus sur ce que sont les listes chaînées. Dans le prochain chapitre, nous allons voir deux variantes de listes chaînées. Rendez-vous dans le prochain chapitre pour voir les piles et les files.