Geospace

TwitterGitHubRSS

Les listes chainées en C

Publié le 27/06/2017

A Epitech, on m’a souvent posé des questions sur les listes chainées… Pourquoi les utilise t’on ? Comment les construire ? Comment les manipuler et les parcourir ? Je vais essayer de répondre à tout ça ici..

Définition

Une liste chainée est une structure de données formées par des cellules. La cellule (parfois appelée node) contient les informations. Chaque cellule est au moins liée à la cellule suivante. Si chaque cellule est également au moins liée à la précédente, on parle de liste doublement chainée. De plus, si le dernier élément de la liste est relié au premier élément de la même liste, celle ci est circulaire.

On peut voir une liste chainée comme un train. Les wagons sont les cellules, chaque wagon est relié au suivant. Les passagers qui voyagent dans les wagons sont les informations. Etant donné que chaque wagon est également relié au précédent, le train serait une liste doublement chainée. Cependant, la locomotive n’étant pas reliée au dernier wagon, le train n’est pas une liste chainée circulaire.

Pourquoi faire ?

La liste chainée est une structure de données très intéressante car dynamique. Contrairement aux tableaux, la mémoire occupée par une liste chainée va grossir puis rétrécir au fur et à mesure que l’on ajoute et enlève des éléments. Ainsi, il est inutile de connaitre à l’avance la taille (le nombre de cellules) d’une liste chainée lors de sa création. De plus, on peut facilement insérer et retirer des éléments au milieu de la liste.

Imaginons un programme qui demande à l’utilisateur de rentrer des nombres, autant qu’il le souhaite, pour ensuite faire des calculs dessus. On ne peut savoir à l’avance le nombre d’entrées que l’utilisateur va faire, cela dépend seulement de sa bonne volonté. Une liste chainée est alors une bonne solution.

La liste chainée est une solution très propre qui permet d’éviter ce genre de choses :

// De toute façon personne ne va jamais
// rentrer plus de 10000 nombres !
int user_inputs[10000];

Ne jamais faire ça ! C’est très sale, ça prend souvent trop de mémoire et ça segfault. Rien ne dit que le programme sera utilisé par un humain. Envoyer 10000 nombres depuis le shell, c’est facile. D’une manière générale, on ne fait jamais confiance à une entrée utilisateur.

$ python -c 'print "1337 " * 12000 + "1338"' | ./personne_ne_va_jamais_rentrer_10000_nombres
Segmentation fault (core dumped)
$ echo "Triste..."
Triste...

En langage C

Nous allons implémenter des listes simplement chainées classiques en langage C.

Nous avons tout d’abord besoin de créer une cellule. Nous savons que chaque cellule va contenir des informations ainsi qu’un lien vers la cellule suivante. Une cellule contient donc au moins deux choses, ce qui nous ammène à utiliser une structure :

typedef struct node {
  int data;
  node *next;
} node;

Je définie ici une structure node qui contient une variable de type int pour stocker mes données ainsi qu’un pointeur vers une autre structure node. Bien entendu, ce pointeur est le lien vers la cellule suivante.

Le type int peut ici être remplacé par n’importe quel type suffisant pour le stockage de nos données. On parlera plus tard de généricité.

On va ensuite poser une fonction permettant de créer une cellule.

node *getNode(int data) {
  node *new = calloc(1, sizeof(node));
  if (new == NULL)
    return NULL;
  new->next = NULL;

  new->data = data;
  return new;
}

Cette fonction alloue l’espace mémoire nécessaire à notre cellule et renvoie un pointeur vers cette dernière. Il convient de toujours conserver un pointeur vers la première cellule de la liste, appelée tête ou head. Certains développeurs aiment enrober leur liste chainée dans une structure semblable à celle ci :

typedef struct {
  node *head;
  node *tail;
} list;

Sauvegarder la queue de la liste (tail) peut aussi être intéressant pour la parcourir en sens inverse mais cela demande une liste doublement chainée. Voilà un exemple d’utilisation de la fonction getNode() :

node *head = getNode(1337);
head->next = getNode(42);
head->next->next = getNode(69);

Des pointeurs ne sont pas vérifiés pour ne pas alourdir le code. Nous avons ici une liste chainée de trois éléments. Voilà une fonction permettant d’afficher la liste :

void printList(node *head) {
  if (head == NULL)
    return;

  while (head->next != NULL) {
    printf("[%d] --> ", head->data);
    head = head->next;
  }
  printf("[%d]\n", head->data);
}

On parcourt notre liste de manière itérative dans cette fonction mais il est également possible d’utiliser la récursion. Voilà une fonction récursive permettant de libérer l’espace mémoire d’une liste :

void freeList(node *head) {
  if (head == NULL)
    return;

  freeList(head->next);
  free(head);
}

Chaque élément next devient tour à tour le head jusqu’à ce que la fonction rencontre un pointeur nul. Tous les éléments sont alors libérés dans l’ordre inverse. En récursif aussi bien qu’en itératif, on peut voir le pointeur head comme un genre de curseur. On note qu’on travaille ici sur une copie de ce pointeur, le pointeur de tête initialement déclaré n’est jamais modifié (et ne doit normalement jamais l’être).

Testons le code :

➜  listes_chainées valgrind ./a.out
==1059== Memcheck, a memory error detector
==1059== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1059== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==1059== Command: ./a.out
==1059==
[1337] --> [42] --> [69]
==1059==
==1059== HEAP SUMMARY:
==1059==     in use at exit: 0 bytes in 0 blocks
==1059==   total heap usage: 4 allocs, 4 frees, 1,072 bytes allocated
==1059==
==1059== All heap blocks were freed -- no leaks are possible
==1059==
==1059== For counts of detected and suppressed errors, rerun with: -v
==1059== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
➜  listes_chainées

Ca l’air de marcher. On a ici une implémentation classique des listes simplement chainées.

Listes doublement chainées

A partir de là, il est assez facile de passer sur des listes doublement chainées.

On modifie notre structure pour y ajouter un pointeur vers la cellule précédente :

typedef struct node {
  int data;
  struct node *next;
  struct node *prev;
} node;

Puis on modifie la fonction de création de cellule pour qu’elle puisse faire le lien avec la cellule précédente :

node *getNode(node *prev, int data) {
  node *new = calloc(1, sizeof(node));
  if (new == NULL)
    return NULL;
  new->next = NULL;

  new->prev = prev;
  if (prev != NULL)
    prev->next = new;
  new->data = data;
  return new;
}

On vérifie si l’argument prev est différent de NULL car lors de la création de la première cellule, on appelle la fonction ainsi :

node *head = getNode(NULL, 1337);

En effet, le pointeur prev de la tête ainsi que le next de la queue seront toujours à NULL, excepté dans le cas d’une liste circulaire ou ils seront liés.

Enfin, on se fait une fonction pour afficher la liste en partant de la queue :

void printListReverse(node *tail) {
  if (tail == NULL)
    return;

  while (tail->prev != NULL) {
    printf("[%d] --> ", tail->data);
    tail = tail->prev;
  }
  printf("[%d]\n", tail->data);
}

Les listes chainées ne sont en fait que des petits bouts de mémoire reliés entre eux. Nous avons écrit ici quelques fonctions usuelles (on les appelle parfois primitives) mais on peut imaginer faire toute une librairie sur les listes chainées. Attention à toujours bien vérifier ces pointeurs et à ne pas modifier le pointeur de tête.

Généricité

Un des problèmes des listes chainées est que le type de donnée qu’on stocke dans la liste n’est pas générique : il est limité par la définition de la structure. On utilisait jusque là le type int pour le champ data de la structure node. Compliqué d’avoir une cellule avec une chaine de caractères par exemple donc. Heureusement, le void * peut nous aider :

typedef struct node {
  void *data;
  struct node *next;
  struct node *prev;
} node;

void freeList(node *head) {
  if (head == NULL)
    return;

  freeList(head->next);
  free(head->data);
  free(head);
}

node *getNode(node *prev, void *data, unsigned int dataSize) {
  node *new = calloc(1, sizeof(node));
  if (new == NULL)
    return NULL;
  new->next = NULL;

  new->prev = prev;
  if (prev != NULL)
    prev->next = new;
  new->data = calloc(dataSize, sizeof(char));
  if (new->data == NULL) {
    free(new);
    return NULL;
  }
  memcpy(new->data, data, dataSize);
  return new;
}

On voit que notre data est désormais un void *. Nous sommes donc libre d’écrire ce que nous voulons à l’emplacement pointé par data grace à la fonction memcpy() dans getNode(). Attention à bien libérer ce void * dans la fonction freeList() !

Nous avons besoin de connaitre le nombre d’octets (du moins le nombre de sizeof(char)) à écrire d’où l’argument unsigned int dataSize passé à getNode(). La fonction peut ensuite s’appeler ainsi :

  int data1 = 42;
  float data2 = 13.37;
  char *data3 = "Pokemon";

  node *head = getNode(NULL, &data1, sizeof(int));
  head->next = getNode(head, &data2, sizeof(float));
  head->next->next = getNode(head->next, data3,
      strlen(data3) * sizeof(char) + 1);

Le problème est alors de traiter la donnée stockée. En effet, il va tôt ou tard falloir déréférencer le pointeur et donc le caster. Il existe alors beaucoup de solutions, on peut par exemple ajouter à la structure un pointeur vers une des fonctions que l’on va écrire pour chacun des types. C’est une solution assez élégante qui rappelle les méthodes.

// Un exemple de ces fonctions
// Cast en int* à l'intérieur
int printInt(void *data) {
  if (data == NULL)
    return FAILURE;
  printf("%d\n", *(int *)data);
  return SUCCESS;
}

// La fonction pointée est générique,
// elle prend un void *
typedef struct node {
  void *data;
  int (*f)(void *);
  struct node *next;
  struct node *prev;
} node;

// On récupère la fonction "spécialisée" pour le type
// en argument
node *getNode(node *prev, void *data, unsigned int dataSize,
    int (*f)(void *)) {
  node *new = calloc(1, sizeof(node));
  if (new == NULL)
    return (NULL);
  new->next = NULL;

  new->prev = prev;
  if (prev != NULL)
    prev->next = new;
  new->data = calloc(dataSize, sizeof(char));
  memcpy(new->data, data, dataSize);
  new->f = f;
  return new;
}

// Exemple avec un int
int data1 = 42;
node *head = getNode(NULL, &data1, sizeof(int), printInt);
head->f(head->data);

Limites

Les listes chainées ont quelques faiblesses.

La première est qu’elle ne sont pas rapides à parcourir. En effet, il faut parcourir toutes ses cellules précédents pour accéder à une cellule précise de la liste. On peut pallier à ça en sauvegardant des pointeurs à différents endroits de la liste. Lors du parcours de la liste, on choisira le pointeur le plus proche de la cellule recherchée.

Un autre problème propre aux listes génériques est qu’elles sont lentes à la lecture. Une opération de déréférenciation est peu couteuse en ressources mais peut le devenir si on les multiplie. Attention à ne faire des listes génériques que lorsque cela est nécessaire. Bien souvent, le type désiré est connu au moment de l’écriture du code. On peut également très bien instancier plusieurs listes en fonction des type.

Enfin, d’une manière générale, les listes chainées occupent plus de mémoire que des valeurs brutes. En effet, il y a des pointeurs supplémentaires à stocker.

Les listes chainées ne sont donc pas une solution miracle. Si l’optimisation est une contrainte lors de l’écriture du code, il convient de ne les utiliser que si nécessaire.