les sentinelles dans les listes chaînées

Voilà j'ai toujours fait mes listes chaînées sans sentinelle.
Un nouveau prof nous impose de les utiliser.
ça complique systématiquement tout mes algos, si bien que je me dis que je ne dois pas avoir compris le sens même de la sentinelle ( qui est sensée simplifiée les conditions d'arrêt).

exemple simple, insertion dans une liste chaînée triée. Sans sentinelle:
je compare jusqu'à trouver ou insérer, et si j'ai pas trouver quand j'arrive au bout de la liste, j'insère là.

Avec sentinelle, si j'ai pas trouvé à la fin, je vais "reboucler" sur le début ( génial...) à moins de rajouter un test qui peut être de la forme :
- Conserver l'adresse de la sentinelle pour vérifier à quel môment je repasse dessus ( assez nul quand même, surtout si on veut faire une récurence, on va se le trimballer tout le long alors que sans sentinelle on aurait pas eu cette variable, il suffisait de comparer avec NULL sans se poser de question).
-initialiser les données de la sentinelle à une valeur particulière (super nul puisque d'un point de vue objet c'est immonde, l'initialisation et le tests sont dans deux fonctions différentes).

Merci d'avance pour vos lumières, jeune jedi en train de basculer dans le côté obscur cherche maître yoda.

Donc, on vous demande de remplacer des listes chaînées normales se terminant avec NULL par des listes chaînées circulaires ne se terminant qu'avec un chaînon contenant une valeur sentinelle, c'est ça?

j'ai moi aussi du mal à comprendre puisque pour moi le dernier pointeur à NULL constituait lui-même une sentinelle plus que suffisante... Je ne vois pas du tout comment c'est supposer simplifier non plus...

à moins que tu n'aies pas compris ce que LUI appelle "sentinelle"...

pour lui sentinelle = liste circulaire. une liste sans sentinelle va s'achever par NULL.
avec sentinelle, à la fin, tu as un lien entre le dernier et le premier chainon.
J'ai hélas bien compris :/

J'ai donc deux options :
1/ Obéir et maugréer que son système est sioux :( .
2/ Me rebeller et faire mon projet comme je l'entend :twisted: .

au moins, la liste avec sentinelle a un (maigre) avantage: à aucun moment, le pointeur n'est censé être NULL.

Le mieux dans ce cas, c'est de tester dans le while/for la si on est en valeur sentinelle ou non, au lieu de tester le pointeur... (juste un assert(pointeur!=NULL) pour le débogage)

Edit:
Un truc à envisage par contre, c'est la liste vide: comment doit-elle être ?
à mon avis, toute vide qu'elle est, elle doit quand même comporter au moins une valeur, la sentinelle elle-même (il en est de même pour les chaînes de caractères: "" contient toujours le \0).

oui d'après sa vision des choses la liste vide contient une sentinelle qui pointe vers elle même.

Citation:

---

Envoyé par eizo

oui d'après sa vision des choses la liste vide contient une sentinelle qui pointe vers elle même.

---

Dans le cadre d'une liste bouclée, ça se comprend.

Mais les cas d'utilisation des listes bouclées sont plutôt rares (scheduler, par exemple).

Je pense que la liste doublement chainée est plus intéressante.

Pour l'utilisation de la sentinelle regarde ici

je connais ce tuto qui m'a énormément appris il y a bien longtemps !
merci qd même