Structure de données - Liste chaînée circulaire
Une liste chaînée circulaire est une variante de la structure de liste chaînée. Sa caractéristique principale est que le dernier nœud de la liste chaînée ne pointe plus vers NULL, mais pointe en retour vers le premier nœud, ce qui fait que toute la liste chaînée forme logiquement une structure en anneau.
Caractéristiques structurelles de la liste chaînée circulaire
Liste chaînée circulaire simple
Liste doublement chaînée circulaire
Liste chaînée ordinaire : le next de fin = NULL, la condition d'arrêt du parcours est cur == NULL
Liste chaînée circulaire : le next de fin = head, la condition d'arrêt du parcours est cur == head (retour au point de départ)
Opérations courantes :Insérer un nœud en tête O(n) — il faut d'abord trouver le nœud de queue | le parcours utilise une boucle do...while
Insérer un nœud en queue O(1) (maintenir le pointeur de queue) | suppression de la même manière
Les listes chaînées circulaires se divisent principalement en deux types :
- Liste chaînée circulaire simple: chaque nœud ne stocke qu'un seul pointeur next, et le next du dernier nœud pointe de nouveau vers le nœud de tête
- Liste doublement chaînée circulaire: basée sur la liste doublement chaînée, le next du dernier nœud pointe vers le nœud de tête, et le prev du nœud de tête pointe vers le dernier nœud
La plus grande caractéristique de la structure de liste chaînée circulaire est qu’elle prend naturellement en charge un parcours continu où la fin se reconnecte au début.
La condition pour déterminer la fin du parcours n’est pas "si NULL est atteint", mais "si l’on revient au nœud de départ".
Opérations de base
Exemple
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Créer un nouveau nœud */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* Pour un nœud unique, next pointe vers lui-même, formant une auto-boucle */
return newNode;
}
/* Insérer un nœud en tête de la liste chaînée circulaire
Complexité temporelle : O(n) — il faut d'abord trouver le nœud de queue pour mettre à jour son pointeur next */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* Liste chaînée vide, le nouveau nœud forme une auto-boucle */
}
/* Trouver le nœud de queue (c'est-à-dire le nœud dont next pointe vers head) */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* Le champ next du nouveau nœud pointe vers le nœud de tête d'origine */
tail->next = newNode; /* Le champ next du nœud de queue pointe vers le nouveau nœud (nouvelle tête) */
return newNode; /* Le nouveau nœud devient le nouveau nœud de tête */
}
/* Parcourir la liste chaînée circulaire (un cycle)
Commencer au nœud de tête, s'arrêter en revenant au nœud de tête */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("Liste chaînée circulaire : ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* Arrêt lorsqu'on revient au point de départ */
printf("(retour au départ)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* Sortie : Liste chaînée circulaire : 10 -> 20 -> 30 -> (retour au départ) */
return 0;
}
La clé pour parcourir une liste chaînée circulaire est d'utiliser
do...whileinstruction au lieu dewhile. Parce que lorsqu'on utilisewhile (cur != head), l'état initial de cur est égal à head, et la boucle ne s'exécutera pas du tout. Etdo...whilegarantit que le corps de la boucle est exécuté au moins une fois, puis vérifie la condition d'arrêt.
Application classique : problème de l'anneau de Josèphe
Ordre d'élimination et résultat final (n=7, m=3)
Problème de l'anneau de Josèphe (problème de Josèphe)est un problème mathématique classique :
Supposons que n personnes se tiennent en cercle. Le comptage commence à partir de la 1re personne, et chaque m-ième personne est éliminée du cercle. Ensuite, le comptage reprend à partir de la personne suivante, et cela continue jusqu'à ce qu'il ne reste que la dernière personne.
Ce problème correspond naturellement aux caractéristiques structurelles d'une liste chaînée circulaire : « reliée de bout en bout, parcourue cycliquement. »
Exemple
#include <stdlib.h>
struct Node {
int data; /* Numéro de la personne */
struct Node* next;
};
/* Solution de l'anneau de Josephus
Paramètres : n nombre total de personnes, m chaque m-ième personne comptée quitte le cercle
Utiliser une liste chaînée circulaire pour simuler l'ensemble du processus */
void josephus(int n, int m) {
if (n <= 0) return;
/* Étape 1 : Créer une liste chaînée circulaire contenant n personnes (numérotées 1~n) */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* Lorsqu'il n'y a qu'une seule personne, cela forme une auto-boucle */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* Le champ next du nouveau nœud pointe toujours vers head */
tail->next = newNode; /* Le next du nœud précédent pointe vers le nouveau nœud */
tail = newNode; /* Avancer tail */
}
/* Étape 2 : Simuler le processus d'élimination */
struct Node* cur = head;
struct Node* prev = tail; /* prev pointe vers le prédécesseur de cur, initialement le nœud tail */
printf("Ordre d'élimination de l'anneau de Josephus (n=%d, m=%d) : ", n, m);
while (cur->next != cur) { /* Fin lorsqu'il ne reste qu'un seul nœud (auto-boucle) */
/* Comptage : compter m-1 fois, en avançant prev et cur simultanément */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* Lorsque le compteur atteint m, cur est éliminé */
printf("%d ", cur->data);
prev->next = cur->next; /* Sauter cur */
free(cur); /* Libérer le nœud éliminé */
cur = prev->next; /* Redémarrer le comptage à partir de la personne suivante */
}
printf("=> Dernier survivant : %d\n", cur->data); /* Afficher la dernière personne */
free(cur);
}
int main() {
josephus(7, 3);
/* Sortie : anneau de Josephus (n=7, m=3) ordre d'élimination : 3 6 2 7 5 1 => Dernier survivant : 4 */
return 0;
}
Autres scénarios d'application
| Scénario | Description |
|---|---|
| Ordonnancement par tranches de temps en tourniquet du système d'exploitation | Le CPU alloue des tranches de temps à chaque processus à tour de rôle. Lorsqu'un processus épuise sa tranche de temps, le processus suivant prend son tour, formant un cycle. |
| Jeux multijoueurs où l'on joue aux cartes à tour de rôle | Dans les jeux de plateau et de cartes, les joueurs agissent à tour de rôle dans le sens horaire (ou antihoraire). |
| Tampon circulaire | Un tampon circulaire pour les flux de données audio/vidéo ; lorsqu'il est plein, il revient au début et écrase les anciennes données. |