1 Introduction

Lorsque l’on manipule plusieurs objets (éléments) en mémoire on peut utiliser des tableaux. Seulement lorsque l’on manipule des informations dont le nombre varie pendant l’exécution du programme. Pire, certain élément disparaissent un peu n’importe où.

Dans ces cas on se rend vite compte qu’utiliser des tableaux n’est pas simple et peu même être coûteux. En effet si on ne veut pas allouer des tableaux toujours plus grand que nécessaire, alors il vas falloir ré-allouer et recopier souvent. Les suppressions d’un élément vont entraîner, bien souvent, un déplacement de éléments qui suivent pour combler ce trou.

La liste chaînée est une solution à ces problèmes. C’est quelques chose de très utilisé en informatique depuis pas mal de temps. Alors pourquoi s’embêter, autant utiliser ce qui marche. Le but de cet article est de familiariser une personne qui ne connaît pas les listes chaînées avec cet outils.

2 Chaînage simple

Le principe de la liste chaînée c’est de donner un des éléments qui la compose et l’endroit ou trouve le suivant.

Bon comme cela reste abstrait et que rien ne vaut un exemple, voici un exemple simple. Imaginons 4 entiers (en commençant la numérotation à 0 mais c’est sans importance).

Voila à quoi cela pourrait ressembler avec un tableau :

Avec une liste chaînée on aurai cela :

Déjà on voit bien que cela ne se ressemble pas. Le tableau c’est une adresse en mémoire avec des éléments qui se suivent (nos 4 entiers). La liste chaînée est composée de beaucoup de petits éléments qui ne se suivent pas. Dans un tableau, il suffit d’avoir l’adresse du premier entier pour trouver les autres qui sont directement à la suite. Par exemple, si je cherche l’entier 2, il suffit de rajouter à l’adresse du premier entier la taille de 2 entiers (entier 0 et entier 1). Pour trouver les éléments de la liste chaînée, il faut avoir le pointeur sur le premier entier mais on ne peut pas directement calculer l’adresse de l’entier 2. Pour cela, on garde avec l’entier 0, l’adresse où trouver l’entier 1. Avec l’entier 1, on conserve l’adresse de l’entier 2. Pour trouver une valeur, on fait ce que l’on appelle un parcours de la liste. Généralement, la dernière valeur garde une adresse spécial pour indiquer qu’il n’y plus rien après (pas obligatoire si on connaît le nombre d’élément de la liste, mais comme de toute façon on a une adresse, on la rempli). Cette valeur est souvent NULL (adresse 0) ou l’adresse du premier élément de la liste.

Sur une liste on peut faire des opérations comme :

• Insérer un élément au début
• Insérer un élément à la fin
• Supprimer un élément

Nous allons voir tout cela sur un exemple de programmation en langage C.

/* Pour compiler cette exemple, on peut faire par exemple : */
/* gcc -Wall liste_simple.c -o liste_simple                 */

#include <stdio.h>  /* pour l'utilisation de printf         */
#include <stdlib.h> /* pour l'utilisation de malloc et free */

/* la structure list_item represente un element de la liste */
typedef struct _list_item list_item;

struct _list_item 
  int       val;   /* element que l'on stocke dans la liste   */
  list_item *next; /* adresse du prochain element de la liste */

;

/* permet d'inserer la valeur val au debut de la liste list */
/* renvoie la nouvelle liste cree                           */
list_item *inserer_debut(list_item *list, int val)

 list_item *vlist_item;
  /* on alloue la memoire pour le nouvel element */
  if((vlist_item = (list_item *)malloc(sizeof(list_item))) == NULL)

   perror("malloc failed "); exit(1); 

  /* on recopie la valeur */
  vlist_item->val  = val;
  /* on chaine avec le prochain element de la liste (l'ancien premier) */
  vlist_item->next = list;

  /* on renvoie notre element car c'est maintenant le permier */
  return(vlist_item);


/* permet d'inserer la valeur val a la finde la liste list */
/* renvoie la nouvelle liste cree                          */

list_item *inserer_fin(list_item *list, int val)
 list_item *vlist_item;

  list_item *vlist_move;
  /* on alloue la memoire pour le nouvel element */
  if((vlist_item = (list_item *)malloc(sizeof(list_item))) == NULL)

   perror("malloc failed "); exit(1); 

  /* on recopie la valeur */
  vlist_item->val  = val;
  /* on chaine avec le prochain element de la liste
     (aucun car on est le dernier) */
  vlist_item->next = NULL;

  if(list == NULL)
   /* la liste etait vide, on devient le premier element */

    return(vlist_item);
   else 
    /* on parcour la liste jusqu'au dernier element
       (celui qui pointe sur NULL) */

    for(vlist_move=list;vlist_move->next!=NULL;vlist_move=vlist_move->next);

    /* le dernier element pointe maitenant sur le nouvel element */
    vlist_move->next = vlist_item;
    /* le premier element de la liste n'a pas change */
    return(list);

  


/* permet de supprimer un element dans la liste en */
/* connaissant sa valeur                           */
/* renvoie la nouvelle liste cree                  */
list_item *supprimer(list_item *list, int val)

 list_item *vlist_move;
  list_item *vlist_move_prev;
  list_item *vlist_tmp;

  /* on recherche l'element avec la valeur val dans la liste */
  /* on conserve aussi dans vlist_move_prev l'element qui le */
  /* precende dans la liste.                                 */
  vlist_move_prev = NULL;

  for(vlist_move=list;(vlist_move!=NULL) && (vlist_move->val!=val);

      vlist_move_prev=vlist_move,vlist_move=vlist_move->next);

  if(vlist_move == NULL)

   /* l'element n'existe pas dans la liste   */
    /* on ne peut donc pas le supprimer.      */
    /* on sait cela car NULL indique que l'on */
    /* est alle au dela de la fin de la liste */
    return(list);

   else 
    if(vlist_move_prev == NULL)

     /* pas d'element avant, on etait le permier */
      /* on conserve l'element suivant            */
      vlist_tmp = vlist_move->next;

      /* on libere la memoire de l'element que l'on devait trouver */
      free(vlist_move);
      /* l'element suivant devient le premier de la liste */
      return(vlist_tmp);

     else 
      /* l'element d'avant indique maintenant le suivant          */
      /* de l'element trouve (on cours circuite l'element trouve) */
      vlist_move_prev->next = vlist_move->next;

      /* on libere l'element trouve */
      free(vlist_move);
      /* le premier de la liste n'a pas change */
      return(list);

    
  


/* un petit exemple d'utilisation */
int main(int argc, char **argv)

 list_item *ma_liste;
  list_item *vlist_move;

  /* initialise la liste comme une liste vide (pas d'elements) */

  ma_liste = NULL;

  /* on rajoute la valeur 4 au debut de la liste */
  ma_liste = inserer_debut(ma_liste, 4);

  /* on rajoute la valeur 3 au debut de la liste */
  ma_liste = inserer_debut(ma_liste, 3);
  /* on rajoute la valeur 44 a la fin de la liste */

  ma_liste = inserer_fin(ma_liste, 44);
  /* on rajoute la valeur 5 a la fin de la liste */
  ma_liste = inserer_fin(ma_liste, 5);

  /* on supprime la valeur 44 de la liste */
  ma_liste = supprimer(ma_liste, 44);

  /* on parcours la liste pour en afficher le contenu */
  for(vlist_move=ma_liste;vlist_move!=NULL;vlist_move=vlist_move->next)

  
    printf("valeur %d\n",vlist_move->val);
  

  return(0);

/* A l'execution de ce programme il doit s'afficher : */
/* valeur 3                                           */
/* valeur 4                                           */
/* valeur 5                                           */

Si vous n’avez pas décroché alors vous avez tout compris sur les listes chaînées. Le reste ce n’est que variantes.

Dans notre exemple de liste chaînée la valeur est gardé dans l’élément de la liste. Il arrive souvent que la valeur soit un pointeur. Cela permet de stocker dans la même liste chaînée n’importe quel type de structure puisque l’on peut avoir des pointeur sur n’importe quoi, cela reste toujours un pointeur. Cela oblige à transtyper les pointeurs pour les faire correspondre à des pointeurs sur le type de structure qui nous intéresse. Cela oblige aussi le programmeur qui utilise la liste à s’occuper lui même de l’allocation et de la dé-allocation des structures qu’il place dans la liste si il veut des copies. Nous verrons cela plus en détail avec les listes doublements chaînées.

3 Doublement chaînées

Les listes doublements chaînées sont une extension du chaînage simple. Le principe est simple, un élément de chaîne conserve l’élément suivant mais aussi l’élément précédent. Cela rend la gestion de la liste un peu plus compliqué mais permet de la parcourir dans les deux sens.

Pour l’instant, je vous laisse le code source d’une liste chaînée développé sur ce principe avec toutes les fonctions nécessaires pour travailler convenablement.

• general.c : quelques déclarations standard
• list.h : les fonctions rendues par les listes
• list.c: le code des fonctions qui gèrent les listes

4 Conclusion

Les listes chaînées présentent beaucoup d’avantages, il ne faut donc pas s’en priver. Toutefois, il ne faut pas oublier qu’elles ne sont pas toujours la meilleure solution pour tous les problèmes. Le surplus de place mémoires nécessaires, la fragmentation de la mémoire ainsi que le coût d’accès important pour les accès aléatoires font partis des faiblesses des listes chaînées. C’est pour cela que l’on trouve aussi les tableaux à taille dynamique (ré-allocation et recopie quand cela est nécessaire).

Dans la même optique que les listes, on trouves les arbres. Il s’agit dans ce cas de référencé non pas un seul élément mais plusieurs éléments suivant en utilisant un ordre entre les différents éléments pour pouvoir retrouver les éléments avec un coût logarithmique. Ce n’est pas le sujet de cet article et je ne vais donc pas entrer dans les détails.