circular linked list data structure c with illustration
Un aperçu complet de la liste liée circulaire.
Une liste liée circulaire est une variante de la liste liée. C'est une liste chaînée dont les nœuds sont connectés de manière à former un cercle.
Dans la liste chaînée circulaire, le pointeur suivant du dernier nœud n'est pas mis à zéro mais il contient l'adresse du premier nœud formant ainsi un cercle.
=> Visitez ici pour apprendre le C ++ à partir de zéro.
Ce que vous apprendrez:
Liste liée circulaire en C ++
La disposition ci-dessous est pour une liste liée individuellement.
Une liste liée circulaire peut être une liste liée individuellement ou une liste doublement liée. Dans une liste chaînée doublement circulaire, le pointeur précédent du premier nœud est connecté au dernier nœud tandis que le pointeur suivant du dernier nœud est connecté au premier nœud.
Sa représentation est indiquée ci-dessous.
Déclaration
Nous pouvons déclarer un nœud dans une liste liée circulaire comme n'importe quel autre nœud, comme indiqué ci-dessous:
struct Node { int data; struct Node *next; }; Afin d'implémenter la liste chaînée circulaire, nous maintenons un pointeur externe «dernier» qui pointe vers le dernier nœud de la liste chaînée circulaire. Par conséquent, last-> next pointera vers le premier nœud de la liste chaînée.
En faisant cela, nous nous assurons que lorsque nous insérons un nouveau nœud au début ou à la fin de la liste, nous n'avons pas besoin de parcourir toute la liste. C'est parce que le dernier pointe vers le dernier nœud tandis que last-> next pointe vers le premier nœud.
Cela n’aurait pas été possible si nous avions pointé le pointeur externe sur le premier nœud.
Opérations de base
La liste liée circulaire prend en charge l'insertion, la suppression et le parcours de la liste. Nous allons maintenant discuter de chacune des opérations en détail.
Insertion
Nous pouvons insérer un nœud dans une liste chaînée circulaire soit en tant que premier nœud (liste vide), au début, à la fin ou entre les autres nœuds. Voyons chacune de ces opérations d'insertion à l'aide d'une représentation picturale ci-dessous.
# 1) Insérer dans une liste vide
Lorsqu'il n'y a pas de nœuds dans la liste circulaire et que la liste est vide, le dernier pointeur est nul, alors nous insérons un nouveau nœud N en pointant le dernier pointeur vers le nœud N comme indiqué ci-dessus. Le pointeur suivant de N pointera vers le nœud N lui-même car il n'y a qu'un seul nœud. Ainsi N devient le premier et le dernier nœud de la liste.
# 2) Insérer au début de la liste
Comme le montre la représentation ci-dessus, lorsque nous ajoutons un nœud au début de la liste, le pointeur suivant du dernier nœud pointe vers le nouveau nœud N, ce qui en fait un premier nœud.
N-> suivant = dernier-> suivant
Dernier-> suivant = N
# 3) Insérer à la fin de la liste
Pour insérer un nouveau nœud à la fin de la liste, nous suivons ces étapes:
questions d'entretien sur html5 et css3
N-> suivant = dernier -> suivant;
dernier -> suivant = N
dernier = N
# 4) Insérer entre la liste
Supposons que nous ayons besoin d'insérer un nouveau nœud N entre N3 et N4, nous devons d'abord parcourir la liste et localiser le nœud après lequel le nouveau nœud doit être inséré, dans ce cas, son N3.
Une fois le nœud localisé, nous exécutons les étapes suivantes.
N -> suivant = N3 -> suivant;
N3 -> suivant = N
Ceci insère un nouveau nœud N après N3.
Effacement
L'opération de suppression de la liste chaînée circulaire consiste à localiser le nœud à supprimer puis à libérer sa mémoire.
Pour cela, nous maintenons deux pointeurs supplémentaires curr et prev puis parcourons la liste pour localiser le nœud. Le nœud donné à supprimer peut être le premier nœud, le dernier nœud ou le nœud intermédiaire. En fonction de l'emplacement, nous définissons les pointeurs curr et prev, puis supprimons le nœud curr.
Une représentation graphique de l'opération de suppression est présentée ci-dessous.
Traversée
La traversée est une technique de visite de chaque nœud. Dans les listes chaînées linéaires comme les listes chaînées simples et les listes doublement liées, la traversée est facile car nous visitons chaque nœud et nous nous arrêtons lorsque NULL est rencontré.
Cependant, cela n'est pas possible dans une liste chaînée circulaire. Dans une liste chaînée circulaire, nous partons du suivant du dernier nœud qui est le premier nœud et traversons chaque nœud. Nous nous arrêtons lorsque nous atteignons à nouveau le premier nœud.
Nous présentons maintenant une implémentation des opérations de liste chaînée circulaire utilisant C ++ et Java. Nous avons implémenté ici des opérations d'insertion, de suppression et de parcours. Pour une compréhension claire, nous avons représenté la liste chaînée circulaire comme
Ainsi, au dernier noeud 50, on attache à nouveau le noeud 10 qui est le premier noeud, l'indiquant ainsi comme une liste chaînée circulaire.
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout < data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '< Production:
La liste liée circulaire créée est la suivante:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Le nœud avec les données 10 est supprimé de la liste
La liste liée circulaire après la suppression de 10 est la suivante:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
Ensuite, nous présentons une implémentation Java pour les opérations de liste chaînée circulaire.
//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print('
'); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf('
Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } } Production:
La liste liée circulaire créée est:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Après avoir supprimé 40, la liste circulaire est:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Avantages désavantages
Laissez-nous discuter de certains avantages et inconvénients de la liste chaînée circulaire.
Avantages:
- Nous pouvons aller à n'importe quel nœud et traverser à partir de n'importe quel nœud. Nous devons simplement nous arrêter lorsque nous visitons à nouveau le même nœud.
- Lorsque le dernier nœud pointe vers le premier nœud, aller au premier nœud à partir du dernier nœud ne prend qu'une seule étape.
Désavantages:
- L'inversion d'une liste liée circulaire est fastidieuse.
- Comme les nœuds sont connectés pour former un cercle, il n'y a pas de marquage approprié pour le début ou la fin de la liste. Par conséquent, il est difficile de trouver la fin de la liste ou du contrôle de boucle. Si cela n'est pas fait, une implémentation peut se retrouver dans une boucle infinie.
- Nous ne pouvons pas revenir au nœud précédent en une seule étape. Nous devons parcourir toute la liste depuis le début.
Applications de la liste liée circulaire
- L'application en temps réel de la liste liée circulaire peut être un système d'exploitation à programmation multiple dans lequel il planifie plusieurs programmes. Chaque programme reçoit un horodatage dédié à exécuter, après quoi les ressources sont transmises à un autre programme. Cela continue en continu dans un cycle. Cette représentation peut être réalisée efficacement en utilisant une liste chaînée circulaire.
- Les parties jouées avec plusieurs joueurs peuvent également être représentées à l'aide d'une liste liée circulaire dans laquelle chaque joueur est un nœud qui a la possibilité de jouer.
- Nous pouvons utiliser une liste chaînée circulaire pour représenter une file d'attente circulaire. En faisant cela, nous pouvons supprimer les deux pointeurs avant et arrière qui sont utilisés pour la file d'attente. Au lieu de cela, nous ne pouvons utiliser qu'un seul pointeur.
Conclusion
Une liste liée circulaire est une collection de nœuds dans laquelle les nœuds sont connectés les uns aux autres pour former un cercle. Cela signifie qu'au lieu de définir le pointeur suivant du dernier nœud sur null, il est lié au premier nœud.
Une liste chaînée circulaire est utile pour représenter des structures ou des activités qui doivent être répétées encore et encore après un intervalle de temps spécifique, comme des programmes dans un environnement de multiprogrammation. Il est également avantageux pour la conception d'une file d'attente circulaire.
Les listes liées circulaires prennent en charge diverses opérations telles que l'insertion, la suppression et les traversées. Ainsi, nous avons vu les opérations en détail dans ce tutoriel.
Dans notre prochain sujet sur les structures de données, nous découvrirons la structure de données de la pile.
=> Vérifiez ici pour voir de A à Z des didacticiels de formation C ++ ici.
lecture recommandée
- Structure de données de liste liée en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
- Structure de données de file d'attente en C ++ avec illustration
- Empiler la structure de données en C ++ avec illustration
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Top 15 des meilleurs outils d'exploration de données gratuits: la liste la plus complète
- Introduction aux structures de données en C ++
- 15 meilleurs outils ETL en 2021 (une liste complète mise à jour)