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
}; |
Bien. Ensuite, il nous faut trois fonctions : ajouter, rechercher et supprimer.
void Ajouter(int valeur)
} Element* Rechercher(int valeur)
} void Supprimer(Element* 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()
} int main(void)
} |
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! :-).
|
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 !