Menü

Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung

  • Haupt
  • Andere
  • Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung

circular linked list data structure c with illustration

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Eine vollständige Übersicht über die zirkuläre verknüpfte Liste.

Eine zirkuläre verknüpfte Liste ist eine Variation der verknüpften Liste. Es ist eine verknüpfte Liste, deren Knoten so verbunden sind, dass sie einen Kreis bilden.

In der zirkular verknüpften Liste wird der nächste Zeiger des letzten Knotens nicht auf Null gesetzt, sondern enthält die Adresse des ersten Knotens, wodurch ein Kreis gebildet wird.

=> Besuchen Sie hier, um C ++ von Grund auf neu zu lernen.

Zirkuläre verknüpfte Liste

Was du lernen wirst:

Zirkuläre verknüpfte Liste in C ++

Die unten gezeigte Anordnung gilt für eine einfach verknüpfte Liste.

einfach verknüpfte Liste

Eine zirkuläre verknüpfte Liste kann eine einfach verknüpfte Liste oder eine doppelt verknüpfte Liste sein. In einer doppelt kreisförmig verknüpften Liste ist der vorherige Zeiger des ersten Knotens mit dem letzten Knoten verbunden, während der nächste Zeiger des letzten Knotens mit dem ersten Knoten verbunden ist.

Die Darstellung ist unten dargestellt.

doppelt zirkuläre verknüpfte Liste

Erklärung

Wir können einen Knoten in einer zirkular verknüpften Liste wie jeden anderen Knoten deklarieren, wie unten gezeigt:

struct Node { int data; struct Node *next; };

Um die zirkuläre verknüpfte Liste zu implementieren, pflegen wir einen externen Zeiger 'last', der auf den letzten Knoten in der zirkulären verknüpften Liste zeigt. Daher zeigt last-> next auf den ersten Knoten in der verknüpften Liste.

Auf diese Weise stellen wir sicher, dass beim Einfügen eines neuen Knotens am Anfang oder am Ende der Liste nicht die gesamte Liste durchlaufen werden muss. Dies liegt daran, dass der letzte auf den letzten Knoten zeigt, während last-> next auf den ersten Knoten zeigt.

Dies wäre nicht möglich gewesen, wenn wir den externen Zeiger auf den ersten Knoten gerichtet hätten.

Grundoperationen

Die zirkuläre verknüpfte Liste unterstützt das Einfügen, Löschen und Durchlaufen der Liste. Wir werden jetzt jede der Operationen im Detail besprechen.

Einfügen

Wir können einen Knoten in eine zirkuläre verknüpfte Liste entweder als ersten Knoten (leere Liste), am Anfang, am Ende oder zwischen den anderen Knoten einfügen. Lassen Sie uns jede dieser Einfügevorgänge anhand einer bildlichen Darstellung unten sehen.

# 1) In eine leere Liste einfügen

In eine leere Liste einfügen

Wenn die kreisförmige Liste keine Knoten enthält und die Liste leer ist, der letzte Zeiger null ist, fügen wir einen neuen Knoten N ein, indem wir den letzten Zeiger wie oben gezeigt auf den Knoten N zeigen. Der nächste Zeiger von N zeigt auf den Knoten N selbst, da es nur einen Knoten gibt. Somit wird N sowohl der erste als auch der letzte Knoten in der Liste.

# 2) Am Anfang der Liste einfügen

Am Anfang der Liste einfügen

Wie in der obigen Darstellung gezeigt, zeigt der nächste Zeiger des letzten Knotens auf den neuen Knoten N, wenn wir einen Knoten am Anfang der Liste hinzufügen, wodurch er zu einem ersten Knoten wird.

N-> next = last-> next

Last-> next = N.

# 3) Am Ende der Liste einfügen

Der letzte Knoten zeigt auf den neuen Knoten

Um einen neuen Knoten am Ende der Liste einzufügen, gehen Sie folgendermaßen vor:

Wie kann ich eine EPS-Datei anzeigen?

N-> next = last -> next;
last -> next = N.
last = N.

# 4) Zwischen die Liste einfügen

Zwischen die Liste einfügen

Angenommen, wir müssen einen neuen Knoten N zwischen N3 und N4 einfügen. Zuerst müssen wir die Liste durchlaufen und den Knoten suchen, nach dem der neue Knoten eingefügt werden soll, in diesem Fall sein N3.

Nachdem der Knoten gefunden wurde, führen wir die folgenden Schritte aus.

N -> next = N3 -> next;
N3 -> next = N.

Dies fügt einen neuen Knoten N nach N3 ein.

Streichung

Der Löschvorgang der zirkular verknüpften Liste umfasst das Auffinden des zu löschenden Knotens und das Freigeben seines Speichers.

Dazu pflegen wir zwei zusätzliche Zeiger curr und prev und durchlaufen dann die Liste, um den Knoten zu lokalisieren. Der angegebene zu löschende Knoten kann der erste Knoten, der letzte Knoten oder der dazwischen liegende Knoten sein. Abhängig von der Position setzen wir die aktuellen und vorherigen Zeiger und löschen dann den aktuellen Knoten.

Eine bildliche Darstellung des Löschvorgangs ist unten dargestellt.

Löschvorgang

Durchquerung

Traversal ist eine Technik zum Besuchen jedes einzelnen Knotens. In linear verknüpften Listen wie einfach verknüpften Listen und doppelt verknüpften Listen ist das Durchlaufen einfach, da wir jeden Knoten besuchen und anhalten, wenn NULL auftritt.

Dies ist jedoch in einer zirkulären verknüpften Liste nicht möglich. In einer zirkulären verknüpften Liste beginnen wir am nächsten des letzten Knotens, der der erste Knoten ist, und durchlaufen jeden Knoten. Wir hören auf, als wir wieder den ersten Knoten erreichen.

Jetzt präsentieren wir eine Implementierung der zirkular verknüpften Listenoperationen mit C ++ und Java. Wir haben hier Einfüge-, Lösch- und Durchlaufoperationen implementiert. Zum besseren Verständnis haben wir die zirkuläre verknüpfte Liste als dargestellt

Durchquerung

Somit fügen wir dem letzten Knoten 50 wieder den Knoten 10 hinzu, der der erste Knoten ist, und geben ihn dadurch als eine kreisförmig verknüpfte Liste an.

#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 '<

Ausgabe:

Die kreisförmige verknüpfte Liste lautet wie folgt:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Der Knoten mit den Daten 10 wird aus der Liste gelöscht

Die zirkuläre verknüpfte Liste nach dem Löschen von 10 lautet wie folgt:

20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20

Als Nächstes präsentieren wir eine Java-Implementierung für die Operationen mit zirkulären verknüpften Listen.

//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); } }

Ausgabe:

Eine kreisförmig verknüpfte Liste wurde erstellt:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Nach dem Löschen von 40 lautet die zirkuläre Liste:

10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10

Vorteile Nachteile

Lassen Sie uns einige Vor- und Nachteile der zirkulären verknüpften Liste diskutieren.

Vorteile:

  • Wir können zu jedem Knoten gehen und von jedem Knoten aus durchqueren. Wir müssen nur anhalten, wenn wir denselben Knoten erneut besuchen.
  • Wenn der letzte Knoten auf den ersten Knoten zeigt, dauert es nur einen einzigen Schritt, vom letzten Knoten zum ersten Knoten zu wechseln.

Nachteile:

  • Das Umkehren einer zirkulären verknüpften Liste ist umständlich.
  • Da die Knoten zu einem Kreis verbunden sind, gibt es keine richtige Markierung für Anfang oder Ende der Liste. Daher ist es schwierig, das Ende der Liste oder der Schleifensteuerung zu finden. Wenn dies nicht beachtet wird, kann eine Implementierung in einer Endlosschleife enden.
  • Wir können nicht in einem einzigen Schritt zum vorherigen Knoten zurückkehren. Wir müssen die gesamte Liste von Anfang an durchlaufen.

Anwendungen der zirkulären verknüpften Liste

  • Die Echtzeitanwendung einer zirkular verknüpften Liste kann ein Betriebssystem mit mehreren Programmierungen sein, bei dem mehrere Programme geplant werden. Jedes Programm erhält einen eigenen Zeitstempel, nach dem die Ressourcen an ein anderes Programm übergeben werden. Dies geschieht kontinuierlich in einem Zyklus. Diese Darstellung kann effizient unter Verwendung einer zirkulären verknüpften Liste erreicht werden.
  • Spiele, die mit mehreren Spielern gespielt werden, können auch mithilfe einer kreisförmigen verknüpften Liste dargestellt werden, in der jeder Spieler ein Knoten ist, dem die Möglichkeit zum Spielen gegeben wird.
  • Wir können eine zirkuläre verknüpfte Liste verwenden, um eine zirkuläre Warteschlange darzustellen. Auf diese Weise können wir die beiden Zeiger vorne und hinten entfernen, die für die Warteschlange verwendet werden. Stattdessen können wir nur einen Zeiger verwenden.

Fazit

Eine kreisförmige verknüpfte Liste ist eine Sammlung von Knoten, in denen die Knoten miteinander verbunden sind, um einen Kreis zu bilden. Dies bedeutet, dass der nächste Zeiger des letzten Knotens nicht auf Null gesetzt wird, sondern mit dem ersten Knoten verknüpft ist.

Eine zirkuläre verknüpfte Liste ist hilfreich bei der Darstellung von Strukturen oder Aktivitäten, die nach einem bestimmten Zeitintervall wie Programme in einer Multiprogrammierumgebung immer wieder wiederholt werden müssen. Dies ist auch zum Entwerfen einer kreisförmigen Warteschlange von Vorteil.

Zirkular verknüpfte Listen unterstützen verschiedene Vorgänge wie Einfügen, Löschen und Durchlaufen. Daher haben wir die Operationen in diesem Tutorial im Detail gesehen.

In unserem nächsten Thema zu Datenstrukturen lernen wir die Stack-Datenstruktur kennen.

=> Hier finden Sie A-Z der C ++ - Schulungsanleitungen.

Literatur-Empfehlungen

^