Liste avec smart pointers

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 :

1. la donnée membre m_Prev;
2. l’accesseur et le modifieur correspondants;
3. 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);    

Liste double avec smart pointers

L’ordre des éléments dans une liste LRU ne dépend que de l’ancienneté du dernier accès à chaque élément, ce qui implique deux conséquences :

1. 1. même si la liste est triée à un instant donné, chaque insertion ou recherche a probablement pour effet de modifier l’ordre de la liste (sauf si ce ne sont que de accès en tête). L’algorithme de recherche à utiliser est donc celui d’une recherche séquentielle dans un ensemble non trié.
   2. l’utilisateur ne peut plus choisir la position à laquelle un élément doit être inséré dans la liste : la propriété “LRU” impose qu’elle soit toujours effectuée en tête.

Travail à effectuer
Modifier la classe CList pour qu’elle réponde au propriété “LRU”.

Nb: on considère que l’affichage ne modifie pas l’ordre des éléments de la liste.

1. Faites en sorte de pouvoir afficher votre arbre sans utiliser de fonction d’aide dite “locale”.
2. Afficher la vue arborescente de l’arbre : chaque fils est décalé d’une indentation par rapport à son père.