Listes chainees

Introduction

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

Implémentation d'une liste chaînée simple

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 noeud' (node) :

struct node
{
   /* donnees */
   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 noeud :

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

   return 0;
}

Il est primordial que cette valeur soit maintenue à jour et qu'elle ne soit pas perdue.

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 noeud qui est par définition, le premier, sinon, on cherche le dernier noeud existant et on y 'accroche' le nouveau.

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

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

      /* donnees */
      p_new->x = value;

      /* chainage par defaut */
      p_new->p_next = NULL;

      /* chainage */
      if (p_head == NULL)
      {
         /* c'est le premier : */
         p_head = p_new;
      }
      else
      {
         /* on cherche le dernier noeud */
         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;
}

ça 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 noeud en tête (add_top()), l'insertion (insert()), la suppression d'un noeud (suppress()) etc. [1]

Implémentation avec structure.

Afin de simplifier la gestion de la liste, il est possible de regrouper, dans une structure 'liste', les éléments intéressants de celle-ci, comme l'inévitable pointeur sur la tête de liste, mais aussi le pointeur sur la fin de la liste, ce qui permet un ajout en queue très rapide. D'autres informations (nombre d'éléments etc.) peuvent aussi accélérer les traitements.

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

L'interface de la fonction d'ajout à la fin se trouve alors modifiée de la façon suivante :

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

et l'usage s'en trouve simplifié :

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

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

Je laisse au lecteur le soin de réaliser les fonctions list_add_end(), list_display(), list_add_top() selon ce principe.[1]

Il est aussi évidemment possible de rendre la structure opaque (TAD)

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

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

/* structures privees */

struct node
{
   /* donnees */
   int x;

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

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

[1] Vous pouvez poster vos tentatives sur le forum en cas de difficultés.