Pourquoi avons-nous besoin d’une structure de données « Circular Linked List » (à elle ou double) ?

Question

Pourquoi avons-nous besoin d’une structure de données « Circular Linked List » (à elle ou double) ?

Quel problème résout-il qui est évident avec de simples listes liées (à elles ou à deux)?

Answer 1

Un exemple simple est de garder une trace de qui c’est le tour dans un jeu de société multijoueur. Mettez tous les joueurs dans une liste circulaire liée. Une fois qu’un joueur a passé à son tour, passez au joueur suivant dans la liste. Cela entraînera le cycle indéfini du programme entre les joueurs.

Pour parcourir une liste circulaire liée, stockez un pointeur vers le premier élément que vous voyez. Lorsque vous voyez à nouveau cet élément, vous avez parcouru toute la liste.

Answer 2

Applications

1) Nous pouvons utiliser une liste circulaire liée à toute application où les entrées apparaissent de manière rotative.
2) La liste circulaire liée est l’idée de base de l’algorithme de planification round robin.

Answer 3

Une liste circulaire liée peut être utilisée efficacement pour créer une file d’attente (FIFO) ou un deque (insertion et suppression efficaces de l’avant et de l’arrière). Voir http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked