Structure de données - Liste liée circulaire

La liste liée circulaire est une variante de la liste liée dans laquelle le premier élément pointe vers le dernier élément et le dernier élément pointe vers le premier élément. La liste à liaison unique et la liste à liaison double peuvent être transformées en une liste liée circulaire.

Liste à lien unique en tant que circulaire

Dans une liste à liaison unique, le pointeur suivant du dernier nœud pointe vers le premier nœud.

Liste doublement liée en tant que circulaire

Dans une liste doublement liée, le pointeur suivant du dernier nœud pointe vers le premier nœud et le pointeur précédent du premier nœud pointe vers le dernier nœud faisant la circulaire dans les deux sens.

Conformément à l'illustration ci-dessus, voici les points importants à considérer.

  • Le prochain lien du dernier lien pointe vers le premier lien de la liste dans les deux cas de liste simple et double.

  • Le précédent du premier lien pointe vers le dernier de la liste en cas de liste doublement liée.

Opérations de base

Voici les opérations importantes soutenues par une liste circulaire.

  • insert - Insère un élément au début de la liste.

  • delete - Supprime un élément du début de la liste.

  • display - Affiche la liste.

Opération d'insertion

Le code suivant illustre l'opération d'insertion dans une liste liée circulaire basée sur une seule liste liée.

Exemple

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

Opération de suppression

Le code suivant illustre l'opération de suppression dans une liste liée circulaire basée sur une seule liste liée.

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

Fonctionnement de la liste d'affichage

Le code suivant illustre l'opération d'affichage de la liste dans une liste liée circulaire.

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

Pour connaître son implémentation en langage de programmation C, veuillez cliquer ici .