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 agencés de telle sorte que chaque nœud puisse être recréé.tracChaque « nœud » est un élément autoréférentiel comportant des pointeurs vers un ou deux nœuds situés à 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 retraccapable de se relier à elle-même. L'exemple ci-dessus est une liste circulaire simplement chaînée.

Remarque : La liste chaînée circulaire la plus simple est un nœud unique dont le pointeur suivant tracelle revient à elle-même, comme indiqué ci-dessous.

Fonction Plug & Play Operations dans les listes chaînées circulaires

Les trois 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.
• Le parcours d'une liste chaînée circulaire est le processus qui consiste à afficher l'intégralité du contenu de la liste chaînée et à la recréer.tracretour au nœud source.

La section suivante explique le fonctionnement de l'insertion et les deux types d'insertion possibles dans une liste circulaire simplement chaînée.

Insertion Operaproduction

Vous commencez par créer un nœud dont le pointeur suivant pointe vers lui-même, comme illustré ci-dessous. Sans ce nœud initial, la première insertion devient le premier nœud de la liste.

Ensuite, il y a deux possibilités :

• Insertion à la position courante de la liste chaînée circulaire. Cela correspond à une insertion au début ou à la fin d'une liste chaînée simple classique ; dans une liste chaînée circulaire, le début et la fin sont confondus.
• 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 insérer un élément au début ou à la fin de la liste chaînée circulaire — c'est-à-dire à l'endroit où le tout premier nœud a été ajouté — suivez les étapes ci-dessous :

• 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 marquant le début ou la fin du cercle peut être réaffecté à n’importe quel nœud. Le parcours retournera toujours au même nœud, comme expliqué plus loin dans cet article.

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érez « VALEUR2 » après le nœud contenant « VALEUR0 », en supposant que le point de départ soit le nœud contenant « VALEUR0 ».

• Rompre le lien 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 pointe vers le nouveau nœud, et le pointeur suivant du nouveau nœud pointe vers ce qui était auparavant le deuxième nœud.
• Le reste de la configuration demeure inchangé. Tous les nœuds sont réactivés.traccapables par eux-mêmes.

REMARQUE : Puisque la structure est cyclique, la procédure d’insertion d’un nœud est identique quelle que soit sa position. Le pointeur qui ferme la boucle se comporte comme n’importe quel autre pointeur de la liste.

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

Considérons une liste chaînée circulaire à 3 nœuds. Les deux cas de suppression sont les suivants :

• 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. La suppression à partir de la fin ne nécessite qu'un seul parcours, du dernier nœud au premier.
3. Supprimez le lien entre le dernier nœud et le premier nœud.
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

Étape 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. Parcourez le réseau jusqu'à ce que le prochain nœud soit celui à 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, puis liez directement le nœud précédent au nœud pointé par le pointeur suivant du nœud actuel (le nœud après 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 de son dernier pointeur, vérifiez d'abord si ce dernier est nul. S'il ne l'est pas, vérifiez si la liste ne contient qu'un seul élément. Sinon, parcourez la liste à l'aide d'un pointeur temporaire jusqu'à atteindre à nouveau le dernier pointeur, comme illustré dans l'animation 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 de liste car le début et la fin coïncident. Algorithms par exemple, la planification à tour de rôle peut parcourir les processus en file d'attente sans problème, sans rencontrer de pointeurs orphelins ou NULL.
3. Une liste chaînée circulaire prend toujours en charge toutes les opérations habituelles d'une liste simplement chaînée. liste doublement chaînée peut même éliminer la nécessité d'un parcours complet pour localiser un élément — dans le pire des cas, la cible se trouve à l'opposé du pointeur de départ, donc au maximum la moitié de la liste doit être parcourue.

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 plus complexes que listes à chaînage unique.
2. RevInverser une liste circulaire est plus complexe qu'inverser une liste simplement ou doublement chaînée.
3. Si la terminaison de la boucle n'est pas gérée avec soin, le code de parcours peut entrer dans une boucle infinie.
4. Il est plus difficile de trouver la fin de la liste et d'écrire correctement les conditions de contrôle de boucle.
5. L'insertion au début nécessite de parcourir toute la liste pour atteindre le dernier nœud (du point de vue de l'implémentation).

Liste chaînée unique en tant que liste chaînée circulaire

Nous vous encourageons à lire et à implémenter le code C ci-dessous. Il illustre l'arithmétique des pointeurs associée à une liste simplement chaînée circulaire.

#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éfinit la structure de chaque nœud autoréférentiel. Elle contient une valeur et un pointeur du même type que la structure.
3. Chaque instance de structure est liée à d'autres 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 addToEmpty, allouez un nœud vide à l'aide de la fonction malloc().
2. Placez les données entrantes dans le nœud temporaire.
3. Attribuez le nœud temporaire à la dernière position et définissez son pointeur suivant sur lui-même afin que le nœud unique pointe vers lui-même.
4. Renvoie le dernier pointeur vers la fonction main() / le contexte de l'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. Si la liste est vide, passez le relais à addToEmpty() et rendez le contrôle.
2. Créez un nœud temporaire à placer après le nœud actuel.
3. Reliez les pointeurs comme indiqué dans le schéma ci-dessus.
4. Renvoie le dernier pointeur correspondant au modèle utilisé 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. Si la liste est vide, ignorez la clé de recherche, ajoutez l'élément actuel comme seul nœud de la liste et rendez le contrôle.
2. À chaque itération de la boucle do-while, un pointeur précédent contient le dernier résultat parcouru.
3. Ce n'est qu'alors que l'étape de parcours suivante a lieu.
4. La boucle do-while s'arrête lorsque les données cibles sont trouvées ou lorsque la variable temp atteint à nouveau la dernière position du pointeur. Le bloc de code suivant détermine le traitement à effectuer avec l'élément trouvé.

...
    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 est introuvable, affichez un message « Élément introuvable » et rendez le contrôle à l'appelant.
2. Si le nœud cible est trouvé, allouez un nouveau nœud pour la valeur à insérer.
3. Lien relier le nœud précédent au nouveau nœud et lier le pointeur suivant du nouveau nœud à temp (la variable de parcours).
4. Cela place le nouvel élément immédiatement après le nœud cible dans la liste chaînée circulaire. Le contrôle est ensuite rendu à 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 le dernier nœud (actuel), vérifiez d'abord si la liste est vide. Si c'est le cas, aucun élément ne peut être supprimé.
2. La variable temporaire fait avancer d'un maillon.
3. Liez le dernier pointeur au nœud suivant le premier nœud.
4. Libérez le pointeur temporaire pour désallouer le nœud 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 d'abord si la liste est vide. Si c'est le cas, aucun élément ne peut être supprimé.
2. Deux Pointeurs se voient attribuer des positions spécifiques pour localiser l’élément à supprimer.
3. Les pointeurs sont avancés l'un derrière l'autre (température des sentiers précédents).
4. Le parcours se poursuit jusqu'à ce que l'élément cible soit trouvé ou que le pointeur suivant atteigne à nouveau le dernier nœud.

    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 la liste chaînée entière est parcourue sans trouver la cible, un message « Élément introuvable » s’affiche.
2. Sinon, l'élément est délié et libéré aux étapes 3 et 4.
3. Le pointeur précédent est lié au nœud pointé par le pointeur suivant de temp (le nœud suivant celui qui est supprimé).
4. Le pointeur temporaire est alors 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 parcours par aperçu n'est pas possible s'il n'y a aucun nœud ; l'utilisateur doit d'abord allouer ou insérer un nœud.
2. S'il n'y a qu'un seul nœud, aucun parcours n'est nécessaire : le contenu du nœud est imprimé directement et la boucle while n'est pas exécutée.
3. S'il y a plus d'un nœud, temp affiche chaque élément jusqu'au dernier.
4. Dès que le dernier élément est atteint, la boucle se termine et la fonction rend le contrôle à main().

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.
• Ordonnancement par anneau à jeton dans les réseaux informatiques.
• Utilisé dans les dispositifs d'affichage tels que les panneaux numériques de magasins qui nécessitent un défilement continu des données.

FAQ