Les listes chaînées en langage C

Emmanuel Delahaye

Cet article présente les listes chaînées qui constituent une alternative intéressante aux tableaux.

Votre avis et vos suggestions sur cet article nous intéressent !

Alors après votre lecture, n'hésitez pas : Commentez ♪

- Titre : Les listes chaînées en langage C

- Auteur : Emmanuel Delahaye

- Parution : 28 janvier 2008

- Mise à jour : 7 mars 2013

- Licence : Copyright ® 2008 Emmanuel Delahaye. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

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

- II-A. Implémentation avec structure

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

II - 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 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;
}

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

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

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.

Il est aussi évidemment possible de rendre la structure opaque (voir l'article les types abstraits de données)

/* 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;
};