Liste circulaire liée: avantages avec l'exemple de programme C

Qu'est-ce qu'une liste liée circulaire?

Une liste chaînée circulaire est une séquence de nœuds disposés de telle sorte que chaque nœud puisse être retracé sur lui-même. Ici, un "nœud" est un élément autoréférentiel avec des pointeurs vers un ou deux nœuds dans le voisinage immédiat de iI.

Vous trouverez ci-dessous une représentation d'une liste chaînée circulaire à 3 nœuds.

Ici, vous pouvez voir que chaque nœud est retracable sur lui-même. L'exemple ci-dessus est une liste circulaire à lien unique.

Remarque: la liste chaînée circulaire la plus simple est un nœud qui se trace uniquement vers lui-même comme indiqué

Dans ce didacticiel sur les listes liées circulaires, vous apprendrez:

• Qu'est-ce qu'une liste liée circulaire?
• Opérations de base
• Opération d'insertion
• Opération de suppression
• Traversée d'une liste liée circulaire
• Avantages de la liste liée circulaire
• Liste à lien unique en tant que liste liée circulaire
• Applications de la liste circulaire liée

Opérations de base

Les opérations de base sur une liste chaînée circulaire sont:

1. Insertion
2. Suppression et
3. Traversée

• L'insertion est le processus de placement d'un nœud à une position spécifiée dans la liste liée circulaire.
• La suppression est le processus de suppression d'un nœud existant de la liste liée. Le nœud peut être identifié par l'occurrence de sa valeur ou par sa position.
• La traversée d'une liste liée circulaire est le processus d'affichage de l'intégralité du contenu de la liste liée et de retour au nœud source.

Dans la section suivante, vous comprendrez l'insertion d'un nœud et les types d'insertion possibles dans une liste circulaire à lien unique.

Opération d'insertion

Au départ, vous devez créer un nœud qui pointe vers lui-même, comme indiqué dans cette image. Sans ce nœud, l'insertion crée le premier nœud.

Ensuite, il y a deux possibilités:

• Insertion à la position actuelle de la liste chaînée circulaire. Cela correspond à l'insertion au début de la fin d'une liste chaînée singulière régulière. Dans une liste chaînée circulaire, le début et la fin sont identiques.
• Insertion après un nœud indexé. Le nœud doit être identifié par un numéro d'index correspondant à sa valeur d'élément.

Pour l'insertion au début / à la fin de la liste chaînée circulaire, c'est-à-dire à la position où le tout premier nœud a été ajouté,

• Vous devrez rompre l'auto-lien existant vers le nœud existant
• Le pointeur suivant du nouveau nœud sera lié au nœud existant.
• Le pointeur suivant du dernier nœud pointera vers le nœud inséré.

REMARQUE: le pointeur qui est le maître de jeton ou le début / la fin du cercle peut être modifié. Il reviendra toujours au même nœud lors d'un parcours, discuté plus loin.

Les étapes de (a) i-iii sont indiquées ci-dessous:

(Nœud existant)

ÉTAPE 1) Rompre le lien existant

ÉTAPE 2) Créer une liaison directe (du nouveau nœud vers un nœud existant)

ÉTAPE 3) Créez un lien en boucle vers le premier nœud

Ensuite, vous essaierez l'insertion après un nœud.

Par exemple, insérons "VALUE2" après le nœud avec "VALUE0". Supposons que le point de départ soit le nœud avec "VALUE0".

• Vous devrez casser la ligne entre le premier et le deuxième nœud et placer le nœud avec "VALUE2" entre les deux.
• Le pointeur suivant du premier nœud doit être lié à ce nœud, et le pointeur suivant de ce nœud doit être lié au deuxième nœud précédent.
• Le reste de l'arrangement reste inchangé. Tous les nœuds sont retracables sur eux-mêmes.

REMARQUE: comme il existe une disposition cyclique, l'insertion d'un nœud implique la même procédure pour n'importe quel nœud. Le pointeur qui termine un cycle termine le cycle comme n'importe quel autre nœud.

Ceci est montré ci-dessous:

(Disons qu'il n'y a que deux nœuds. C'est un cas trivial)

ÉTAPE 1) Supprimez le lien interne entre les nœuds connectés

ÉTAPE 2) Connectez le nœud de gauche au nouveau nœud

ÉTAPE 3) Connectez le nouveau nœud au nœud de droite.

Opération de suppression

Supposons une liste chaînée circulaire à 3 nœuds. Les cas de suppression sont indiqués ci-dessous:

• Suppression de l'élément actuel
• Suppression après un élément.

Suppression au début / à la fin:

1. Traversez le premier nœud à partir du dernier nœud.
2. Pour supprimer à partir de la fin, il ne doit y avoir qu'une seule étape de traversée, du dernier nœud au premier nœud.
3. Supprimez le lien entre le dernier nœud et le nœud suivant.
4. Liez le dernier nœud à l'élément suivant du premier nœud.
5. Libérez le premier nœud.

(Configuration existante)

ÉTAPE 1 ) Retirez le lien circulaire

ÉTAPES 2) Supprimez le lien entre le premier et le suivant, liez le dernier nœud, au nœud suivant le premier

ÉTAPE 3) Libérer / désallouer le premier nœud

Suppression après un nœud:

1. Traversez jusqu'à ce que le nœud suivant soit le nœud à supprimer.
2. Passez au nœud suivant, en plaçant un pointeur sur le nœud précédent.
3. Connectez le nœud précédent au nœud après le nœud actuel, en utilisant son pointeur suivant.
4. Libérez le nœud actuel (dissocié).

ÉTAPE 1) Disons que nous devons supprimer un nœud avec "VALUE1".

ÉTAPE 2) Supprimez le lien entre le nœud précédent et le nœud actuel. Liez son nœud précédent au nœud suivant pointé par le nœud actuel (avec VALUE1).

ÉTAPE 3) Libérez ou désallouez le nœud actuel.

Traversée d'une liste liée circulaire

Pour parcourir une liste liée circulaire, à partir d'un dernier pointeur, vérifiez si le dernier pointeur lui-même est NULL. Si cette condition est fausse, vérifiez s'il n'y a qu'un seul élément. Sinon, parcourez à l'aide d'un pointeur temporaire jusqu'à ce que le dernier pointeur soit à nouveau atteint, ou autant de fois que nécessaire, comme indiqué dans le GIF ci-dessous.

Avantages de la liste liée circulaire

Certains des avantages des listes chaînées circulaires sont:

1. Aucune exigence pour une affectation NULL dans le code. La liste circulaire ne pointe jamais vers un pointeur NULL à moins qu'elle ne soit entièrement désallouée.
2. Les listes chaînées circulaires sont avantageuses pour les opérations de fin puisque le début et la fin coïncident. Des algorithmes tels que l'ordonnancement Round Robin peuvent éliminer proprement les processus qui sont mis en file d'attente de manière circulaire sans rencontrer de pointeurs pendants ou référentiels NULL.
3. La liste liée circulaire remplit également toutes les fonctions régulières d'une liste liée individuellement. En fait, les listes circulaires à double lien discutées ci-dessous peuvent même éliminer le besoin d'un parcours complet pour localiser un élément. Cet élément ne serait au plus que exactement opposé au début, ne complétant que la moitié de la liste chaînée.

Liste liée individuellement en tant que liste liée circulaire

Nous vous encourageons à essayer de lire et d'implémenter le code ci-dessous. Il présente l'arithmétique des pointeurs associée aux listes chaînées circulaires.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){… 

Explication du code:

1. Les deux premières lignes de code sont les fichiers d'en-tête inclus nécessaires.
2. La section suivante décrit la structure de chaque nœud autoréférentiel. Il contient une valeur et un pointeur du même type que la structure.
3. Chaque structure est liée à plusieurs reprises à des objets de structure du même type.
4. Il existe différents prototypes de fonctions pour:
   1. Ajout d'un élément à une liste chaînée vide
   2. Insertion à la position actuellement pointée d'une liste chaînée circulaire.
   3. Insertion après une valeur indexée particulière dans la liste chaînée.
   4. Suppression / Suppression après une valeur indexée particulière dans la liste chaînée.
   5. Suppression à la position actuellement pointée d'une liste chaînée circulaire
5. La dernière fonction imprime chaque élément par un parcours circulaire à n'importe quel état de la liste chaînée.

int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Explication du code:

1. Pour le code addEmpty, allouez un nœud vide à l'aide de la fonction malloc.
2. Pour ce nœud, placez les données dans la variable temp.
3. Assignez et liez la seule variable à la variable temporaire
4. Renvoie le dernier élément au contexte main () / application.

struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;… 

Explication du code

1. S'il n'y a aucun élément à insérer, vous devez vous assurer de l'ajouter à une liste vide et de renvoyer le contrôle.
2. Créez un élément temporaire à placer après l'élément actuel.
3. Liez les pointeurs comme indiqué.
4. Renvoie le dernier pointeur comme dans la fonction précédente.

… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");… 

Explication du code:

1. S'il n'y a aucun élément dans la liste, ignorez les données, ajoutez l'élément actuel comme dernier élément de la liste et renvoyez le contrôle
2. Pour chaque itération de la boucle do-while, assurez-vous qu'il existe un pointeur précédent contenant le dernier résultat parcouru.
3. Ce n'est qu'alors que le prochain parcours peut avoir lieu.
4. Si les données sont trouvées, ou si temp atteint le dernier pointeur, le do-while se termine. La section suivante du code décide de ce qui doit être fait avec l'élément.

… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)… 

Explication du code:

1. Si la liste entière a été parcourue, mais que l'élément n'est pas trouvé, affichez un message "élément non trouvé", puis renvoyez le contrôle à l'appelant.
2. S'il y a un nœud trouvé et / ou si le nœud n'est pas encore le dernier nœud, créez un nouveau nœud.
3. Liez le nœud précédent au nouveau nœud. Liez le nœud actuel à temp (la variable de parcours).
4. Cela garantit que l'élément est placé après un nœud particulier dans la liste liée circulaire. Revenez à l'appelant.

struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Explication du code

1. Pour supprimer uniquement le dernier nœud (actuel), vérifiez si cette liste est vide. Si tel est le cas, aucun élément ne peut être supprimé.
2. La variable temp traverse juste un lien vers l'avant.
3. Liez le dernier pointeur au pointeur après le premier.
4. Libérez le pointeur temporaire. Il désalloue le dernier pointeur non lié.

struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");… 

Explication du code

1. Comme pour la fonction de suppression précédente, vérifiez s'il n'y a pas d'élément. Si tel est le cas, aucun élément ne peut être supprimé.
2. Les pointeurs se voient attribuer des positions spécifiques pour localiser l'élément à supprimer.
3. Les pointeurs sont avancés, les uns derrière les autres. (prévaut derrière la température)
4. Le processus se poursuit jusqu'à ce qu'un élément soit trouvé, ou jusqu'à ce que l'élément suivant revienne au dernier pointeur.

if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Explication du programme

1. Si l'élément trouvé après avoir parcouru toute la liste liée, un message d'erreur s'affiche indiquant que l'élément n'a pas été trouvé.
2. Sinon, l'élément est dissocié et libéré aux étapes 3 et 4.
3. Le pointeur précédent est lié à l'adresse pointée comme "suivant" par l'élément à supprimer (temp).
4. Le pointeur temporaire est donc désalloué et libéré.

… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Explication du code

1. Le coup d'oeil ou la traversée n'est pas possible s'il n'y a aucun besoin. L'utilisateur doit allouer ou insérer un nœud.
2. S'il n'y a qu'un seul nœud, il n'est pas nécessaire de traverser, le contenu du nœud peut être imprimé et la boucle while ne s'exécute pas.
3. S'il y a plus d'un nœud, alors la température imprime tout l'élément jusqu'au dernier élément.
4. Au moment où le dernier élément est atteint, la boucle se termine et la fonction renvoie l'appel à la fonction principale.

Applications de la liste circulaire liée

• Implémentation de la planification circulaire dans les processus système et de la planification circulaire dans les graphiques haute vitesse.
• Programmation des anneaux de jetons dans les réseaux informatiques.
• Il est utilisé dans les unités d'affichage comme les tableaux de bord qui nécessitent une traversée continue des données.