Cours sur les Structures de Données

Dans un tableau, la relation successeur est implicite, elle découle de la contiguïté des composantes. Dans une liste chaînée, au contraire, la relation successeur est explicite : à chaque élément est accolée une information supplémentaire qui renvoie à son successeur, lequel n'a donc pas besoin d'être contigu, ni même voisin.

La notion de liste chaînée n'est pas liée à une manière concrète de matérialiser la relation successeur. Cependant, si le langage utilisé le permet, on choisit généralement d'associer deux principes :

• les éléments sont référencés par leurs adresses dans la mémoire ;
• chaque élément est alloué dynamiquement, au moment où il commence à être utile.

Ce qui, en C, donne les déclarations :

typedef ... OBJET; /* dépend du problème particulier considéré */
typedef struct maillon {
    OBJET info;
    struct maillon *suiv;
} MAILLON, *POINTEUR;
POINTEUR premier;

À retenir, trois points clés des listes chaînées :

• chaque élément de la liste est formé de n+1 champs :

  • n champs constituant l'information portée par le maillon, dépendante du problème particulier considéré,
  • un champ supplémentaire qui est la matérialisation de la relation successeur ;
• le dernier élément est signalé par une valeur conventionnelle du champ successeur (ex. : NULL) ;
• on accède à la liste par l'adresse de son premier élément.

À titre de modèle, examinons l'opération la plus fondamentale et fréquente dans le traitement des listes chaînées : la création d'un maillon portant une certaine valeur X et son insertion dans une liste, à la suite d'un maillon donné.

Supposons que p ait pour valeur l'adresse de ce maillon (ne cherchons pas ici à savoir comment p a été déterminé). La séquence à exécuter est :

                                /* état initial: fig. 3 (a) */
q = malloc(sizeof(MAILLON));    /*     résultat: fig. 3 (b) */
q->info = X;                    /*     résultat: fig. 3 (c) */
q->suiv = p->suiv;              /*     résultat: fig. 3 (d) */
p->suiv = q;                    /*     résultat: fig. 3 (e) */

Deux opérations se présentent très souvent ensemble : l'allocation dynamique d'une structure pointée (l'appel de malloc) et le remplissage des champs de la structure ainsi créée. Il est clair et pratique de les réunir en une fonction spécifique, une sorte de version personnalisée de malloc :

POINTEUR maillon(OBJET i, POINTEUR s) {
    POINTEUR p = malloc(sizeof(MAILLON));
    assert(p != NULL);
    p->info = i;
    p->suiv = s;
    return p;
}

Cette fonction dépend étroitement de la structure utilisée (ses arguments formels en reproduisent exactement les champs), mais elle est indépendante de l'usage qu'on en fait dans une application. Dans la suite, chaque fois qu'une structure sera déclarée, nous supposerons que nous avons écrit l'allocateur correspondant.

Avec un tel allocateur, les quatre lignes de la page précédente s'écrivent bien plus simplement :

p->suiv = maillon(X, p->suiv);

Cette question se pose au programmeur dans de nombreuses applications. Lorsque le choix est possible, on doit considérer les points suivants.

Avantages des tableaux par rapport aux listes :

• accès indexé « direct ». C'est la définition même des tableaux : l'accès au i^e élément se fait en un temps indépendant de i, alors que dans une liste chaînée ce temps est de la forme k × i (car il faut exécuter i fois l'opération p = p->suiv) ;
• pas de surencombrement. La relation successeur étant implicite (définie par la contiguïté des composantes), il n'y a pas besoin d'espace supplémentaire pour son codage. Alors que dans une liste chaînée l'encombrement de chaque maillon est augmenté de la taille du pointeur suivant(1).

Avantages des listes par rapport aux tableaux :

• efficacité et souplesse dans la définition de la relation successeur. Cette relation étant explicite, on peut la modifier aisément (les maillons des listes chaînées peuvent être réarrangés sans avoir à déplacer les informations portées). Autre aspect de la même propriété : un même maillon peut appartenir à plusieurs listes (cf. § 1.5Application aux matrices creuses (listes orthogonales)) ;
• encombrement total selon le besoin, si on utilise, comme dans les exemples précédents, l'allocation dynamique des maillons. Le nombre de maillons d'une liste correspond au nombre d'éléments effectivement présents, alors que l'encombrement d'un tableau est fixé d'avance et constant.

NOTE. Une conséquence de l'encombrement constant d'un tableau est le risque de saturation : l'insertion d'un élément échoue parce que toutes les cases du tableau sont déjà occupées. Bien sûr, ce risque existe aussi dans le cas des listes chaînées (il se manifeste par l'échec de la fonction malloc), mais il correspond alors à la saturation de la mémoire de l'ordinateur ; c'est un événement grave mais rare. Alors que le débordement des tableaux est beaucoup plus fréquent, car il ne traduit qu'une erreur d'appréciation de la part du programmeur (si le tableau est statique) ou de l'utilisateur (si le tableau est dynamique).

Le parcours des listes est une opération qui revient fréquemment dans les applications. Par exemple, le parcours d'une liste à la recherche d'un maillon portant une information x donnée alors que l'on n'est pas sûr qu'un tel maillon existe, peut se programmer ainsi :

POINTEUR trouver(OBJET x, POINTEUR p) { /* rend p tel que p->info == x ou NULL */
    while (p != NULL && p->info != x)
        p = p->suiv;
    return p;
}

Supposons avoir à écrire un programme où cette opération est critique (autrement les considérations suivantes sont sans intérêt). Nous devons essayer de rendre la boucle while ci-dessus, qui est déjà très simple, encore moins onéreuse.

C'est le moment de nous rappeler que la seule caractéristique de NULL que nous utilisons est le fait d'être une adresse conventionnelle distincte de toutes les autres adresses manipulées. Par conséquent, n'importe quelle adresse pourra jouer le rôle de NULL, à la condition qu'elle ait fait l'objet d'une convention préalable, connue et suivie par la partie de notre programme qui a construit la liste. Par exemple, l'adresse NULLBIS d'un maillon créé par nos soins :

MAILLON laFinDeToutesLesListes;
#define NULLBIS (&laFinDeToutesLesListes)

Il est clair qu'un programme correct (ne contenant pas initialement les deux noms ci-dessus) dans lequel on a ensuite ajouté les deux lignes précédentes, puis remplacé par NULLBIS chaque occurrence de NULL, est encore correct. Par exemple (ceci suppose que, comme dit précédemment, en construisant la liste on a utilisé NULLBIS à la place de NULL) :

POINTEUR trouver(OBJET x, POINTEUR p) { /* rend p t.q. p->info == x ou NULLBIS */
    while (p != NULLBIS && p->info != x)
        p = p->suiv;
    return p;
}

Pour le moment nous n'avons rien gagné. Mais cela devient intéressant quand on s'aperçoit qu'on peut améliorer la fonction trouver en logeant dans le maillon pointé par NULLBIS une valeur « sentinelle » :

POINTEUR trouver(OBJET x, POINTEUR p) { /* rend p t.q. p->info == x ou NULLBIS */
    NULLBIS->info = x;
    while (p->info != x) /* maintenant on est sûr de "trouver" x */
        p = p->suiv;
    return p;
}

Dans la boucle (la seule partie qui doit nous intéresser, du point de vue de l'efficacité) nous avons remplacé deux comparaisons par une seule. On peut estimer que la boucle a été réduite de 2/3.

Des sections précédentes se dégage une notion de liste assez terre à terre, faisant penser plus à une collection de trucs et astuces pour économiser l'espace ou gagner du temps qu'à une structure de données tant soit peu abstraite. Pour rehausser le débat, voici comment on peut présenter les listes d'une manière plus formelle, comme cela se fait dans les langages Lisp, Prolog, etc. où elles sont les structures de données fondamentales.

DÉFINITION

Soit X un ensemble. Une liste d'éléments de X est définie récursivement comme : un symbole conventionnel, appelé la liste vide, ou bien, un couple ( i , L ) où i ∈ X et L est une liste d'éléments de X.

Le rapport avec ce que nous appelions liste précédemment devient évident si on décide qu'une liste sera représentée dans un programme par une adresse : soit NULL, représentant la liste vide, soit l'adresse d'un maillon à deux champs représentant une paire ( i , L ) :

De cette définition récursive des listes dérive immédiatement une définition récursive de l'algorithme de leur parcours : pour parcourir une liste L il faut :

• si L est la liste vide, ne rien faire ;
• si L = ( i , L' ), exploiter i puis parcourir L'.

Ici, « exploiter » représente une opération qui dépend de l'ensemble X et du problème particulier considéré. Ce qui donne le programme :

void parcours(POINTEUR liste) {
    if (liste != NULL) {
        EXPLOITER(liste->info);
        parcours(liste->suiv);
    }
}

Une liste ordonnée est une liste dont les maillons ont un champ clé (éventuellement le champ info tout entier), dont les valeurs appartiennent à un ensemble totalement ordonné, et la liste vérifie :

si p->suiv existe alors p->cle ≤ p->suiv->cle

Les listes ordonnées se rencontrent très fréquemment, nous en verrons des exemples dans les pages suivantes. L'ajout d'un maillon nouveau dans une telle structure met en évidence une qualité des listes : l'insertion d'un élément au milieu de la liste ne requiert pas le déplacement « physique » des éléments qui seront derrière le nouveau venu.

L'insertion d'un élément dans une liste ordonnée se fait en trois temps (les deux premiers sont interchangeables) :

• rechercher la place dans la liste du nouvel élément ;
• allouer le nouveau maillon et remplir ses champs ;

• raccrocher le nouvel élément à la liste, ce qui se fait de deux manières, selon que :

  • la liste est vide ou le nouvel élément se place à la tête de la liste (c.-à-d. : le nouvel élément ne sera le successeur d'aucun maillon),
  • la liste n'est pas vide et le nouvel élément ne se place pas en tête.

Ce qui donne, en supposant que la liste est repérée par un pointeur teteDeListe :

POINTEUR pr, pc, nouveau;
pc = teteDeListe; /* pc parcourt la liste, pr court après pc */
while (pc != NULL && pc->cle < x) {
    pr = pc;
    pc = pc->suiv;
}
nouveau = maillon(x, autres informations, pc);
if (pc == teteDeListe)
    teteDeListe = nouveau;
else
    pr->suiv = nouveau;

On peut abolir la différence de traitement qui existe entre l'insertion d'un maillon en tête d'une liste et l'insertion à une autre place (voir le programme précédent), en convenant que toute liste commencera par un maillon « technique », sans signification pour l'application. Ainsi, d'un point de vue pratique, une liste ne sera jamais vide et, lors de l'insertion d'un maillon, il n'y aura qu'un seul cas à considérer.

Si on procède ainsi, une liste ne sera pas représentée par l'adresse de son premier maillon utile mais par l'adresse d'un maillon sans signification, voire - si on programme en C - par ce maillon sans signification lui-même. À la place de :

POINTEUR teteDeListe;

on aura :

MAILLON maillonBidon;

Voici le programme de recherche/insertion qui correspond à une telle liste. Comme prévu, la deuxième partie de l'insertion se simplifie bien :

POINTEUR pr, pc;
…
pr = &maillonBidon;
pc = maillonBidon.suiv;
while (pc != NULL && pc->cle < x) {
    pr = pc;
    pc = pc->suiv;
}
pr->suiv = maillon(x, /* autres informations */, pc);

On peut trouver cette manière de gérer les listes préférable, mais ce n'est pas une évidence. Elle ne simplifie que le texte du programme, dont l'exécution n'est ni plus ni moins rapide que celle de la version précédente, car nous n'avons pas modifié la boucle while qui, du point de vue de l'efficacité, est la seule partie à considérer. D'autre part, cette simplification se paye par un encombrement supplémentaire de chaque liste, puisque nous avons remplacé un pointeur par un maillon tout entier. Ce surencombrement ne peut être tenu pour négligeable que lorsqu'on doit gérer un petit nombre de listes ou bien des listes faites de maillons dont la partie info est de petite taille.

VARIANTE

Ayant introduit le maillon sans signification, qui garantit qu'une liste a toujours au moins un élément, nous pouvons récrire le programme précédent à l'aide d'un seul pointeur :

POINTEUR pr;
…
pr = &maillonBidon;
while (pr->suiv != NULL && pr->suiv->cle < x)
    pr = pr->suiv;
pr->suiv = maillon(x, autres informations, pr->suiv);

Il est difficile de dire si cette version du programme est plus ou moins rapide que la précédente, car dans la boucle, nous avons supprimé une affectation mais nous avons ajouté deux indirections.

Pour implanter une queue nous nous donnerons deux indices, appelés premier et dernier, et nous utiliserons un tableau circulaire, obtenu à partir d'un tableau ordinaire en décidant que la première case du tableau fait suite à la dernière.

D'un point de vue technique, il suffira de modifier légèrement l'opération « passage au successeur ». Pour un tableau ordinaire, cette opération se traduit par l'incrémentation d'un indice :

i = i + 1;

Pour avoir un tableau circulaire, nous faisons une incrémentation modulo la taille du tableau :

i = (i + 1) % TAILLE_TABLEAU;

Attention, premier n'est pas nécessairement devant dernier :

#define MAXQUEUE 10
OBJET queue[MAXQUEUE];
int premier, dernier, nombre;
#define SUCCESS(i) (((i) + 1) % MAXQUEUE)

void initialiser(void)
{
    nombre = 0;
    premier = dernier = 0;
}

void entrer(OBJET x)
{
    assert(nombre < MAXQUEUE);
    nombre++;
    queue[dernier] = x;
    dernier = SUCCESS(dernier);
}

OBJET sortir(void)
{
    OBJET r;
    assert(nombre > 0);
    nombre--;
    r = queue[premier];
    premier = SUCCESS(premier);
    return r;
}

Remarque : on peut être surpris par la présence du compteur nombre, croyant que la position relative de premier et dernier suffit pour déceler qu'une queue est vide ou pleine. Or, il y a un petit piège : la figure 8 montre une queue avec deux éléments, que l'on fait sortir successivement, et une autre avec deux cases libres, que l'on remplit.

On constate que la position relative de premier et dernier, lorsque la queue est vide, est la même que celle qui correspond à une queue pleine. D'où la nécessité de prendre des mesures supplémentaires, comme veiller à ce qu'il y ait toujours une case libre ou bien utiliser un compteur du nombre d'éléments.