Les listes chaînées en langage C

Les listes chaînées constituent une alternative intéressante aux tableaux. En dehors du fait qu'elles sont souples par nature, elles permettent d'insérer et de supprimer facilement un élément. Par contre, le parcours est séquentiel (mais rien n'empêche de gérer un 'index', c'est-à-dire un tableau de pointeurs, séparément).

Le principe est très simple. Il suffit de définir dans l'élément un champ 'pointeur sur le suivant' qui contient l'adresse de l'élément suivant. Il suffit alors de connaître le début de la liste, et on peut alors la parcourir séquentiellement en allant chercher l'élément suivant, jusqu'au dernier qui pointe sur NULL (fin de liste).

On commence par définir un 'maillon' ou nœud' (node) :

struct node
{
   /* données */
   int x;

   /* chainage */
   struct node *p_next;
};

Ensuite, on définit le pointeur de tête. Il a le même type qu'un maillon et il contient soit NULL (chaîne vide), soit l'adresse du premier nœud :

int main (void)
{
   struct node *p_head = NULL;

   return 0;
}

Ensuite, on crée une fonction qui permet, par exemple, d'ajouter en fin de liste. Pour ça, on distingue le cas de la liste vide et les autres cas. Si la liste est vide, on retourne simplement l'adresse du nouveau nœud qui est par définition, le premier, sinon, on cherche le dernier nœud existant et on y 'accroche' le nouveau.

struct node *add_end (struct node *p_head, int value)
{
   /* allocation du nœud */
   struct node *p_new = malloc (sizeof *p_new);

   /* si tout s'est bien passé : */
   if (p_new != NULL)
   {
      /* mise a jour des champs : */

      /* données */
      p_new->x = value;

      /* chainage par défaut */
      p_new->p_next = NULL;

      /* chainage */
      if (p_head == NULL)
      {
         /* c'est le premier : */
         p_head = p_new;
      }
      else
      {
         /* on cherche le dernier nœud */
         struct node *p = p_head;

         while (p->p_next != NULL)
         {
            /* pointer sur le suivant */
            p = p->p_next;
         }

         /* modification du chainage */
         p->p_next = p_new;
      }
   }
   return p_head;
}

Afin de pouvoir tout de suite vérifier si tout s'est bien passé, on définit dans la foulée, une fonction de visualisation de la liste chaînée :

void display (struct node *p_head)
{
   struct node *p = p_head;

   while (p != NULL)
   {
      /* afficher les données courantes */
      printf ("%d > ", p->x);

      /* pointer sur le suivant */
      p = p->p_next;
   }
   /* afficher la fin */
   printf ("NIL\n");
}

Avec ce petit fichier de test :

int main (void)
{
   struct node *p_head = NULL;

   p_head = add_end (p_head, 1);
   p_head = add_end (p_head, 2);
   p_head = add_end (p_head, 3);
   display (p_head);
   return 0;
}

Cela donne :

1 > 2 > 3 > NIL

Press ENTER to continue.

Je laisse au lecteur le soin de réaliser la fonction de libération de l'ensemble de la liste, l'ajout d'un nœud en tête (add_top()), l'insertion (insert()), la suppression d'un nœud (suppress()), etc.

II-A. Implémentation avec structure▲

struct list
{
   struct node *p_head;
   struct node *p_tail;
};

void add_end (struct list *p_list, int value);

int main (void)
{
   struct list list = {0};

   add_end (&list, 1);
   add_end (&list, 2);
   add_end (&list, 3);
   display (&list);
   return 0;
}

/* list.h */
typedef struct list list_s;

/* list.c */
#include "list.h"

/* structures privées */

struct node
{
   /* données */
   int x;

   /* chainage */
   struct node *p_next;
};

struct list
{
   struct node *p_head;
   struct node *p_tail;
};