Structures de données chaînées : les listes

    

Une liste chaînée étiquetée   (en anglais labelled linked list ), appelée désormais liste, est définie récursivement de la façon suivante : une liste est soit vide, soit formée d'une étiquette et d'une liste, appelée son successeur.

Nous utilisons l'allocation dynamique pour implémenter ces listes. De façon analogue aux arbres binaires étiquetés, une liste est implémentée à l'aide d'une structure auto-référencée à deux champs, contenant respectivement une étiquette (objet d'un type data quelconque) et un pointeur de cellules :

typedef struct list_cell {
  data label;
  struct list_cell *next;
} list_cell;

Une liste sera désignée à l'aide d'un pointeur de list_cell ; la liste vide est ainsi représentée par le pointeur NULL. Tout traitement d'une liste doit d'abord tester si elle est vide. Le constructeur de cellule de liste est la fonction

list_cell *list_cons(const data d, list_cell *l) {
  list_cell *c = malloc(sizeof(list_cell));
  
  c->label = d;
  c->next = l;
  return c;                                  
}

  

Figure 29: Une liste chaînée

La liste de la figure 29, le type data étant int, est désignée par le pointeur p défini par :

  list_cell *p = list_cons(2, list_cons(1, list_cons(0, NULL)));

Comme pour les arbres, des fonctions list_clone et list_free de clonage et de libération doivent être programmées.

On suppose maintenant que le type data a la forme suivante, le type du champ info n'étant pas spécifié :

typedef struct {
  char key[L];
  ... info;
} data;

La recherche séquentielle d'une cellule par sa clé dans une liste se fait de façon très classique par une boucle for qui parcourt la liste ; la condition d'exécution, c != NULL, est que la variable c << pointe >> ; l'instruction d'itération remplace un lien par le lien suivant :

list_cell *search(const char s[], list_cell *l) {
  list_cell *c;
  
  for (c = l; c != NULL; c = c->next) {
    if (strcmp(s, c->key) == 0) {
      return c;
    }
  }
  return NULL;
}

Cette fonction retourne la cellule contenant la chaîne recherchée ou bien NULL en cas d'échec. La version récursive de cette recherche est aussi simple :

list_cell *search_rec(const char s[], list_cell *l) {

  if (l == NULL) {
    return NULL;
  } else if (strcmp(s, l->key) == 0) {
    return l;
  } else {
    return search_rec(s, l->next);
  }
}

Nous appliquerons ces listes à une nouvelle méthode de hachage.