Listes chaînées circulaires

Version imprimable

07/05/2005, 17h32
gege2061

Listes chaînées circulaires

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éé :?:
07/05/2005, 18h40
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.
08/05/2005, 00h35
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.
08/05/2005, 14h37
gege2061

Citation:

Envoyé par Mac LAK

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.
08/05/2005, 15h19
FrancisSourd

Citation:

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.
08/05/2005, 19h43
Mac LAK

Citation:

Envoyé par gege2061

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.

Citation:

Envoyé par gege2061

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 ?

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:

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 { unit<T>* unext; unit<T>* uprev; public: T data; unit ( const T& a ) : data ( a ) { unext = this; uprev = this; } unit<T>* next ( ) { return unext; } unit<T>* prev ( ) { return uprev; } void insert ( unit<T>* u ) { this->unext->uprev = u->unext; u->unext->unext = this->unext; this->unext = &u; u->uprev = this; } unit<T>* erase ( ) { unit<T>* tmp1; unit<T>* tmp2; tmp1 = this->unext; tmp2 = this->uprev; this->uprev->unext = tmp1; this->unext->uprev = tmp2; return this; } }; }
Que l'on utilise comme ceci:
Code:

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 () { typedef rl::unit<int> unit; int n, i; std::cin >> n; unit* u = new unit(n); for ( i = 0 ; i < n ; i++ ) u->insert( new unit( std::rand() ) ); while( true ) { std::cin >> i; if ( i == 0 ) break; while ( i-- ) u = u->next(); std::cout << u->data << std::endl; } for ( i = 0 ; i <= n ; i++ ) delete u->next()->erase(); return 0; }
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.

08/05/2005, 20h38
Mac LAK

Citation:

Envoyé par 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...
08/05/2005, 21h10
Selenite

Citation:

Envoyé par Mac LAK

Citation:

Envoyé par 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.
08/05/2005, 21h22
Mac LAK

Citation:

Envoyé par Selenite

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...

Citation:

Envoyé par Selenite

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

http://yelims3.free.fr/Hein/Hein03.gif
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...
09/05/2005, 12h35
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).
09/05/2005, 19h48
Mac LAK

Citation:

Envoyé par Selenite

(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.
09/05/2005, 20h42
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é. ;-)
09/05/2005, 21h40
Mac LAK

Citation:

Envoyé par Selenite

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... ;-)
11/05/2005, 12h14
gege2061

Citation:

Envoyé par Mac LAK

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 :?:

Citation:

Envoyé par gege2061

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:

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 : LC |----------S-----------| | D############>-\ F##########@@@@@@@@@@@@@<-/ S : Début de parcours. D : Premier noeud examiné. F : Dernier noeud examiné. # : Noeud examiné 1 fois. @ ; Noeud examiné 2 fois. <->|/\ : 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).