La puissance des pointeurs :
Les listes chaînées
linked_list.cpp

 


Voici la situation : nous connaissons les structures, les pointeurs, l'allocation dynamique de mémoire. C'est beau. C'est grand. Qu'est-ce qu'on en fait? (et vlan, on a cassé l'ambiance! :-).

Dans ce cours-ci, nous allons mettre en oeuvre toutes ces connaissances à la fois, pour créer une structure de donnée (terme à ne pas confondre avec les struct et le reste) très utilisée : la liste chaînée. Si vous en avez déjà entendu parler, c'est très bien. Si vous en avez déjà programmé, c'est encore mieux, car vous n'aurez que la partie purement "C++" à apprendre. Pour ceux qui n'ont aucune idée de quoi il s'agit, ce n'est pas grave : on attaque tout de suite.

Le principe

Dans le cours précédent, nous avions rencontré un problème : comment n'utiliser que la mémoire dont on a besoin, alors qu'on sait qu'on va devoir manipuler une collection de données similaires. Nous avions alors introduit les tableaux dynamiques : ils grandissent à chaque fois qu'on y ajoute un élément. Cette méthode est parfaitement correcte, mais elle présente un désavantage de taille : elle est très lente.

Revoyons le fonctionnement du tableau dynamique, que nous appelerons T :

Et maintenant, calculons! Soit n la longueur de T. Notre programme manipule un tableau dynamique d'ints, et dans une boucle, il y ajoute 1000 éléments. Combien de copies d'int le programme doit-il alors effectué? Je vous passe le calcul, mais au total, on aura copié 500500 entiers, rien que dans cette boucle. Pas mal, non? Sans compter les allocations de mémoire, et tout ce qui va avec la manipulation du tableau. Pour 1000, il ne faudra pas longtemps avant d'avoir fini la boucle. Mais si il y a plus de 1000 éléments dans le tableau, ou s'il faut manipuler le tableau dynamique à chaque itération d'une boucle... galère!

Le tableau dynamique est donc facile à comprendre, mais fort peu efficace. Il vaut mieux alors faire appel à la liste chaînée. Voici le principe de fonctionnement :

Une liste chaînée est composée d'éléments. Chaque élémént est composé de deux "briques" : l'une pour les données auquelles l'élément est associé, et l'autre comme pointeur vers l'élément suivant dans la liste. C'est tout simple.

Bien sûr, chaque élément de la liste est un peu plus grand que les données qu'il contient, ce qui fait qu'une liste de n éléments occupe plus de mémoire qu'un tableau de même taille. Mais il faut savoir qu'en général, les données sont des structures ou d'autres collections de données, qui sont beaucoup plus grandes que le petit pointeur qui permet de connaître l'élément suivant, ce qui rend la perte de mémoire négligeable : au lieu d'avoir un tableau de 800 éléments de 30 octets chacun, occupant ainsi 24000 octets en mémoire, vous aurez une liste chaînée occupant 25600 octets. Pas si méchant. De toute façon, la liste chaînée présente bien trop d'avantages par rapport à un tableau dynamique, si bien que cette considération semble bien ridicule.

Maintenant, lorsqu'on veut insérer un objet, à la fin du tableau par exemple, il suffit de le créer, puis de dire que le dernier élément de la liste pointe vers l'objet nouvellement créé... et c'est tout! On ne copie pas de données, on réaffecte tout simplement un pointeur. Retirer un élément de la liste n'est pas difficile non-plus : il suffit de dire que son précédent pointe sur son suivant, et voilà, l'élément n'est plus dans la liste. Encore une fois, pas de copie. Le gain en vitesse est substantiel.

Réalisation d'une liste chaînée

Il existe mille et une façons de programmer et d'utiliser une liste chaînée. En réalité, tout dépend de son rôle dans le programme. On peut avoir besoin d'une liste chaînée simple, d'une liste chaînée double (avec un pointeur vers l'élément précédent), une liste circulaire, et toutes les combinaisons imaginables. On peut créer une file FIFO (First In First Out), une pile LIFO (Last In First Out), on peut écrire des queues de priorité (comme les listes de processus en cours dans les systèmes multi-tâches)... La liste est longue.

Pour réaliser notre petite liste chaînée, nous allons commencer par un modèle très simple de liste :

Pour réaliser cette liste, il va nous falloir une struct qui va faire office d'élément. On l'appellera Element. La tête de la liste sera un pointeur global (cette solution étant la plus simple, à défaut d'être élégante).

struct Element
{

int valeur;
Element* suivant;

};

Element* liste = NULL;

Bien. Ensuite, il nous faut trois fonctions : ajouter, rechercher et supprimer.

void Ajouter(int valeur)
{

Element* element= new Element;
// On fixe la valeur de l'élément
element->valeur = valeur;
// Comme on place le nouvel élément en début
// de liste, on dit que son suivant est le
// premier élément de la liste.

element->suivant = liste;
// Puis on remet à jour le pointeur vers le
// premier élément de la liste, qui est notre
// nouvel élément.

liste = element;

}

Element* Rechercher(int valeur)
{

Element* element = liste;
// La méthode de recherche est simple :
// On se place en première position, et tant
// qu'il y a des éléments suivants, on suit
// les flèches, jusqu'à ce qu'on trouve un
// élément de liste qui contienne la valeur
// recherchée.

while(element != NULL && element->valeur != valeur)

element = element->suivant;

// Ici, on renvoie une information pertinente :
// - ou bien on a trouvé quelque chose, auquel
// cas on renvoie ce quelque chose,
// - ou bien on n'a rien trouvé et element vaut
// NULL, qui est la valeur qui indique qu'un élément
// n'a pas été trouvé.

return element;

}

void Supprimer(Element* element)
{

Element* precedent = liste;
// Si l'élément à supprimer est le premier de
// la liste, alors le travail est vite fait.

if
(element == liste)
{

liste = NULL;
delete element;
return;

}

// Sinon, il faut rechercher l'élément précédent,
// et détourner le pointeur de ce précédent pour
// pointer vers l'élément suivant celui à supprimer.
// Ainsi, il ne se trouve plus dans la liste.

while(precedent != NULL && precedent->suivant != element)

precedent = precedent->suivant;

if(precedent == NULL) return;
precedent->suivant = element->suivant;
delete element;

}

Voici pour la manipulation de la liste à proprement parler. Dans notre cas, nous allouons et désallouons la mémoire nécessaire à la liste au moment de l'ajout et de la suppression d'un élément. Encore une fois, il existe mille et une façon de gérer ceci, surtout en C++.

Passons maintenant au corps du programme, avec en prime une fonction pour afficher la liste.

void Afficher()
{

Element* element = liste;
while(element != NULL)
{

cout << element->valeur << "\t";
element = element->suivant;

}
cout << endl;

}

int main(void)
{

Element* e;

Ajouter(10);
Ajouter(5);
Ajouter(13);
Ajouter(7);

Afficher();

e = Rechercher(5);
Supprimer(e);

Afficher();

return 0;

}

Une fois le programme ci-dessus compilé (il est joint dans le fichier linked_list.cpp), on peut constater que l'affichage n'a rien de surprenant :

7   13   5   10
7   13   10

Notez bien que puisqu'on insère les éléments au début de la liste, ils apparaissent dans l'ordre inverse de celui de l'ajout. Autre point subtile : le pointeur liste, qui pointe toujours sur le premier élément de la liste est initialisé à NULL. Ceci à pour effet quelque chose de très pratique dans notre cas : le premier élément qui sera ajouté aura pour suivant NULL. Cette valeur particulière va nous permettre de très simplement repérer le dernier élément de la liste (c'est celui dont le pointeur suivant vaut NULL).

Comme je vous l'ai dit, il existe plusieurs façons d'implémenter une liste chaînée, et elle peut avoir plusieurs utilisations différentes. Dans les exercices qui vont suivre, je vais vous proposer quelques extensions/modifications qui sont courantes dans les programmes (car croyez-moi, vous allez en programmer des listes chaînées! :-).

  • Une première modification serait de pouvoir insérer une élément à une position donnée. Si je donne à la fonction Ajouter() l'adresse du troisième élément de la liste et la valeur 14 en paramètre, alors elle insérerait à la troisième position un nouvel élément dont la valeur serait 14 (et l'élément désigné par le pointeur passé en paramètre deviendrait le 4ème élément de la liste).
  • A partir de cette modification, il n'est pas difficile de faire une liste chaînée triée : il suffit d'insérer chaque nouvel élément à la bonne position (position qu'on recherche par une méthode similaire que dans la fonction Rechercher() ci-dessus.)
  • A chaque fois que nous supprimons un élément de la liste, nous devons reparcourir toute la liste jusqu'à l'élément précédent l'élément à supprimer, ce qui n'est pas très efficace lorsque la liste est vraiment grande. Une façon de remédier à cela est une liste double chaînée : chaque élément possède un pointeur vers l'élément suivant, mais aussi un pointeur vers l'élément précédent. Ainsi, lorsqu'on veut supprimer un élément, la manipulation est immédiate. Essayez d'implémenter, à partir de ce que vous avez déjà fait, une liste double chaînée.
  • Avec une liste doublement chaînée, il peut être intéressant de savoir également où se trouve le dernier élément de la liste. Une autre information utile est le nombre d'éléments que contient la liste. On peut alors concevoir une petite struct qui va tenir toutes ces informations. On pourra alors rendre une instance de cette struct globale, plutôt que le pointeur vers le début de la liste.
  • En modifiant le programme légèrement, sauriez-vous gérer plusieurs listes à la fois ? Chaque liste correspondrait à une instance de la struct introduite ci-avant. Cela nécessiterait de modifier les fonctions de gestion de liste pour qu'elles prennent en paramètre la liste à utiliser.
  • Maintenant, nous allons voir un type de structure particulier : la pile. Elle fonction sur le principe du LIFO : Last In First Out, autrement dit, on ne peut retirer de la liste que le dernier élément ajouté. C'est un peu le principe de la pile de plateau : on rajoute un plateau sur le dessus de la pile, et si on veut atteindre le troisième plateau (en partant du haut), on est obligé de retirer les deux plateaux qui sont au-dessus.
    De manière plus informatique, la pile est omniprésente. Si vous vous rappelez, les variables statiques (c'est-à-dire les variables déclarées directoment, sans pointeur) sont allouées dans la pile de votre programme. Lorsque le programme entre dans une fonction, il rajoute les variables locales en haut de la pile (en réalité, la pile est à l'envers, mais je ne vais pas vous embrouiller avec ça pour l'instant), et les dépile lorsque l'exécution sort de la fonction. En assembleur, on travaille constemment avec la pile, grâce aux instructions PUSH (empiler une valeur) et POP (récupérer la dernière valeur empilée).
    En reprenant le programme proposé dans le cours, et en renommant les fonctions d'ajout et de suppression d'élément, pourriez-vous utiliser la liste chaînée comme pile d'entiers ? Voici les prototypes des fonctions Push() et Pop() à utiliser au lieur de Ajouter() et Supprimer() :
    • void Push(int valeur);
      Empile l'entier valeur.
    • int Pop(void);
      Renvoie la valeur du dernier entier empilé avec push().

    Bien entendu, on ne peut pas dépiler plus de valeur qu'il n'y en a d'empilées.

Les listes chaînées et leurs utilisation ne constituent qu'une partie des structures complexes de données qu'on peut utiliser en programmation. Notamment, une liste linéaire n'est pas très efficace lorsqu'il s'agit de trier des objets : au pire des cas, on doit parcourir toute la liste avant d'avoir trouvé la bonne place. Pour ce genre d'applications, il existe un autre type de structure, plus intéressante (mais aussi plus complexe) : les arbres. Ce sera le thème de notre prochain cours. D'ici là, bonnes listes !


Retour au sommaireLa gestion dynamique de la mémoireLes arbres