Liste circulaire chaînée : avantages et inconvénients

Qu'est-ce qu'une liste circulaire chaînée ?

Une liste chaînée circulaire est une séquence de nœuds disposés de telle manière que chaque nœud puisse être retracé jusqu'à lui-même. Ici, un « nœud » est un élément auto-référentiel avec des pointeurs vers un ou deux nœuds à proximité immédiate.

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

Ici, vous pouvez voir que chaque nœud est retraçable à lui-même. L’exemple présenté ci-dessus est une liste circulaire à chaînage unique.

Remarque : La liste chaînée circulaire la plus simple est un nœud qui ne trace que vers lui-même, comme indiqué.

Basic Operation dans les listes circulaires liées

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 consistant à placer un nœud à une position spécifiée dans la liste chaînée circulaire.
• La suppression est le processus de suppression d'un nœud existant de la liste chaînée. Le nœud peut être identifié par l'occurrence de sa valeur ou par sa position.
• La traversée d'une liste chaînée circulaire est le processus d'affichage de l'intégralité du contenu de la liste chaîné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 à chaînage unique.

Insertion Operaproduction

Initialement, 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 à la valeur de son élément.

Pour l'insertion au début/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 prochain pointeur du nouveau nœud sera lié au nœud existant.
• Le prochain pointeur du dernier nœud pointera vers le nœud inséré.

REMARQUE : Le pointeur qui est le maître du jeton ou le début/fin du cercle peut être modifié. Il reviendra toujours au même nœud lors d'une traversée, discutée 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 un lien direct (d'un nouveau nœud vers un nœud existant)

ÉTAPE 3) Créer un lien de 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 rompre 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 du dispositif reste inchangé. Tous les nœuds sont retraçables à eux-mêmes.

REMARQUE : Puisqu'il existe un arrangement 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 illustré 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.

Suppression Operaproduction

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

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

Suppression au début/fin :

1. Traversez le premier nœud à partir du dernier nœud.
2. Pour supprimer depuis la fin, il ne doit y avoir qu’une seule étape de parcours, 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) Supprimer 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. Traverser jusqu'au nœud suivant est 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.

Parcours d'une liste chaînée circulaire

Pour parcourir une liste chaîné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 chaîné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 libéré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. Algorithms telle que la planification Round Robin peut éliminer proprement les processus qui sont mis en file d'attente de manière circulaire sans rencontrer de pointeurs pendants ou de référence NULL.
3. La liste chaînée circulaire remplit également toutes les fonctions régulières d’une liste chaînée unique. En fait, circulaire listes doublement chaînées discuté ci-dessous peut même éliminer le besoin d’un parcours complet pour localiser un élément. Cet élément serait tout au plus exactement opposé au début, ne complétant que la moitié de la liste chaînée.

Inconvénients de la liste chaînée circulaire

Les inconvénients de l’utilisation d’une liste chaînée circulaire sont les suivants :

1. Les listes circulaires sont complexes par rapport à listes à chaînage unique.
2. RevLe contraire d'une liste circulaire est plus complexe que les listes simples ou doubles.
3. S’il n’est pas manipulé avec soin, le code peut alors suivre une boucle infinie.
4. Plus difficile de trouver la fin de la liste et le contrôle de la boucle.
5. En insérant au début, nous devons parcourir la liste complète pour trouver le dernier nœud. (Perspective de mise en œuvre)

Liste chaînée unique en tant que liste chaîné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<stdio.h>
#include<stdlib.h>

struct 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 de manière répétée à des objets de structure du même type.
4. Il existe différents prototypes de fonctions pour :
   1. Ajouter un élément à une liste chaînée vide
   2. Insertion au actuellement pointé position d’une liste chaînée circulaire.
   3. Insérer après un point particulier indexé valeur dans la liste chaînée.
   4. Supprimer/Supprimer après un certain temps indexé valeur 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 via 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 temporaire.
3. Attribuer et lier 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 qui contient le dernier résultat parcouru.
3. Ce n’est qu’alors que la prochaine traversée pourra avoir lieu.
4. Si les données sont trouvées ou si temp revient au 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 redonnez le contrôle à l'appelant.
2. Si un nœud est trouvé et/ou si le nœud n'est pas encore le dernier nœud, créez un nouveau nœud.
3. Lien le nœud précédent avec le nouveau nœud. Liez le nœud actuel avec temp (la variable de parcours).
4. Cela garantit que l'élément est placé après un nœud particulier dans la liste chaîné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 ne traverse qu'un seul lien vers l'avant.
3. Liez le dernier pointeur au pointeur après le premier.
4. Libérez le pointeur de température. Il libère 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 aucun élément. Si cela est vrai, aucun élément ne peut être supprimé.
2. Pointers 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écédent derrière la température)
4. Le processus continue jusqu'à ce qu'un élément soit trouvé ou 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 est trouvé après avoir parcouru toute la liste chaînée, un message d'erreur s'affiche indiquant que l'élément n'a pas été trouvé.
2. Sinon, l'élément est délié 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 le parcours n'est pas possible s'il n'y en a aucun nécessaire. 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 le parcourir, 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 le temp imprime tous les éléments 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 d'une planification circulaire dans les processus système et d'une planification circulaire dans les graphiques à grande vitesse.
• Planification des anneaux à jetons dans les réseaux informatiques.
• Il est utilisé dans les unités d'affichage telles que les tableaux d'affichage qui nécessitent un parcours continu des données.