logo

TechCodeview

Inleiding tot circulair gekoppelde lijst

Wat is een circulair gekoppelde lijst?

De circulair gekoppelde lijst is een gekoppelde lijst waarbij alle knooppunten met elkaar zijn verbonden om een ​​cirkel te vormen. In een circulair gekoppelde lijst zijn het eerste knooppunt en het laatste knooppunt met elkaar verbonden, wat een cirkel vormt. Er staat geen NULL aan het einde.

Circulair gekoppelde lijst



Er zijn over het algemeen twee soorten circulair gekoppelde lijsten:

  • Circulaire enkelvoudig gekoppelde lijst: In een cirkelvormige, enkelvoudig gekoppelde lijst bevat het laatste knooppunt van de lijst een verwijzing naar het eerste knooppunt van de lijst. We doorkruisen de cirkelvormige, enkelvoudig gekoppelde lijst totdat we hetzelfde knooppunt bereiken waar we begonnen. De cirkelvormige, enkelvoudig gekoppelde lijst heeft geen begin of einde. Er is geen nulwaarde aanwezig in het volgende deel van een van de knooppunten.

Vertegenwoordiging van een circulaire, enkelvoudig gekoppelde lijst

  • Circulaire Dubbel gelinkte lijst: Circulaire dubbel gekoppelde lijst heeft eigenschappen van zowel dubbel gekoppelde lijst als circulair gekoppelde lijst waarin twee opeenvolgende elementen zijn gekoppeld of verbonden door de vorige en volgende aanwijzer en het laatste knooppunt verwijst naar het eerste knooppunt door de volgende aanwijzer en ook het eerste knooppunt wijst naar het laatste knooppunt bij de vorige aanwijzer.

Vertegenwoordiging van een cirkelvormige, dubbel gekoppelde lijst



Opmerking: We zullen de enkelvoudig circulair gekoppelde lijst gebruiken om de werking van de circulair gekoppelde lijst weer te geven.

Weergave van circulair gekoppelde lijst:

Circulair gekoppelde lijsten zijn vergelijkbaar met enkelvoudige gekoppelde lijsten, met uitzondering van het verbinden van het laatste knooppunt met het eerste knooppunt.

Java-wiskunde willekeurig

Knooppuntrepresentatie van een circulair gekoppelde lijst:



C++ 
// Class Node, similar to the linked list class Node{  int value; // Points to the next node.  Node next; }>
C 
struct Node {  int data;  struct Node *next; };>
Java 
public class Node {  int data;  Node next;    public Node(int data) {  this.data = data;  this.next = null;  } }>
C# 
public class Node {  public int data;  public Node next;    public Node(int data)  {  this.data = data;  this.next = null;  } }>
Javascript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  } }>
PHP 
class Node {  public $data;  public $next;  function __construct($data) {  $this->gegevens = $gegevens;  $dit->volgende = nul;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Voorbeeld van een circulaire enkelvoudig gekoppelde lijst:

Voorbeeld van een circulair gekoppelde lijst

De bovenstaande circulaire, enkelvoudig gekoppelde lijst kan worden weergegeven als:

arp een opdracht
C++ 
// Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C 
Node* one = createNode(3); Node* two = createNode(5); Node* three = createNode(9); // Connect nodes one->volgende = twee; twee->volgende = drie; drie->volgende = één;>
Java 
// Define the Node class class Node {  int value;  Node next;  public Node(int value) {  this.value = value;  } } // Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C# 
Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
Javascript 
let one = new Node(3); let two = new Node(5); let three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
PHP 
$one = new Node(3); $two = new Node(5); $three = new Node(9); // Connect nodes $one->volgende = $twee; $twee->volgende = $drie; $drie->volgende = $één;>
Python3 
# Initialize the Nodes. one = Node(3) two = Node(5) three = Node(9) # Connect nodes one.next = two two.next = three three.next = one>

Uitleg: In het bovenstaande programma zijn één, twee en drie het knooppunt met respectievelijk de waarden 3, 5 en 9 die op een cirkelvormige manier zijn verbonden als:

  • Voor knooppunt één: De Next-aanwijzer slaat het adres van knooppunt twee op.
  • Voor knooppunt twee: The Next slaat het adres van knooppunt drie op
  • Voor knooppunt drie: De Het volgende wijst naar knooppunt één.

Bewerkingen op de circulair gekoppelde lijst:

We kunnen een aantal bewerkingen uitvoeren op de circulair gekoppelde lijst, vergelijkbaar met de enkelvoudig gekoppelde lijst, namelijk:

  1. Plaatsing
  2. Verwijdering

1. Invoeging in de circulair gekoppelde lijst:

Een knooppunt kan op drie manieren worden toegevoegd:

  1. Invoeging aan het begin van de lijst
  2. Invoeging aan het einde van de lijst
  3. Invoeging tussen de knooppunten

1) Invoeging aan het begin van de lijst: Volg deze stappen om een ​​knooppunt aan het begin van de lijst in te voegen:

  • Maak een knooppunt, zeg T.
  • Maak T -> volgende = laatste -> volgende.
  • laatste -> volgende = T.

Circulair gekoppelde lijst vóór invoeging

En dan,

Circulair gekoppelde lijst na invoeging

2) Invoeging aan het einde van de lijst: Volg deze stappen om een ​​knooppunt aan het einde van de lijst in te voegen:

  • Maak een knooppunt, zeg T.
  • Maak T -> volgende = laatste -> volgende;
  • laatste -> volgende = T.
  • laatste = T.

Vóór het inbrengen,

Circulair gekoppelde lijst vóór invoeging van knooppunt aan het einde

pseudocode java

Na het inbrengen,

Circulair gekoppelde lijst na invoeging van een knooppunt aan het einde

3) Invoeging tussen de knooppunten: Om een ​​knooppunt tussen de twee knooppunten in te voegen, volgt u deze stappen:

b+ boom
  • Maak een knooppunt, zeg T.
  • Zoek het knooppunt waarna T moet worden ingevoegd, zeg dat dat knooppunt P is.
  • Maak T -> volgende = P -> volgende;
  • P -> volgende = T.

Stel dat 12 moet worden ingevoegd nadat het knooppunt de waarde 10 heeft,

Circulair gekoppelde lijst vóór invoeging

Na het zoeken en invoegen,

Circulair gekoppelde lijst na invoeging

2. Verwijdering in een circulair gekoppelde lijst:

1) Verwijder het knooppunt alleen als dit het enige knooppunt in de circulair gekoppelde lijst is:

javascriptvariabele globaal
  • Maak het geheugen van het knooppunt vrij
  • De laatste waarde moet NULL zijn. Een knooppunt verwijst altijd naar een ander knooppunt, dus NULL-toewijzing is niet nodig.
    Elk knooppunt kan als startpunt worden ingesteld.
    Knooppunten worden snel doorlopen van de eerste tot de laatste.

2) Verwijdering van het laatste knooppunt:

  • Zoek het knooppunt vóór het laatste knooppunt (laat het een temperatuur zijn)
  • Bewaar het adres van het knooppunt naast het laatste knooppunt in Temp
  • Wis de laatste herinnering
  • Zet op het einde de temperatuur

3) Verwijder elk knooppunt uit de circulair gekoppelde lijst: We krijgen een knooppunt en het is onze taak om dat knooppunt uit de circulair gekoppelde lijst te verwijderen.

Algoritme:
Zaak 1 : Lijst is leeg.

  • Als de lijst leeg is, komen we gewoon terug.

Geval 2 :Lijst is niet leeg

  • Als de lijst niet leeg is, definiëren we twee pointers kr En vorige en initialiseer de aanwijzer kr met de hoofd knooppunt.
  • Doorloop de lijst met kr om het knooppunt te vinden dat moet worden verwijderd en voordat u naar curr naar het volgende knooppunt gaat, stelt u elke keer prev = curr in.
  • Als het knooppunt wordt gevonden, controleer dan of dit het enige knooppunt in de lijst is. Zo ja, stel head = NULL en free(curr) in.
  • Als de lijst meer dan één knooppunt heeft, controleer dan of dit het eerste knooppunt van de lijst is. Voorwaarde om dit te controleren (curr == hoofd). Zo ja, ga dan naar vorige totdat het laatste knooppunt wordt bereikt. Nadat prev het laatste knooppunt heeft bereikt, stelt u head = head -> next en prev -> next = head in. Huidig ​​verwijderen
  • Als curr niet het eerste knooppunt is, controleren we of dit het laatste knooppunt in de lijst is. Voorwaarde om dit te controleren is (curr -> next == head).
  • Als curr het laatste knooppunt is. Stel prev -> next = head in en verwijder het knooppunt curr met free(curr).
  • Als het knooppunt dat moet worden verwijderd noch het eerste knooppunt, noch het laatste knooppunt is, stel dan prev -> next = curr -> next in en verwijder curr.
  • Als het knooppunt niet aanwezig is in de lijst, keert u terug naar de kop en doet u niets.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++ 
// C++ program to delete a given key from // linked list. #include  using namespace std; // Structure for a node class Node { public:  int data;  Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  Node* ptr1 = new Node();  ptr1->gegevens = gegevens;  ptr1->volgende = *head_ref;  // Als de gekoppelde lijst niet NULL is, // stel dan het volgende van het laatste knooppunt in if (*head_ref != NULL) {// Zoek het knooppunt vóór het hoofd en // update het volgende knooppunt.  Knooppunt* temp = *head_ref;  while (temp->volgende != *head_ref) temp = temp->volgende;  temp->volgende = ptr1;  } else // Voor het eerste knooppunt ptr1->next = ptr1;  *hoofd_ref = ptr1; } // Functie om knooppunten af ​​te drukken in een gegeven // circulair gekoppelde lijst void printList(Node* head) { Node* temp = head;  if (hoofd!= NULL) { do { cout<< temp->gegevens<< ' ';  temp = temp->volgende;  } while (temp != hoofd);  } uit<< endl; } // Function to delete a given node // from the list void deleteNode(Node** head, int key) {  // If linked list is empty  if (*head == NULL)  return;  // If the list contains only a  // single node  if ((*head)->data == sleutel && (*hoofd)->volgende == *hoofd) { free(*hoofd);  *hoofd = NULL;  opbrengst;  } Knooppunt *laatste = *head, *d;  // If head moet worden verwijderd if ((*head)->data == key) {// Zoek het laatste knooppunt van de lijst terwijl (last->next != *head) last = last->next;  // Wijs het laatste knooppunt naar het volgende van // head, d.w.z. het tweede knooppunt // van de lijst last->next = (*head)->next;  gratis(*hoofd);  *hoofd = laatste->volgende;  opbrengst;  } // Het knooppunt dat moet worden verwijderd is // niet gevonden of het einde van de lijst // is niet bereikt while (last->next != *head && last->next->data != key) { last = last ->volgende;  } // Als het te verwijderen knooppunt is gevonden als (laatste->volgende->data == sleutel) { d = laatste->volgende;  laatste->volgende = d->volgende;  gratis(d);  } anders uit<< 'Given node is not found in the list!!!
'; } // Driver code int main() {  // Initialize lists as empty  Node* head = NULL;  // Created linked list will be  // 2->5->7->8->10 druk(&hoofd, 2);  push(&hoofd, 5);  push(&hoofd, 7);  duwen(&hoofd, 8);  push(&hoofd, 10);  uit<< 'List Before Deletion: ';  printList(head);  deleteNode(&head, 7);  cout << 'List After Deletion: ';  printList(head);  return 0; }>
C 
#include  #include  // Structure for a node struct Node {  int data;  struct Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(struct Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));  ptr1->gegevens = gegevens;  ptr1->volgende = *head_ref;  // Als de gekoppelde lijst niet NULL is, // stel dan het volgende van het laatste knooppunt in if (*head_ref != NULL) {// Zoek het knooppunt vóór het hoofd en // update het volgende knooppunt.  struct Knooppunt* temp = *head_ref;  while (temp->volgende != *head_ref) temp = temp->volgende;  temp->volgende = ptr1;  } else // Voor het eerste knooppunt ptr1->next = ptr1;  *hoofd_ref = ptr1; } // Functie om knooppunten af ​​te drukken in een gegeven // circulair gekoppelde lijst void printList(struct Node* head) { struct Node* temp = head;  if (head != NULL) { do { printf('%d ', temp->data);  temp = temp->volgende;  } while (temp != hoofd);  } printf('
'); } // Functie om een ​​bepaald knooppunt te verwijderen // uit de lijst void deleteNode(struct Node** head, int key) {// Als de gekoppelde lijst leeg is if (*head == NULL) return;  // Als de lijst slechts één // enkel knooppunt bevat if ((*head)->data == key && (*head)->next == *head) { free(*head);  *hoofd = NULL;  opbrengst;  } struct Knooppunt *last = *head, *d;  // If head moet worden verwijderd if ((*head)->data == key) {// Zoek het laatste knooppunt van de lijst terwijl (last->next != *head) last = last->next;  // Wijs het laatste knooppunt naar het volgende van // head, d.w.z. het tweede knooppunt // van de lijst last->next = (*head)->next;  gratis(*hoofd);  *hoofd = laatste->volgende;  opbrengst;  } // Het knooppunt dat moet worden verwijderd is // niet gevonden of het einde van de lijst // is niet bereikt while (last->next != *head && last->next->data != key) { last = last ->volgende;  } // Als het te verwijderen knooppunt is gevonden als (laatste->volgende->data == sleutel) { d = laatste->volgende;  laatste->volgende = d->volgende;  gratis(d);  } else printf('Gegeven knooppunt is niet gevonden in de lijst!!!
'); } // Stuurprogrammacode int main() {// Initialiseer lijsten als lege struct Knooppunt* head = NULL;  // De aangemaakte gekoppelde lijst wordt // 2->5->7->8->10 push(&head, 2);  push(&hoofd, 5);  push(&hoofd, 7);  duwen(&hoofd, 8);  push(&hoofd, 10);  printf('Lijst vóór verwijdering: ');  printLijst(hoofd);  deleteNode(&head, 7);  printf('Lijst na verwijdering: ');  printLijst(hoofd);  retour 0; }>
Java 
// Java program to delete a given key from // linked list. import java.io.*; import java.util.*; public class GFG {  /* structure for a node */  static class Node {  int data;  Node next;  };  /* Function to insert a node at the beginning of a Circular linked list */  static Node push(Node head_ref, int data)  {  // Create a new node and make head as next  // of it.  Node ptr1 = new Node();  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  ptr1.next = ptr1; /*For the first node */  head_ref = ptr1;  return head_ref;  }  /* Function to print nodes in a given circular linked list */  static void printList(Node head)  {  Node temp = head;  if (head != null) {  do {  System.out.printf('%d ', temp.data);  temp = temp.next;  } while (temp != head);  }  System.out.printf('
');  }  /* Function to delete a given node from the list */  static Node deleteNode(Node head, int key)  {  if (head == null)  return null;  int flag = 0;  // Find the required node  Node curr = head, prev = new Node();  while (curr.data != key) {  if (curr.next == head) {  System.out.printf(  'Given node is not found in the list!!!
');  flag = 1;  break;  }  prev = curr;  curr = curr.next;  }  // Check if the element is not present in the list  if (flag == 1)  return head;  // Check if node is only node  if (curr == head && 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;  }  return head;  }  /* Driver code */  public static void main(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>
C# 
using System; // Structure for a node public class Node {  public int data;  public Node next; } // Class for Circular Linked List public class CircularLinkedList {  // Function to insert a node at the  // beginning of a Circular linked list  public static void Push(ref Node head_ref, int data)  {  // Create a new node and make head  // as next of it.  Node ptr1 = new Node();  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  public static void PrintList(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  public static void DeleteNode(ref Node head, int 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;  }  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  public static void Main()  {  // Initialize lists as empty  Node head = null;  // Created linked list will be  // 2->5->7->8->10 Duwen (ref kop, 2);  Duwen (ref kop, 5);  Duwen (ref kop, 7);  Duwen (ref kop, 8);  Duwen (ref kop, 10);  Console.Write('Lijst vóór verwijdering: ');  PrintLijst(hoofd);  DeleteNode(ref hoofd, 7);  Console.Write('Lijst na verwijdering: ');  PrintLijst(hoofd);  } }>
Javascript 
 // Javascript program to delete a given key from linked list.  // Structure for a node  class Node {  constructor() {  this.data;  this.next;  }  }  // Function to insert a node at the  // beginning of a Circular linked list  function push(head, data) {  // Create a new node and make head  // as next of it.  var ptr1 = new Node();  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  else ptr1.next = ptr1;  head = ptr1;  return head;  }  // Function to print nodes in a given  // circular linked list  function printList(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 list  function deleteNode(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;  } else console.log('Given node is not found in the list!!!');  }  // Driver code  // Initialize lists as empty  head = null;  // Created linked list will be  // 2->5->7->8->10 kop = duwen(kop, 2);  hoofd = duwen(hoofd, 5);  hoofd = duwen(hoofd, 7);  hoofd = duwen(hoofd, 8);  hoofd = duwen(hoofd, 10);  console.log('Lijst vóór verwijdering: ');  printLijst(hoofd);  deleteNode(hoofd, 7);  console.log('Lijst na verwijdering: ');  printLijst(hoofd);>
Python3 
# Python program to delete a given key from linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at the # beginning of a Circular linked list def push(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 if head != 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 return head # Function to print nodes in a given circular linked list def printList(head): if head == 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 list def deleteNode(head, key): # If linked list is empty if (head == None): return # If the list contains only a # single node if (head.data == key and head.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 and 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 = None else: print('Given node is not found in the list!!!') # Driver code # Initialize lists as empty head = None # Created linked list will be # 2->5->7->8->10 hoofd = duwen(kop, 2) hoofd = duwen(kop, 5) hoofd = duwen(kop, 7) hoofd = duwen(kop, 8) hoofd = duwen(kop, 10) print('Lijst vóór verwijdering: ') printList(head) deleteNode(head, 7) print('Lijst na verwijdering: ') printList(head)>
Uitvoer 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Tijdcomplexiteit: O(N), In het ergste geval treedt het te verwijderen element op als het laatste element en moeten we door de hele lijst lopen.
Hulpruimte: O(1), Omdat er constant extra ruimte wordt gebruikt.

Voordelen van circulair gekoppelde lijsten:

  • Elk knooppunt kan een startpunt zijn. We kunnen de hele lijst doorkruisen door vanaf elk punt te beginnen. We hoeven alleen maar te stoppen wanneer het eerst bezochte knooppunt opnieuw wordt bezocht.
  • Handig voor het implementeren van een wachtrij. in tegenstelling tot dit Bij de implementatie hoeven we geen twee verwijzingen voor de voor- en achterkant aan te houden als we een circulair gekoppelde lijst gebruiken. We kunnen een verwijzing naar het laatst ingevoegde knooppunt behouden en de voorkant kan altijd als een na laatste worden verkregen.
  • Cirkelvormige lijsten zijn handig bij toepassingen waarbij u herhaaldelijk de lijst wilt doorlopen. Als er bijvoorbeeld meerdere applicaties op een pc draaien, is het gebruikelijk dat het besturingssysteem de actieve applicaties in een lijst plaatst en er vervolgens doorheen bladert, waarbij elk van hen een stukje tijd krijgt om uit te voeren, en ze vervolgens laat wachten terwijl ze worden uitgevoerd. de CPU wordt aan een andere applicatie gegeven. Het is handig voor het besturingssysteem om een ​​cirkelvormige lijst te gebruiken, zodat het, wanneer het het einde van de lijst bereikt, naar het begin van de lijst kan lopen.
  • Circulaire dubbelgekoppelde lijsten worden gebruikt voor de implementatie van geavanceerde datastructuren zoals de Fibonacci-hoop .
  • Het implementeren van een circulair gekoppelde lijst kan relatief eenvoudig zijn vergeleken met andere, meer complexe datastructuren zoals bomen of grafieken.

Nadelen van circulair gekoppelde lijst:

  • Vergeleken met enkelvoudig gekoppelde lijsten zijn circulaire lijsten complexer.
  • Het omkeren van een cirkelvormige lijst is ingewikkelder dan het enkelvoudig of dubbel omkeren van een cirkelvormige lijst.
  • Het is mogelijk dat de code in een oneindige lus terechtkomt als er niet zorgvuldig mee wordt omgegaan.
  • Het is moeilijker om het einde van de lijst te vinden en de lus te beheersen.
  • Hoewel circulair gekoppelde lijsten in bepaalde toepassingen efficiënt kunnen zijn, kunnen hun prestaties in bepaalde gevallen langzamer zijn dan die van andere gegevensstructuren, bijvoorbeeld wanneer de lijst moet worden gesorteerd of doorzocht.
  • Circulair gekoppelde lijsten bieden geen directe toegang tot individuele knooppunten

Toepassingen van circulair gekoppelde lijsten:

  • Multiplayer-spellen gebruiken dit om elke speler de kans te geven om te spelen.
  • Een circulair gekoppelde lijst kan worden gebruikt om meerdere actieve applicaties op een besturingssysteem te ordenen. Deze toepassingen worden herhaald door het besturingssysteem.
  • Circulair gekoppelde lijsten kunnen worden gebruikt bij problemen met de toewijzing van middelen.
  • Circulair gekoppelde lijsten worden vaak gebruikt om circulaire buffers te implementeren,
  • Circulair gekoppelde lijsten kunnen worden gebruikt bij simulatie en gaming.

Waarom circulair gelinkte lijst?

  • Een knooppunt verwijst altijd naar een ander knooppunt, dus NULL-toewijzing is niet nodig.
  • Elk knooppunt kan als startpunt worden ingesteld.
  • Knooppunten worden snel doorlopen van de eerste tot de laatste.

Volgende berichten: Circulaire gekoppelde lijst | Set 2 (doortocht) Circulaire enkelvoudig gekoppelde lijst | Plaatsing Schrijf alstublieft commentaar als u een bug in bovenstaande code/algoritme vindt, of zoek andere manieren om hetzelfde probleem op te lossen