Discussion :

[gege2061]

Bonjour,
je cherche à crée une bibliothèque de gestion des listes chaînées circulaires et j'aurai aimé savoir s'il était util de garder une sentinelle sur le premier maillon créé :

[Tibo]

Quand tu parcours ta liste, il faut bien stocker quelque part un pointeur vers le premier élément de la liste pour t'arrêter. Sinon ça fait une boucle sans fin.

[Mac LAK]

Accessoirement, effectuer un double chaînage et conserver en annexe à la liste le nombre d'éléments (Count) est très utile.

Tout dépend aussi du but recherché : souvent, lorsqu'une liste chaînée circulaire est nécessaire, il est souvent très intéressant de "modifier" la tête de liste pour y assigner le pointeur courant après recherche fructueuse (=> la prochaine recherche "Next" ou "Prev" sera très rapide), et de blinder tes fonctions en utilisant une programmation par contrat (=> ne pas dépasser Count itérations).

Avec ces variantes implémentées, j'appelle ça les "listes Rolodex", car ça fonctionne exactement de la même manière que ces carnets. C'est extrêmement simple à implémenter, et ça offre de très bonnes performances en général.

[gege2061]

Tout dépend aussi du but recherché

C'est dans le cas général puisque c'est pour un tutorial.
Voici l'implémentation des listes doublement chaînées: http://nicolasj.developpez.com/articles/listedouble/ à partir de là je voudrai rendre la liste circulaire.
Pour l'instant, seul l'élément courant est connu et on accéde au autres éléments en passant par les liens prev et next. Est ce que ça peut passer pour une liste circulaire, sachant que le point d'arrêt sera l'élément courrant.

PS: quand je parle du permier élément, il s'agit du premier élément enregistrer.

[FrancisSourd]

Pour l'instant, seul l'élément courant est connu et on accéde au autres éléments en passant par les liens prev et next. Est ce que ça peut passer pour une liste circulaire, sachant que le point d'arrêt sera l'élément courrant.

Oui, cela suffit parfaitement d'avoir à tout moment uniquement un pointeur sur une cellule existante. A partir de ce pointeur, on peut tout faire (insertion et recherche). En effet, dans la structure circulaire, toutes les cellules sont topologiquement équivalente, il n'y a donc pas lieu d'en privilégier une (et donc il n'y a pas lieu de privilégier la première créée.

Il faudra cependant faire attention au cas où la liste peut devenir nulle (lorsqu'on enlève une cellule dans une liste à un élément, ce qui se détecte par courant->next==courant). Le plus simple est certainement de mettre à NULL le pointeur courant quand la liste devient nulle. Pour l'insertion et la recherche, il faudra en premier lieu tester si la cellule courante est NULL ou pas.

[Mac LAK]

Pour l'instant, seul l'élément courant est connu et on accéde au autres éléments en passant par les liens prev et next. Est ce que ça peut passer pour une liste circulaire, sachant que le point d'arrêt sera l'élément courrant.

Ca peut passer, mais il peut être risqué (d'un point de vue général, j'entends) de comparer les pointeurs entre eux : suivant l'implémentation utilisée au bilan final, l'adresse du pointeur peut changer (mémoire swappable) => maintenir le nombre d'éléments est plus fiable. Accessoirement, ça évite d'avoir à parcourir toute la liste pour en connaître la taille (opération très coûteuse en temps machine), et ça simplifie les boucles portant sur l'intégralité des éléments de la liste.

PS: quand je parle du permier élément, il s'agit du premier élément enregistrer.

Pour moi, il s'agit plutôt du pointeur "de base", c'est à dire celui par lequel on mémorise la liste. Habituellement, c'est effectivement le premier noeud créé, mais ça n'a rien d'obligatoire : dans mes implémentations "type Rolodex", c'était systématiquement le pointeur sur le dernier noeud demandé.
Par exemple, une recherche d'éléments faisait, comme seule et unique opération "extérieure", une modification de ce pointeur de base sur l'élément cherché. Les opérations de suppression ne pouvaient supprimer que l'élément courant, et l'ajout se faisait toujours après l'élément courant. Tu vois ce que je veux dire ?

[Selenite]

Finalement, une liste chainée circulaire, c'est une interface de liste chainée circulaire. A partir de là, tu peut faire du STL-like. C'est-à-dire que tu représente les données comme tu l'entend (par une liste chainée simple par exemple), et tu implémente un itérateur avec les fonction suivant, précédent, insérer et effacer.


Ton message m'a donné envie de faire une liste chainée circulaire simplissime. J'ai donc fait ça (C++):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
 
namespace ring_list
{
 
 
	template <typename T>
	class unit
	&#123;
 
		unit<T>* unext;
		unit<T>* uprev;
 
	public&#58;
 
		T data;
 
		unit &#40; const T& a &#41;
			&#58; data &#40; a &#41;
		&#123; 
 
			unext = this;
			uprev = this;
 
		&#125;
 
 
		unit<T>* next &#40; &#41; &#123; return unext; &#125;
		unit<T>* prev &#40; &#41; &#123; return uprev; &#125;
 
		void insert &#40; unit<T>* u &#41;
		&#123;
 
			this->unext->uprev = u->unext;
			u->unext->unext = this->unext;
 
			this->unext = &u;
			u->uprev = this;
		&#125;
 
		unit<T>* erase &#40; &#41;
		&#123;
 
			unit<T>* tmp1;
			unit<T>* tmp2;
 
			tmp1 = this->unext;
			tmp2 = this->uprev;
			this->uprev->unext = tmp1;
			this->unext->uprev = tmp2;
 
			return this;
		&#125;
 
 
	&#125;;
 
 
 
 
&#125;

Que l'on utilise comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
 
#include <iostream>
#include <cstdlib>
 
#include "ring_list.h"
 
namespace rl = ring_list;
 
 
int main &#40;&#41;
&#123;
 
	typedef rl&#58;&#58;unit<int> unit;
 
	int n, i;
	std&#58;&#58;cin >> n;
 
	unit* u = new unit&#40;n&#41;;
 
	for &#40; i = 0 ; i < n ; i++ &#41;
		u->insert&#40; new unit&#40; std&#58;&#58;rand&#40;&#41; &#41; &#41;;
 
 
	while&#40; true &#41;
	&#123;
 
		std&#58;&#58;cin >> i;
 
		if &#40; i == 0 &#41;
			break;
 
		while &#40; i-- &#41;
			u = u->next&#40;&#41;;
 
		std&#58;&#58;cout << u->data << std&#58;&#58;endl;
 
	&#125;
 
	for &#40; i = 0 ; i <= n ; i++ &#41;
		delete u->next&#40;&#41;->erase&#40;&#41;;
 
 
	return 0;
&#125;

Bon, c'est plus pour le fun qu'autre chose ;-). Mais ça respecte quelques points qui me paraissent essentiels (du moins pour l'interface, en interne on fait ce que l'on veut):
- une liste circulaire n'a ni début, ni fin.
- une lc ne connait pas son nombre d'élément. (Discutable. Mais je pense que el nombre d'élément vaut fin - début, or il n'y a ni début ni fin.)
- une lc peut être prise par n'importe quel bout.

[Mac LAK]

- une lc ne connait pas son nombre d'élément. (Discutable. Mais je pense que el nombre d'élément vaut fin - début, or il n'y a ni début ni fin.)

Hum hum... Amplement discutable, même.
Une liste circulaire est un ensemble, qui a donc une cardinalité si tu préfères ce terme. Or, dans ce cas précis, le cardinal de la liste correspond à son nombre d'éléments.
Le nombre d'éléments est loin d'être toujours aussi simple à calculer que "fin-début", hélas...

[Selenite]

- une lc ne connait pas son nombre d'élément. (Discutable. Mais je pense que el nombre d'élément vaut fin - début, or il n'y a ni début ni fin.)

Hum hum... Amplement discutable, même.
Une liste circulaire est un ensemble, qui a donc une cardinalité si tu préfères ce terme. Or, dans ce cas précis, le cardinal de la liste correspond à son nombre d'éléments.
Le nombre d'éléments est loin d'être toujours aussi simple à calculer que "fin-début", hélas...

Quand je dis fin - début, c'est en terme de pointeur ou d'itérateur. Une LC à bien une cardinalité, mais l'utilisateur en a-t-il besoin ? Une liste circulaire est utilisée pour simuler l'infini. A partir du moment ou on doit connaitre le nombre d'élément, une liste circulaire ne répond plus au besoin. De même que parcourir les éléments jusqu'a revenir au point de départ d'une LC n'a pas vraiment de sens, ceci reviendrait à écrire for ( i = lc.begin() ; i < lc.end() ; i++ ) or comme je l'ai dit, une LC n'a ni de début, ni de fin.

[Mac LAK]

Une LC à bien une cardinalité, mais l'utilisateur en a-t-il besoin ?

Disons plutôt que je ne connais pas beaucoup d'utilisations d'une telle liste où la cardinalité ne joue pas un rôle...

Une liste circulaire est utilisée pour simuler l'infini.

Son utilisation est plutôt pour un truc du genre "présentoir", et je ne vois vraiment pas ce que viens faire l'infini là-dedans...
Lorsque j'appelle ça des "liste Rolodex", tu devrais regarder exactement ce qu'est un Rolodex : tu comprendrais certainement que c'est la notion de pouvoir partir de n'importe où sans louper des éléments qui est importante, et non pas celle d'avoir quelque chose "d'infini". C'est en ça que la cardinalité est importante, notamment si ça implémente un fichier client...

[Selenite]

Infini dans dans le sens de sans fin.
Je verrais bien une LC pour traiter une boucle d'action. Un module effectue une action et passe à la suivante. Un autre rajoute des actions dans la LC, au besoin. Une LC nous libère de la notion d'indice (et même d'ordre).
Un Rolodex est un bon exemple. Mais si la cardinalité intervient, une LC en répond plus au besoins (amuse toi à compter les pages d'un Rolodex, sans marque page, tu ne peut pas).

[Mac LAK]

(amuse toi à compter les pages d'un Rolodex, sans marque page, tu ne peut pas).

Mais c'est exactement pour cette raison que je dis qu'il faut qu'elle exporte sa cardinalité !!!
Le problème de la LC "simple", c'est justement ce rebouclage non-automatique => d'où liste circulaire, même si la cardinalité intervient.

[Selenite]

D'accord, je comprend ce que tu veux dire.


Pff... Il y comprend rien lui... Les listes circulaires c'est toute une philosophie, le summum de l'abstraction, et il vient me parler de cardinalité. ;-)

[Mac LAK]

Pff... Il y comprend rien lui... Les listes circulaires c'est toute une philosophie, le summum de l'abstraction, et il vient me parler de cardinalité. ;-)

Arrêtes de marmonner comme ça, c'est vraiment pas poli, et puis l'implémentation corrompt l'abstraction... ;-)

[gege2061]

Le problème de la LC "simple", c'est justement ce rebouclage non-automatique => d'où liste circulaire, même si la cardinalité intervient.

Ce qui veut dire que seul les listes simplement chaînées on un intérêt à être cirulaire :

[Mac LAK]

Ce qui veut dire que seul les listes simplement chaînées on un intérêt à être cirulaire :

Non.
Lorsque tu commences "au milieu" d'une LC (même doublement chaînée), lorsque tu as "fini" ta liste, tu repars au début.
En simple chaînage, tu n'as pas le choix. En double chaînage, c'est idiot de repartir en sens inverse, car tu traiterais certains éléments plusieurs fois (une fois dans le sens "positif", une fois dans le sens "négatif" de parcours). J'illustre mon propos :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Parcours liste simplement chaînée :
LC |----------S-----------|
              |            
 />##########FD############>\
 |                          |
 \<<<<<<<<<<<<<<<<<<<<<<<<<</
 
Parcours liste doublement chaînée &#58;
LC |----------S-----------|
              |            
              D############>-\
   F##########@@@@@@@@@@@@@<-/
 
S &#58; Début de parcours.
D &#58; Premier noeud examiné.
F &#58; Dernier noeud examiné.
# &#58; Noeud examiné 1 fois.
@ ; Noeud examiné 2 fois.
<->|/\ &#58; Déplacement sans examen.

Tu vois aussi que même les listes doublement chaînées peuvent avoir un intérêt à être circulaires : ne serait-ce que pour "reculer" d'un élément sans avoir à parcourir l'intégralité de la liste moins un élément... ;-)

Exemple : si les éléments sont plus ou moins "indicés" ou "classés" (ça, c'est fonction de l'utilisation de la LC circulaire doublement chaînée), le calcul d'écart entre la valeur de l'indice courant et de l'indice "cible" permet d'optimiser le sens de parcours afin de réduire au maximum les déplacements. C'est une problématique courante dans le pilotage des automates (réduction des déplacements mécaniques, et accélération des positionnements).