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 :

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

Une liste sera désignée à l'aide d'un pointeur de list_cell, via le type list ; 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, ce qui peut être fait par la fonction suivante :

bool is_empty_list(list l) {
  return (l == NULL);
}

Le constructeur de liste est la fonction

list list_cons(const data& d, list l) {
  list c = new list_cell;
  
  c->label = d;
  c->next = l;
  return c;                                  
}

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

  list p = list_cons(2, list_cons(1, list_cons(0, NULL)));

Comme pour les arbres, des fonctions list_clone et list_delete 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é :

struct data {
  string key;
  ... info;
};

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 search(const string& s, list l) {
  list c;
  
  for (c = l; !is_empty_list(c); c = c->next) {
    if (s == c->key) {
      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 search_rec(const string& s, list l) {

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

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