Qu’est-ce qu’une liste liée circulaire ?
La liste chaînée circulaire est une liste chaînée où tous les nœuds sont connectés pour former un cercle. Dans une liste chaînée circulaire, le premier nœud et le dernier nœud sont connectés l’un à l’autre, ce qui forme un cercle. Il n’y a pas de NULL à la fin.
Il existe généralement deux types de listes circulaires chaînées :
- Liste circulaire à liaison simple : dans une liste circulaire à liaison simple, le dernier nœud de la liste contient un pointeur vers le premier nœud de la liste. Nous parcourons la liste circulaire simplement liée jusqu’à ce que nous atteignions le même nœud où nous avons commencé. La liste circulaire simple chaînée n’a ni début ni fin. Aucune valeur nulle n’est présente dans la partie suivante de l’un des nœuds.
Représentation de la liste circulaire à liens simples
- Liste circulaire doublement liée: La liste circulaire doublement liée a des propriétés à la fois de liste doublement liée et de liste circulaire liée dans laquelle deux éléments consécutifs sont liés ou connectés par le pointeur précédent et suivant et le dernier nœud pointe vers le premier nœud par le pointeur suivant et aussi le premier nœud pointe vers le dernier nœud par le pointeur précédent.
Représentation d’une liste circulaire doublement chaînée
Remarque : Nous utiliserons la liste liée circulaire unique pour représenter le fonctionnement de la liste liée circulaire.
Représentation de la liste chaînée circulaire :
Les listes liées circulaires sont similaires aux listes liées simples, à l’exception de la connexion du dernier nœud au premier nœud.
Représentation des nœuds d’une liste circulaire liée :
C
structNode { intdata; structNode *next;}; |
C++
// Class Node, similar to the linked listclassNode{ intvalue;// Points to the next node. Node next;} |
Python3
# Class Node, similar to the linked listclassNode: def__init__(self,data): self.data =data self.next=None |
Java
publicclassNode { intdata; Node next; publicNode(intdata) { this.data = data; this.next = null; }} |
C#
publicclassNode{ publicintdata; publicNode next; publicNode(intdata) { this.data = data; this.next = null; }} |
Javascript
class Node { constructor(data) { this.data = data; this.next = null; }} |
PHP
classNode { public$data; public$next; function__construct($data) { $this->data = $data; $this->next = null; }} |
Exemple de liste circulaire à liens simples :
Exemple de liste chaînée circulaire
La liste circulaire simple ci-dessus peut être représentée comme suit :
C
Node* one = createNode(3);Node* two = createNode(5);Node* three = createNode(9);// Connect nodesone->next = two;two->next = three;three->next = one; |
C++
// Initialize the Nodes.Node one = newNode(3);Node two = newNode(5);Node three = newNode(9);// Connect nodesone.next = two;two.next = three;three.next = one; |
Python3
# Initialize the Nodes.one =Node(3)two =Node(5)three =Node(9)# Connect nodesone.next=twotwo.next=threethree.next=one |
Java
// Define the Node classclassNode { intvalue; Node next; publicNode(intvalue) { this.value = value; }}// Initialize the Nodes.Node one = newNode(3);Node two = newNode(5);Node three = newNode(9);// Connect nodesone.next = two;two.next = three;three.next = one; |
C#
Node one = newNode(3);Node two = newNode(5);Node three = newNode(9);// Connect nodesone.next = two;two.next = three;three.next = one; |
Javascript
let one = newNode(3);let two = newNode(5);let three = newNode(9);// Connect nodesone.next = two;two.next = three;three.next = one; |
PHP
$one= newNode(3);$two= newNode(5);$three= newNode(9);// Connect nodes$one->next = $two;$two->next = $three;$three->next = $one; |
Explication : Dans le programme ci-dessus, un, deux et trois sont les nœuds avec les valeurs 3, 5 et 9 respectivement qui sont connectés de manière circulaire comme :
- Pour le nœud un : le pointeur Next stocke l’adresse du nœud deux.
- Pour le nœud deux : le suivant stocke l’adresse du nœud trois
- Pour le nœud trois : le suivant pointe vers le nœud un.
Opérations sur la liste chaînée circulaire :
Nous pouvons effectuer certaines opérations sur la liste circulaire chaînée similaires à la liste chaînée simple qui sont :
- Insertion
- Effacement
1. Insertion dans la liste chaînée circulaire :
Un nœud peut être ajouté de trois manières :
- Insertion en début de liste
- Insertion en fin de liste
- Insertion entre les nœuds
1) Insertion en début de liste : Pour insérer un nœud en début de liste, procédez comme suit :
- Créez un nœud, dites T.
- Faites T -> suivant = dernier -> suivant.
- dernier -> suivant = T.
Liste chaînée circulaire avant insertion
Et puis,
Liste chaînée circulaire après insertion
Ci-dessous l’implémentation du code pour insérer un nœud au début de la liste :
C
voidinsertAtBeginning(intdata) { structNode *newNode = (structNode*) malloc(sizeof(structNode)); newNode->data = data; if(!head) { head = newNode; newNode->next = head; } else{ structNode *current = head; while(current->next != head) { current = current->next; } newNode->next = head; current->next = newNode; head = newNode; }} |
C++
structNode *addBegin(structNode *last, intdata){if(last == NULL) returnaddToEmpty(last, data);// Creating a node dynamically.structNode *temp = (structNode *)malloc(sizeof(structNode)); // Assigning the data.temp -> data = data;// Adjusting the links.temp -> next = last -> next;last -> next = temp; returnlast;} |
Python3
defaddBegin(last, data): if(last ==None): returnaddToEmpty(last, data) # Creating a node dynamically. # Assigning the data. temp =Node(data) # Adjusting the links. temp.next=last.next last.next=temp returnlast |
Java
publicvoidinsertAtBeginning(intnewData) { Node newNode = newNode(newData); if(head == null) { head = newNode; head.next = head; } else{ Node current = head; while(current.next != head) { current = current.next; } newNode.next = head; current.next = newNode; head = newNode; }} |
C#
publicvoidInsertAtBeginning(intnewData){ Node newNode = newNode(newData); if(head == null) { head = newNode; head.Next = head; } else { Node current = head; while(current.Next != head) { current = current.Next; } newNode.Next = head; current.Next = newNode; head = newNode; }} |
Javascript
functioninsertAtBeginning(newData) { let newNode = newNode(newData); if(!head) { head = newNode; head.next = head; } else{ let current = head; while(current.next !== head) { current = current.next; } newNode.next = head; current.next = newNode; head = newNode; }} |
PHP
functioninsertAtBeginning($newData) { $newNode= newNode($newData); if(!$head) { $head= $newNode; $head->next = $head; } else{ $current= $head; while($current->next !== $head) { $current= $current->next; } $newNode->next = $head; $current->next = $newNode; $head= $newNode; }} |
Complexité temporelle : O(1) pour insérer un nœud au début pas besoin de parcourir la liste cela prend un temps constant
Espace Auxiliaire : O(1)
2) Insertion en fin de liste : Pour insérer un nœud en fin de liste, procédez comme suit :
- Créez un nœud, dites T.
- Faire T -> suivant = dernier -> suivant ;
- dernier -> suivant = T.
- dernier = T.
Avant l’insertion,
Liste chaînée circulaire avant insertion du nœud à la fin
Après insertion,
Circular linked list after insertion of node at the end
Below is the code implementation to insert a node at the beginning of the list:
C
voidinsertAtEnd(intnewData) { structNode* newNode = (structNode*)malloc(sizeof(structNode)); newNode->data = newData; if(!head) { head = newNode; newNode->next = head; } else{ structNode* current = head; while(current->next != head) { current = current->next; } current->next = newNode; newNode->next = head; }} |
C++
structNode *addEnd(structNode *last, intdata){if(last == NULL) returnaddToEmpty(last, data);// Creating a node dynamically.structNode *temp = (structNode *)malloc(sizeof(structNode)); // Assigning the data.temp -> data = data;// Adjusting the links.temp -> next = last -> next;last -> next = temp;last = temp; returnlast;} |
Python3
defaddEnd(last, data): if(last ==None): returnaddToEmpty(last, data) # Creating a node dynamically. # Assigning the data. temp =Node(data) # Adjusting the links. temp.next=last.next last.next=temp last =temp returnlast |
Java
publicvoidinsertAtEnd() { Node newNode = newNode(); newNode.data = newData; if(head == null) { head = newNode; newNode.next = head; } else{ Node current = head; while(current.next != head) { current = current.next; } current.next = newNode; newNode.next = head; }} |
C#
publicvoidInsertAtEnd(){ Node newNode = newNode(); newNode.Data = newData; if(head == null) { head = newNode; newNode.Next = head; } else { Node current = head; while(current.Next != head) { current = current.Next; } current.Next = newNode; newNode.Next = head; }} |
Javascript
functioninsertAtEnd(newData) { let newNode = newNode(newData); if(!head) { head = newNode; newNode.next = head; } else{ let current = head; while(current.next != head) { current = current.next; } current.next = newNode; newNode.next = head; }} |
PHP
functioninsertAtEnd($newData) { $newNode= newNode($newData); if(!$head) { $head= $newNode; $newNode->next = $head; } else{ $current= $head; while($current->next != $head) { $current= $current->next; } $current->next = $newNode; $newNode->next = $head; }} |
Time Complexity: O(1) to insert a node at the end of the list. No need to traverse the list as we are utilizing the last pointer, hence it takes constant time.
Auxiliary Space: O(1)
3) Insertion in between the nodes: To insert a node in between the two nodes, follow these steps:
- Create a node, say T.
- Search for the node after which T needs to be inserted, say that node is P.
- Make T -> next = P -> next;
- P -> next = T.
Suppose 12 needs to be inserted after the node has the value 10,
Circular linked list before insertion
After searching and insertion,
Circular linked list after insertion
Voici le code pour insérer un nœud à la position spécifiée de la liste :
C
voidinsertAtPosition(intposition, Node *newNode) { if(position < 1 || position > getSize() + 1) { printf("Invalid position!"); return; } if(position == 1) { insertAtBeginning(newNode); } elseif(position == getSize() + 1) { insertAtEnd(newNode); } else{ Node *current = head; for(inti = 1; i < position - 1; i++) { current = current->next; } newNode->next = current->next; current->next = newNode; }} |
C++
structNode *addAfter(structNode *last, intdata, intitem){ if(last == NULL) returnNULL; structNode *temp, *p; p = last -> next; // Searching the item. do { if(p ->data == item) { // Creating a node dynamically. temp = (structNode *)malloc(sizeof(structNode)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = p -> next; // Adding newly allocated node after p. p -> next = temp; // Checking for the last node. if(p == last) last = temp; returnlast; } p = p -> next; } while(p != last -> next); cout << item << " not present in the list."<< endl; returnlast;} |
Python3
defaddAfter(last, data, item): if(last ==None): return p =last.next # Searching the item. while(p !=last): if(p.data ==item): # Creating a node dynamically. # Assigning the data. temp =Node(data) # Adjusting the links. temp.next=p.next # Adding newly allocated node after p. p.next=temp # Checking for the last node. if(p ==last): last =temp returnlast p =p.next print(item," not present in the list.") returnlast |
Java
publicvoidinsertAtPosition(intposition, Node newNode) { if(position < 1|| position > getSize() + 1) { System.out.println("Invalid position!"); return; } if(position == 1) { insertAtBeginning(newNode); } elseif(position == getSize() + 1) { insertAtEnd(newNode); } else{ Node current = head; for(inti = 1; i < position - 1; i++) { current = current.next; } newNode.next = current.next; current.next = newNode; }} |
C#
publicvoidInsertAtPosition(intposition, Node newNode){ if(position < 1 || position > GetSize() + 1) { Console.WriteLine("Invalid position!"); return; } if(position == 1) { InsertAtBeginning(newNode); } elseif(position == GetSize() + 1) { InsertAtEnd(newNode); } else { Node current = head; for(inti = 1; i < position - 1; i++) { current = current.Next; } newNode.Next = current.Next; current.Next = newNode; }} |
Javascript
functioninsertAtPosition(position, newNode) { if(position < 1 || position > getSize() + 1) { console.log("Invalid position!"); return; } if(position === 1) { insertAtBeginning(newNode); } elseif(position === getSize() + 1) { insertAtEnd(newNode); } else{ let current = head; for(let i = 1; i < position - 1; i++) { current = current.next; } newNode.next = current.next; current.next = newNode; }} |
PHP
functioninsertAtPosition($position, $newNode) { global$head; if($position< 1 || $position> getSize() + 1) { echo"Invalid position!"; return; } if($position=== 1) { insertAtBeginning($newNode); } elseif($position=== getSize() + 1) { insertAtEnd($newNode); } else{ $current= $head; for($i= 1; $i< $position- 1; $i++) { $current= $current->next; } $newNode->next = $current->next; $current->next = $newNode; }} |
Complexité temporelle : O(N)
Espace auxiliaire : O(1)
2. Suppression dans une liste chaînée circulaire :
1) Supprimez le nœud uniquement s’il s’agit du seul nœud de la liste circulaire chaînée :
- Libérez la mémoire du nœud
- La dernière valeur doit être NULL Un nœud pointe toujours vers un autre nœud, donc l’affectation NULL n’est pas nécessaire.
N’importe quel nœud peut être défini comme point de départ.
Les nœuds sont parcourus rapidement du premier au dernier.
2) Suppression du dernier nœud :
- Localisez le nœud avant le dernier nœud (qu’il soit temporaire)
- Conservez l’adresse du nœud à côté du dernier nœud dans temp
- Supprimer la dernière mémoire
- Mettre temp à la fin
3) Delete any node from the circular linked list: We will be given a node and our task is to delete that node from the circular linked list.
Algorithm:
Case 1: List is empty.
- If the list is empty we will simply return.
Case 2:List is not empty
- If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.
- Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.
- If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr).
- Si la liste comporte plusieurs nœuds, vérifiez s’il s’agit du premier nœud de la liste. Condition pour vérifier ceci( curr == head). Si oui, déplacez prev jusqu’à ce qu’il atteigne le dernier nœud. Une fois que prev a atteint le dernier nœud, définissez head = head -> next et prev -> next = head. Supprimer curr.
- Si curr n’est pas le premier nœud, nous vérifions s’il s’agit du dernier nœud de la liste. La condition pour vérifier ceci est (curr -> next == head).
- Si curr est le dernier nœud. Définissez prev -> next = head et supprimez le nœud curr par free(curr).
- Si le nœud à supprimer n’est ni le premier ni le dernier nœud, alors définissez prev -> next = curr -> next et supprimez curr.
- Si le nœud n’est pas présent dans la liste, retournez head et ne faites rien.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C
#include <stdio.h>#include <stdlib.h>// Structure for a nodestructNode { intdata; structNode* next;};// Function to insert a node at the// beginning of a Circular linked listvoidpush(structNode** head_ref, intdata){ // Create a new node and make head // as next of it. structNode* ptr1 = (structNode*)malloc(sizeof(structNode)); ptr1->data = data; ptr1->next = *head_ref; // If linked list is not NULL then // set the next of last node if(*head_ref != NULL) { // Find the node before head and // update next of it. structNode* temp = *head_ref; while(temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else // For the first node ptr1->next = ptr1; *head_ref = ptr1;}// Function to print nodes in a given// circular linked listvoidprintList(structNode* head){ structNode* temp = head; if(head != NULL) { do{ printf("%d ", temp->data); temp = temp->next; } while(temp != head); } printf("\n");}// Function to delete a given node// from the listvoiddeleteNode(structNode** head, intkey){ // If linked list is empty if(*head == NULL) return; // If the list contains only a // single node if((*head)->data == key && (*head)->next == *head) { free(*head); *head = NULL; return; } structNode *last = *head, *d; // If head is to be deleted if((*head)->data == key) { // Find the last node of the list while(last->next != *head) last = last->next; // Point last node to the next of // head i.e. the second node // of the list last->next = (*head)->next; free(*head); *head = last->next; return; } // Either the node to be deleted is // not found or the end of list // is not reached while(last->next != *head && last->next->data != key) { last = last->next; } // If node to be deleted was found if(last->next->data == key) { d = last->next; last->next = d->next; free(d); } else printf("Given node is not found in the list!!!\n");}// Driver codeintmain(){ // Initialize lists as empty structNode* head = NULL; // Created linked list will be // 2->5->7->8->10 push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); printf("List Before Deletion: "); printList(head); deleteNode(&head, 7); printf("List After Deletion: "); printList(head); return0;} |
C++
// C++ program to delete a given key from// linked list.#include <bits/stdc++.h>usingnamespacestd;// Structure for a nodeclassNode {public: intdata; Node* next;};// Function to insert a node at the// beginning of a Circular linked listvoidpush(Node** head_ref, intdata){ // Create a new node and make head // as next of it. Node* ptr1 = newNode(); ptr1->data = data; ptr1->next = *head_ref; // If linked list is not NULL then // set the next of last node if(*head_ref != NULL) { // Find the node before head and // update next of it. Node* temp = *head_ref; while(temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else // For the first node ptr1->next = ptr1; *head_ref = ptr1;}// Function to print nodes in a given// circular linked listvoidprintList(Node* head){ Node* temp = head; if(head != NULL) { do{ cout << temp->data << " "; temp = temp->next; } while(temp != head); } cout << endl;}// Function to delete a given node// from the listvoiddeleteNode(Node** head, intkey){ // If linked list is empty if(*head == NULL) return; // If the list contains only a // single node if((*head)->data == key && (*head)->next == *head) { free(*head); *head = NULL; return; } Node *last = *head, *d; // If head is to be deleted if((*head)->data == key) { // Find the last node of the list while(last->next != *head) last = last->next; // Point last node to the next of // head i.e. the second node // of the list last->next = (*head)->next; free(*head); *head = last->next; return; } // Either the node to be deleted is // not found or the end of list // is not reached while(last->next != *head && last->next->data != key) { last = last->next; } // If node to be deleted was found if(last->next->data == key) { d = last->next; last->next = d->next; free(d); } else cout << "Given node is not found in the list!!!\n";}// Driver codeintmain(){ // Initialize lists as empty Node* head = NULL; // Created linked list will be // 2->5->7->8->10 push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); cout << "List Before Deletion: "; printList(head); deleteNode(&head, 7); cout << "List After Deletion: "; printList(head); return0;} |
Java
// Java program to delete a given key from// linked list.importjava.io.*;importjava.util.*;publicclassGFG { /* structure for a node */ staticclassNode { intdata; Node next; }; /* Function to insert a node at the beginning ofa Circular linked list */ staticNode push(Node head_ref, intdata) { // Create a new node and make head as next // of it. Node ptr1 = newNode(); ptr1.data = data; ptr1.next = head_ref; /* If linked list is not null then set thenext of last node */ if(head_ref != null) { // Find the node before head and update // next of it. Node temp = head_ref; while(temp.next != head_ref) temp = temp.next; temp.next = ptr1; } else ptr1.next = ptr1; /*For the first node */ head_ref = ptr1; returnhead_ref; } /* Function to print nodes in a givencircular linked list */ staticvoidprintList(Node head) { Node temp = head; if(head != null) { do{ System.out.printf("%d ", temp.data); temp = temp.next; } while(temp != head); } System.out.printf("\n"); } /* Function to delete a given node from the list */ staticNode deleteNode(Node head, intkey) { if(head == null) returnnull; intflag = 0; // Find the required node Node curr = head, prev = newNode(); while(curr.data != key) { if(curr.next == head) { System.out.printf( "Given node is not found in the list!!!\n"); flag = 1; break; } prev = curr; curr = curr.next; } // Check if the element is not present in the list if(flag == 1) returnhead; // Check if node is only node if(curr == head && curr.next == head) { head = null; returnhead; } // 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 elseif(curr.next == head) { prev.next = head; } else{ prev.next = curr.next; } returnhead; } /* Driver code */ publicstaticvoidmain(String args[]) { /* Initialize lists as empty */ Node head = null; /* Created linked list will be 2.5.7.8.10 */ head = push(head, 2); head = push(head, 5); head = push(head, 7); head = push(head, 8); head = push(head, 10); System.out.printf("List Before Deletion: "); printList(head); head = deleteNode(head, 7); System.out.printf("List After Deletion: "); printList(head); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python program to delete a given key from linked listclassNode: def__init__(self, data): self.data =data self.next=None# Function to insert a node at the# beginning of a Circular linked listdefpush(head, data): # Create a new node and make head as next of it. newP =Node(data) newP.next=head # If linked list is not NULL then # set the next of last node ifhead !=None: # Find the node before head and # update next of it. temp =head while(temp.next!=head): temp =temp.next temp.next=newP else: newP.next=newP head =newP returnhead# Function to print nodes in a given circular linked listdefprintList(head): ifhead ==None: print("List is Empty") return temp =head.next print(head.data, end=' ') if(head !=None): while(temp !=head): print(temp.data, end=" ") temp =temp.next print()# Function to delete a given node# from the listdefdeleteNode(head, key): # If linked list is empty if(head ==None): return # If the list contains only a # single node if(head.data ==key andhead.next==head): head =None return last =head # If head is to be deleted if(head.data ==key): # Find the last node of the list while(last.next!=head): last =last.next # Point last node to the next of # head i.e. the second node # of the list last.next=head.next head =last.next return # Either the node to be deleted is # not found or the end of list # is not reached while(last.next!=head andlast.next.data !=key): last =last.next # If node to be deleted was found if(last.next.data ==key): d =last.next last.next=d.next d =None else: print("Given node is not found in the list!!!")# Driver code# Initialize lists as emptyhead =None# Created linked list will be# 2->5->7->8->10head =push(head, 2)head =push(head, 5)head =push(head, 7)head =push(head, 8)head =push(head, 10)print("List Before Deletion: ")printList(head)deleteNode(head, 7)print("List After Deletion: ")printList(head) |
Javascript
// Javascript program to delete a given key from linked list.// Structure for a nodeclass Node { constructor() { this.data; this.next; }}// Function to insert a node at the// beginning of a Circular linked listfunctionpush(head, data) { // Create a new node and make head // as next of it. varptr1 = newNode(); ptr1.data = data; ptr1.next = head; // If linked list is not NULL then // set the next of last node if(head != null) { // Find the node before head and // update next of it. let temp = head; while(temp.next != head) temp = temp.next; temp.next = ptr1; } // For the first node elseptr1.next = ptr1; head = ptr1; returnhead;}// Function to print nodes in a given// circular linked listfunctionprintList(head) { let tempp = head; if(head != null) { do{ console.log(tempp.data); tempp = tempp.next; } while(tempp != head); }}// Function to delete a given node// from the listfunctiondeleteNode(head, key) { // If linked list is empty if(head == null) return; // If the list contains only a // single node if(head.data == key && head.next == head) { head = null; return; } let last = head; // If head is to be deleted if(head.data == key) { // Find the last node of the list while(last.next != head) last = last.next; // Point last node to the next of // head i.e. the second node // of the list last.next = head.next; head = last.next; return; } // Either the node to be deleted is // not found or the end of list // is not reached while(last.next != head && last.next.data != key) { last = last.next; } // If node to be deleted was found if(last.next.data == key) { d = last.next; last.next = d.next; d = null; } elseconsole.log("Given node is not found in the list!!!");}// Driver code// Initialize lists as emptyhead = null;// Created linked list will be// 2->5->7->8->10head = push(head, 2);head = push(head, 5);head = push(head, 7);head = push(head, 8);head = push(head, 10);console.log("List Before Deletion: ");printList(head);deleteNode(head, 7);console.log("List After Deletion: ");printList(head); |
C#
usingSystem;// Structure for a nodepublicclassNode { publicintdata; publicNode next;}// Class for Circular Linked ListpublicclassCircularLinkedList { // Function to insert a node at the // beginning of a Circular linked list publicstaticvoidPush(refNode head_ref, intdata) { // Create a new node and make head // as next of it. Node ptr1 = newNode(); ptr1.data = data; ptr1.next = head_ref; // If linked list is not NULL then // set the next of last node if(head_ref != null) { // Find the node before head and // update next of it. Node temp = head_ref; while(temp.next != head_ref) temp = temp.next; temp.next = ptr1; } else // For the first node ptr1.next = ptr1; head_ref = ptr1; } // Function to print nodes in a given // circular linked list publicstaticvoidPrintList(Node head) { Node temp = head; if(head != null) { do{ Console.Write(temp.data + " "); temp = temp.next; } while(temp != head); } Console.WriteLine(); } // Function to delete a given node // from the list publicstaticvoidDeleteNode(refNode head, intkey) { // If linked list is empty if(head == null) return; // If the list contains only a // single node if(head.data == key && head.next == head) { head = null; return; } Node last = head, d; // If head is to be deleted if(head.data == key) { // Find the last node of the list while(last.next != head) last = last.next; // Point last node to the next of // head i.e. the second node // of the list last.next = head.next; head = last.next; return; } // Either the node to be deleted is // not found or the end of list // is not reached while(last.next != head && last.next.data != key) { last = last.next; } // If node to be deleted was found if(last.next.data == key) { d = last.next; last.next = d.next; } else Console.WriteLine( "Given node is not found in the list!!!"); } // Driver code publicstaticvoidMain() { // Initialize lists as empty Node head = null; // Created linked list will be // 2->5->7->8->10 Push(refhead, 2); Push(refhead, 5); Push(refhead, 7); Push(refhead, 8); Push(refhead, 10); Console.Write("List Before Deletion: "); PrintList(head); DeleteNode(refhead, 7); Console.Write("List After Deletion: "); PrintList(head); }} |
Sortir
Liste avant suppression : 10 8 7 5 2 Liste après suppression : 10 8 5 2
Complexité temporelle : O(N), le pire des cas se produit lorsque l’élément à supprimer est le dernier élément et que nous devons parcourir toute la liste.
Espace auxiliaire : O(1), car un espace supplémentaire constant est utilisé.
Avantages des listes circulaires liées :
- Tout nœud peut être un point de départ. On peut parcourir toute la liste en partant de n’importe quel point. Nous avons juste besoin de nous arrêter lorsque le premier nœud visité est à nouveau visité.
- Utile pour la mise en place d’une file d’attente. Contrairement à cette implémentation, nous n’avons pas besoin de maintenir deux pointeurs pour l’avant et l’arrière si nous utilisons une liste chaînée circulaire. Nous pouvons maintenir un pointeur vers le dernier nœud inséré et le front peut toujours être obtenu comme avant-dernier.
- Les listes circulaires sont utiles dans les applications pour faire le tour de la liste à plusieurs reprises. Par exemple, lorsque plusieurs applications s’exécutent sur un PC, il est courant que le système d’exploitation place les applications en cours d’exécution sur une liste, puis les parcoure, en donnant à chacune d’elles une tranche de temps pour s’exécuter, puis en les faisant attendre pendant que le CPU est donné à une autre application. Il est pratique pour le système d’exploitation d’utiliser une liste circulaire afin que lorsqu’il atteint la fin de la liste, il puisse passer au début de la liste.
- Les listes circulaires doublement liées sont utilisées pour la mise en œuvre de structures de données avancées telles que le tas de Fibonacci .
- La mise en œuvre d’une liste chaînée circulaire peut être relativement facile par rapport à d’autres structures de données plus complexes comme des arbres ou des graphiques.
Inconvénients de la liste chaînée circulaire :
- Par rapport aux listes à liens simples, les listes circulaires sont plus complexes.
- L’inversion d’une liste circulaire est plus compliquée que l’inversion simple ou double d’une liste circulaire.
- Il est possible que le code entre dans une boucle infinie s’il n’est pas manipulé avec soin.
- Il est plus difficile de trouver la fin de la liste et de contrôler la boucle.
- Bien que les listes chaînées circulaires puissent être efficaces dans certaines applications, leurs performances peuvent être plus lentes que d’autres structures de données dans certains cas, par exemple lorsque la liste doit être triée ou recherchée.
- Les listes liées circulaires ne fournissent pas un accès direct aux nœuds individuels
Applications des listes chaînées circulaires :
- Les jeux multijoueurs l’utilisent pour donner à chaque joueur une chance de jouer.
- Une liste chaînée circulaire peut être utilisée pour organiser plusieurs applications en cours d’exécution sur un système d’exploitation. Ces applications sont itérées par le système d’exploitation.
- Les listes chaînées circulaires peuvent être utilisées dans les problèmes d’allocation de ressources.
- Les listes chaînées circulaires sont couramment utilisées pour implémenter des tampons circulaires,
- Les listes liées circulaires peuvent être utilisées dans la simulation et les jeux.
Pourquoi une liste chaînée circulaire ?
- Un nœud pointe toujours vers un autre nœud, donc l’affectation NULL n’est pas nécessaire.
- N’importe quel nœud peut être défini comme point de départ.
- Les nœuds sont parcourus rapidement du premier au dernier.