Une liste circulaire n'est rien d'autre qu'une liste tout à fait classique - qu'elle soit simplement ou doublement chaînée - dont le dernier élément de la liste pointe sur le premier, et inversément dans le cas d'une liste doublement chaînée.
L'avantage principal d'une liste circulaire, c'est que, comme tout cercle, elle n'a plus ni début, ni fin.
Quand bien même il n'y aurait (plus) qu'un seul élément, on peut demander d'accéder dix fois à l'élément suivant, on se retrouvera sur un élément valide.
Tous les cas qui pourraient justifier que l'on souhaîte disposer d'une liste "infinie" d'éléments peuvent s'adapter à une telle liste, mais on peut citer, principalement:
Afin de faire prendre conscience de l'avantage que peut représenter cette technique, attardons nous un instant sur les possibilités qui nous sont offertes de faire autrement:
Un jeu de cartes disposant d'un nombre fini de cartes, nous pourrions très bien envisager de travailler avec un simple tableau.
Seulement, une même carte ne peut, théoriquement, être distribuée qu'à une seule personne, or, en n'ayant en tout et pour tout que - mettons 52 cartes pour un jeu complêt - la probabilité que la routine aléatoire nous envoie vers un élément du tableau qui a déjà été distribué augmentra avec le nombre de cartes qui ont déjà été distribuées et tendra tout doucement vèrs 1.
Cela signifie que, plus ne nombre de cartes déjà distribuées sera important, plus la recherche d'une carte encore disponible risque de prendre du temps.
La deuxième solution est d'utiliser, tout simplement, une liste chaînée classique (qu'elle soit simplement ou doublement chaînée n'important que peu dans l'histoire).
Cela nous permettrait de retirer facilement n'importe quelle carte du tas, et même d'envisager d'utiliser une liste pour gérer les cartes dont disposent les joueurs, ce qui en soi ne serait déjà pas si mal.
Par contre, cela implique malgré tout quelques tracas supplémentaires:
En effet, il faudra alors soit s'assurer que la routine aléatoire nous fournisse une valeur comprise entre 0 et le nombre de cartes à distribuer restant, soit s'assurer que l'on revienne au début de la liste si on en a atteint la fin…
Bien sûr, le fait de revenir au début de la liste si on est à la fin est très facile à faire - il suffit d'un simple test pour savoir s'il y a un élément suivant celui sur lequel on est - mais ce "simple test" devrait prendre place dans une boucle, et être effectué à chaque itération de la boucle.
Comme ce sont les petits ruisseaux qui font les grands fleuves, le fait de s'économiser le test peut faire, au final, gagner pas mal de temps au niveau du processeur.
Un autre inconvéniant, minime celui-là, de la liste "normale" est que… le début de la liste reste toujours le même.
Par contre, le fait d'utiliser une liste circulaire permet de prendre en permanence… la carte qui suit celle que l'on vient de distribuer comme nouveau "début" de la liste.
Et comme la carte que l'on vient de distribuer a été sélectionnée de manière aléatoire, le début de la liste devient lui même aléatoire pour la carte à distribuer suivante.
Cela permet d'assurer une distribution plus aléatoire encore des cartes.
Evidemment, rien n'est jamais ni tout à fait blanc, ni tout à fait noir, mais tout se déclie toujours en une mutlitude de gris. Et la liste circulaire ne déroge pas à cette règle.
L'inconvéniant majeur que l'on peut trouver la liste circulaire est que, le dernier élément étant relié au premier, il devient difficile - même si ce n'est pas impossible - de rajouter des éléments en les triant à cette liste en cours d'utilisation.
Il s'agira alors, le plus souvent, de "casser le cercle" avant d'effectuer l'insertion triée de manière, cette fois, tout à fait classique.
Evidemment, cela ne s'applique que si vous voulez réellement avoir une liste triée.
Copyright (©) 2005 (Philippe Dunski)
Ce cours est libre, vous pouvez le redistribuer et/ou le modifier selon les termes de la Licence Publique Générale GNU publiée par la Free Software Foundation (version 2 ou bien toute autre version ultérieure choisie par vous).
Ce cours est distribué car potentiellement utile, mais SANS AUCUNE GARANTIE, ni explicite ni implicite, y compris les garanties de commercialisation ou d'adaptation dans un but spécifique. Reportez-vous à la Licence Publique Générale GNU pour plus de détails.
Cependant, l'auteur apprécierait grandement que vous lui fassiez part de toute modification apportée à son contnu
Vous pouvez le contacter par mail à l'adresse koala01@free.fr
Vous pouvez trouver une adaptation française de la licence GNU/GPL à l'URL http://www.linux-france.org/article/these/gpl.html
