Nous avons montré précédemment que les listes simplement chaînées présentent entre autres un inconvénient majeur : celui d’interdire le retour arrière. Cette impossibilité nécessite, même pour les opérations élémentaires et indispensables comme la suppression d’un élément, de mémoriser au minimum le pointeur vers l’élément précédent au fur et à mesure du parcours. Cependant, toute permutation, tout déplacement (en particulier les tris) deviennent inutilement complexes et malcommodes.
L’alternative est de construire des éléments possédant un double chaînage, vers le précédent et vers le suivant. En fait, chaque information appartient à deux listes simples inverses l’une de l’autre.
Le parcours de la liste double pouvant être effectué à tout moment dans les deux sens, il est normal qu’elle possède deux points d’entrée, la Tete et la Queue.
Dans l’exercice “Sentinelle dans une liste simple”, nous avons montré que les ajouts/suppressions en tête pouvaient être banalisés en insérant au début de la liste, et dès sa construction, un élément “vide”, appelé sentinelle.
Le problème est le même pour les listes doubles, et se reproduit avec les opérations d’ajout/suppression en queue. C’est pourquoi les listes doublement chaînées sont généralement implémentées avec deux sentinelles, appelées naturellement sentinelles de tête et sentinelle de queue. Ainsi, la structure d’une liste double vide est illustrée dans l’encadré supérieur de la figure ci-dessous :
Travail à effectuer
Ajouter à la classe CNode :
- la donnée membre
m_Prev;
- l’accesseur et le modifieur correspondants;
- le corps du constructeur et du destructeur de la classe.
Modifier, dans la classe CList, le constructeur, les fonctions AddAfter() et Delete().
Ajouter la fonction AddBefore() de profil :
void AddBefore (const std::shared_ptr < CNode < T>> &, const T & val);