logo

TechCodeview

Einführung in die zirkuläre verknüpfte Liste

Was ist eine kreisförmige verknüpfte Liste?

Der zirkuläre verknüpfte Liste ist eine verknüpfte Liste, bei der alle Knoten zu einem Kreis verbunden sind. In einer kreisförmig verknüpften Liste sind der erste und der letzte Knoten miteinander verbunden, wodurch ein Kreis entsteht. Am Ende steht kein NULL.

Zirkuläre verknüpfte Liste



Im Allgemeinen gibt es zwei Arten von zirkulär verknüpften Listen:

  • Zirkuläre einfach verknüpfte Liste: In einer zirkulären einfach verknüpften Liste enthält der letzte Knoten der Liste einen Zeiger auf den ersten Knoten der Liste. Wir durchlaufen die kreisförmige einfach verknüpfte Liste, bis wir denselben Knoten erreichen, an dem wir begonnen haben. Die kreisförmige einfach verknüpfte Liste hat keinen Anfang und kein Ende. Im nächsten Teil eines der Knoten ist kein Nullwert vorhanden.

Darstellung einer kreisförmigen einfach verknüpften Liste

  • Zirkuläre doppelt verkettete Liste: Eine kreisförmige doppelt verknüpfte Liste hat Eigenschaften sowohl einer doppelt verknüpften Liste als auch einer kreisförmig verknüpften Liste, in der zwei aufeinanderfolgende Elemente durch den vorherigen und den nächsten Zeiger verknüpft oder verbunden sind und der letzte Knoten durch den nächsten Zeiger auf den ersten Knoten zeigt und auch der erste Knoten darauf zeigt der letzte Knoten durch den vorherigen Zeiger.

Darstellung einer kreisförmigen doppelt verknüpften Liste



Notiz: Wir werden die einfach zirkulär verknüpfte Liste verwenden, um die Funktionsweise der zirkulär verknüpften Liste darzustellen.

Was ist Struktur in der Datenstruktur?

Darstellung einer zirkulären verknüpften Liste:

Zirkulär verknüpfte Listen ähneln einfach verknüpften Listen, mit der Ausnahme, dass der letzte Knoten mit dem ersten Knoten verbunden ist.

Knotendarstellung einer zirkulären verknüpften Liste:



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->data = $data;  $this->next = null;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Beispiel einer kreisförmigen einfach verknüpften Liste:

Beispiel einer zirkulär verknüpften Liste

Die obige kreisförmige einfach verknüpfte Liste kann wie folgt dargestellt werden:

Java-Zufallszahl
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->next = zwei; zwei->nächste = drei; three->next = one;>
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->next = $two; $two->next = $drei; $drei->nächstes = $eins;>
Python3 
# Initialize the Nodes. one = Node(3) two = Node(5) three = Node(9) # Connect nodes one.next = two two.next = three three.next = one>

Erläuterung: Im obigen Programm sind eins, zwei und drei die Knoten mit den Werten 3, 5 und 9, die wie folgt kreisförmig verbunden sind:

  • Für Knoten Eins: Der Next-Zeiger speichert die Adresse von Knoten zwei.
  • Für Knoten zwei: Der Next speichert die Adresse von Knoten drei
  • Für Knoten Drei: Der Next zeigt auf Knoten eins.

Operationen auf der zirkulären verknüpften Liste:

Wir können einige Operationen an der zirkulär verknüpften Liste durchführen, die der einfach verknüpften Liste ähneln:

  1. Einfügen
  2. Streichung

1. Einfügen in die zirkuläre verknüpfte Liste:

Ein Knoten kann auf drei Arten hinzugefügt werden:

  1. Einfügung am Anfang der Liste
  2. Einfügung am Ende der Liste
  3. Einfügung zwischen den Knoten

1) Einfügung am Anfang der Liste: Um einen Knoten am Anfang der Liste einzufügen, gehen Sie folgendermaßen vor:

  • Erstellen Sie einen Knoten, sagen wir T.
  • Machen Sie T -> next = last -> next.
  • letztes -> nächstes = T.

Zirkuläre verknüpfte Liste vor dem Einfügen

Und dann,

Zirkuläre verknüpfte Liste nach dem Einfügen

2) Einfügung am Ende der Liste: Um einen Knoten am Ende der Liste einzufügen, gehen Sie folgendermaßen vor:

  • Erstellen Sie einen Knoten, sagen wir T.
  • Machen Sie T -> next = last -> next;
  • letztes -> nächstes = T.
  • zuletzt = T.

Vor dem Einfügen,

Javafx auf Eclipse

Zirkuläre verknüpfte Liste vor dem Einfügen des Knotens am Ende

Nach dem Einfügen,

Zirkuläre verknüpfte Liste nach dem Einfügen eines Knotens am Ende

3) Einfügung zwischen den Knoten: Um einen Knoten zwischen den beiden Knoten einzufügen, gehen Sie folgendermaßen vor:

  • Erstellen Sie einen Knoten, sagen wir T.
  • Suchen Sie nach dem Knoten, nach dem T eingefügt werden muss, sagen wir, dieser Knoten ist P.
  • Machen Sie T -> next = P -> next;
  • P -> weiter = T.

Angenommen, 12 muss eingefügt werden, nachdem der Knoten den Wert 10 hat.

Zirkuläre verknüpfte Liste vor dem Einfügen

Nach dem Suchen und Einfügen,

Zirkuläre verknüpfte Liste nach dem Einfügen

Wann wurde die Schule erfunden?

2. Löschung in einer zirkulär verknüpften Liste:

1) Löschen Sie den Knoten nur, wenn er der einzige Knoten in der zirkulär verknüpften Liste ist:

  • Geben Sie den Speicher des Knotens frei
  • Der letzte Wert sollte NULL sein. Ein Knoten zeigt immer auf einen anderen Knoten, daher ist eine NULL-Zuweisung nicht erforderlich.
    Als Ausgangspunkt kann ein beliebiger Knotenpunkt festgelegt werden.
    Knoten werden vom ersten bis zum letzten schnell durchlaufen.

2) Löschen des letzten Knotens:

  • Suchen Sie den Knoten vor dem letzten Knoten (es sei temporär)
  • Behalten Sie die Adresse des Knotens neben dem letzten Knoten in temp bei
  • Letzten Speicher löschen
  • Stellen Sie am Ende die Temperatur ein

3) Löschen Sie einen beliebigen Knoten aus der zirkulär verknüpften Liste: Wir erhalten einen Knoten und unsere Aufgabe besteht darin, diesen Knoten aus der zirkulär verknüpften Liste zu löschen.

Algorithmus:
Fall 1 : Liste ist leer.

  • Wenn die Liste leer ist, kehren wir einfach zurück.

Fall 2 :Liste ist nicht leer

  • Wenn die Liste nicht leer ist, definieren wir zwei Zeiger akt Und vorh und initialisieren Sie den Zeiger akt mit dem Kopf Knoten.
  • Durchlaufen Sie die Liste mit akt Um den zu löschenden Knoten zu finden und vor dem Wechseln zu curr zum nächsten Knoten zu wechseln, setzen Sie jedes Mal prev = curr.
  • Wenn der Knoten gefunden wird, prüfen Sie, ob es der einzige Knoten in der Liste ist. Wenn ja, setze head = NULL und free(curr).
  • Wenn die Liste mehr als einen Knoten hat, prüfen Sie, ob es sich um den ersten Knoten der Liste handelt. Bedingung, um dies zu überprüfen (curr == head). Wenn ja, verschieben Sie prev, bis der letzte Knoten erreicht ist. Nachdem prev den letzten Knoten erreicht hat, setzen Sie head = head -> next und prev -> next = head. Akt. löschen
  • Wenn curr nicht der erste Knoten ist, prüfen wir, ob es der letzte Knoten in der Liste ist. Bedingung, um dies zu überprüfen, ist (curr -> next == head).
  • Wenn curr der letzte Knoten ist. Setze prev -> next = head und lösche den Knoten curr durch free(curr).
  • Wenn der zu löschende Knoten weder der erste noch der letzte Knoten ist, dann setze prev -> next = curr -> next und lösche curr.
  • Wenn der Knoten nicht in der Liste vorhanden ist, geben Sie den Kopf zurück und unternehmen Sie nichts.

Nachfolgend finden Sie die Implementierung für den oben genannten Ansatz:

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->Daten = Daten;  ptr1->next = *head_ref;  // Wenn die verknüpfte Liste nicht NULL ist, // setze den nächsten des letzten Knotens, wenn (*head_ref != NULL) { // Finde den Knoten vor dem Kopf und // aktualisiere den nächsten davon.  Node* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->next = ptr1;  } else // Für den ersten Knoten ptr1->next = ptr1;  *head_ref = ptr1; } // Funktion zum Drucken von Knoten in einer gegebenen // zirkulär verknüpften Liste void printList(Node* head) { Node* temp = head;  if (head != NULL) { do { cout<< temp->Daten<< ' ';  temp = temp->nächste;  } while (temp != head);  } cout<< 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 == key && (*head)->next == *head) { free(*head);  *head = NULL;  zurückkehren;  } Node *last = *head, *d;  // Wenn head gelöscht werden soll if ((*head)->data == key) { // Den letzten Knoten der Liste finden while (last->next != *head) last = last->next;  // Den letzten Knoten auf den nächsten // Kopf verweisen, d. h. den zweiten Knoten // der Liste last->next = (*head)->next;  frei(*Kopf);  *head = last->next;  zurückkehren;  } // Entweder wird der zu löschende Knoten // nicht gefunden oder das Ende der Liste // wird nicht erreicht while (last->next != *head && last->next->data != key) { last = last ->nächster;  } // Wenn der zu löschende Knoten gefunden wurde if (last->next->data == key) { d = last->next;  last->next = d->next;  befreit);  } sonst cout<< '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 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);  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->Daten = Daten;  ptr1->next = *head_ref;  // Wenn die verknüpfte Liste nicht NULL ist, // setze den nächsten des letzten Knotens, wenn (*head_ref != NULL) { // Finde den Knoten vor dem Kopf und // aktualisiere den nächsten davon.  struct Node* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->next = ptr1;  } else // Für den ersten Knoten ptr1->next = ptr1;  *head_ref = ptr1; } // Funktion zum Drucken von Knoten in einer gegebenen // zirkulär verknüpften Liste void printList(struct Node* head) { struct Node* temp = head;  if (head != NULL) { do { printf('%d ', temp->data);  temp = temp->next;  } while (temp != head);  } printf('
'); } // Funktion zum Löschen eines bestimmten Knotens // aus der Liste void deleteNode(struct Node** head, int key) { // Wenn die verknüpfte Liste leer ist if (*head == NULL) return;  // Wenn die Liste nur einen // einzelnen Knoten enthält if ((*head)->data == key && (*head)->next == *head) { free(*head);  *head = NULL;  zurückkehren;  } struct Node *last = *head, *d;  // Wenn head gelöscht werden soll if ((*head)->data == key) { // Den letzten Knoten der Liste finden while (last->next != *head) last = last->next;  // Den letzten Knoten auf den nächsten // Kopf verweisen, d. h. den zweiten Knoten // der Liste last->next = (*head)->next;  frei(*Kopf);  *head = last->next;  zurückkehren;  } // Entweder ist der zu löschende Knoten // nicht gefunden oder das Ende der Liste // ist nicht erreicht while (last->next != *head && last->next->data != key) { last = last ->nächster;  } // Wenn der zu löschende Knoten gefunden wurde if (last->next->data == key) { d = last->next;  last->next = d->next;  befreit);  } else printf('Angegebener Knoten wurde nicht in der Liste gefunden!!!
'); } // Treibercode int main() { // Listen als leer initialisieren struct Node* head = NULL;  // Die erstellte verknüpfte Liste lautet // 2->5->7->8->10 push(&head, 2);  push(&head, 5);  push(&head, 7);  push(&head, 8);  push(&head, 10);  printf('Liste vor dem Löschen: ');  printList(head);  deleteNode(&head, 7);  printf('Liste nach dem Löschen: ');  printList(head);  0 zurückgeben; }>
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 Push(ref head, 2);  Push(ref head, 5);  Push(ref head, 7);  Push(ref head, 8);  Push(ref head, 10);  Console.Write('Liste vor dem Löschen: ');  PrintList(head);  DeleteNode(ref head, 7);  Console.Write('Liste nach dem Löschen: ');  PrintList(head);  } }>
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 head = push(head, 2);  head = push(head, 5);  head = push(head, 7);  head = push(head, 8);  head = push(head, 10);  console.log('Liste vor dem Löschen: ');  printList(head);  deleteNode(head, 7);  console.log('Liste nach dem Löschen: ');  printList(head);>
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 head = push(head, 2) head = push(head, 5) head = push(head, 7) head = push(head, 8) head = push(head, 10) print('Liste vor dem Löschen: ') printList(head) deleteNode(head, 7) print('Liste nach dem Löschen: ') printList(head)>
Ausgabe 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Zeitkomplexität: O(N), der schlimmste Fall tritt ein, wenn das zu löschende Element das letzte Element ist und wir uns durch die gesamte Liste bewegen müssen.
Hilfsraum: O(1), Als Konstante wird zusätzlicher Platz verwendet.

Vorteile von zirkulär verknüpften Listen:

  • Jeder Knoten kann ein Ausgangspunkt sein. Wir können die gesamte Liste durchlaufen, indem wir von jedem Punkt aus beginnen. Wir müssen nur aufhören, wenn der erste besuchte Knoten erneut besucht wird.
  • Nützlich für die Implementierung einer Warteschlange. nicht wie Das Bei der Implementierung müssen wir nicht zwei Zeiger für vorne und hinten pflegen, wenn wir eine zirkulär verknüpfte Liste verwenden. Wir können einen Zeiger auf den zuletzt eingefügten Knoten beibehalten und die Vorderseite kann immer als vorletzter Knoten abgerufen werden.
  • Zirkuläre Listen sind in Anwendungen nützlich, um die Liste wiederholt zu durchlaufen. Wenn beispielsweise mehrere Anwendungen auf einem PC ausgeführt werden, ist es üblich, dass das Betriebssystem die ausgeführten Anwendungen in eine Liste einfügt und sie dann durchläuft, wobei es jeder Anwendung eine gewisse Zeit für die Ausführung gibt und sie dann eine Weile warten lässt die CPU wird einer anderen Anwendung übergeben. Für das Betriebssystem ist es praktisch, eine kreisförmige Liste zu verwenden, sodass es, wenn es das Ende der Liste erreicht, zum Anfang der Liste wechseln kann.
  • Zirkuläre doppelt verknüpfte Listen werden für die Implementierung erweiterter Datenstrukturen wie verwendet Fibonacci-Haufen .
  • Die Implementierung einer zirkulär verknüpften Liste kann im Vergleich zu anderen komplexeren Datenstrukturen wie Bäumen oder Diagrammen relativ einfach sein.

Nachteile einer zirkulären verknüpften Liste:

  • Im Vergleich zu einfach verknüpften Listen sind zirkuläre Listen komplexer.
  • Das Umkehren einer zirkulären Liste ist komplizierter als das einfache oder doppelte Umkehren einer zirkulären Liste.
  • Es ist möglich, dass der Code in eine Endlosschleife gerät, wenn er nicht sorgfältig gehandhabt wird.
  • Es ist schwieriger, das Ende der Liste zu finden und die Schleife zu kontrollieren.
  • Obwohl zirkulär verknüpfte Listen in bestimmten Anwendungen effizient sein können, kann ihre Leistung in bestimmten Fällen langsamer sein als die anderer Datenstrukturen, beispielsweise wenn die Liste sortiert oder durchsucht werden muss.
  • Zirkulär verknüpfte Listen bieten keinen direkten Zugriff auf einzelne Knoten

Anwendungen von zirkulär verknüpften Listen:

  • Multiplayer-Spiele nutzen dies, um jedem Spieler die Chance zu geben, mitzuspielen.
  • Eine zirkulär verknüpfte Liste kann verwendet werden, um mehrere laufende Anwendungen auf einem Betriebssystem zu organisieren. Diese Anwendungen werden vom Betriebssystem wiederholt.
  • Zirkular verknüpfte Listen können bei Ressourcenzuweisungsproblemen verwendet werden.
  • Zirkular verknüpfte Listen werden üblicherweise zur Implementierung von Ringpuffern verwendet.
  • Zirkular verknüpfte Listen können in Simulationen und Spielen verwendet werden.

Warum zirkulär verknüpfte Liste?

  • Ein Knoten zeigt immer auf einen anderen Knoten, daher ist eine NULL-Zuweisung nicht erforderlich.
  • Als Ausgangspunkt kann ein beliebiger Knotenpunkt festgelegt werden.
  • Knoten werden vom ersten bis zum letzten schnell durchlaufen.

Nächste Beiträge: Zirkuläre verknüpfte Liste | Satz 2 (Durchquerung) Zirkuläre einfach verknüpfte Liste | Einfügen Bitte schreiben Sie Kommentare, wenn Sie einen Fehler im obigen Code/Algorithmus finden oder andere Möglichkeiten zur Lösung des gleichen Problems finden