Menü

Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung

  • Haupt
  • Andere
  • Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung

doubly linked list data structure c with illustration

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Ein ausführliches Tutorial zur doppelt verknüpften Liste.

Eine doppelt verknüpfte Liste ist eine Variation der einfach verknüpften Liste. Wir sind uns bewusst, dass die einfach verknüpfte Liste eine Sammlung von Knoten ist, wobei jeder Knoten einen Datenteil und einen Zeiger hat, der auf den nächsten Knoten zeigt.

Eine doppelt verknüpfte Liste ist auch eine Sammlung von Knoten. Jeder Knoten besteht hier aus einem Datenteil und zwei Zeigern. Ein Zeiger zeigt auf den vorherigen Knoten, während der zweite Zeiger auf den nächsten Knoten zeigt.

=> Lesen Sie hier die ausführlichen C ++ - Schulungsanleitungen.

DOPPELVERBUNDENE LISTE

Was du lernen wirst:

In C ++ doppelt verknüpft

Wie in der einfach verknüpften Liste hat auch die doppelt verknüpfte Liste einen Kopf und einen Schwanz. Der vorherige Zeiger des Kopfes wird auf NULL gesetzt, da dies der erste Knoten ist. Der nächste Zeiger des Endknotens wird auf NULL gesetzt, da dies der letzte Knoten ist.

Ein Grundlayout der doppelt verknüpften Liste ist in der folgenden Abbildung dargestellt.

Ein Grundlayout der doppelt verknüpften Liste

In der obigen Abbildung sehen wir, dass jeder Knoten zwei Zeiger hat, von denen einer auf den vorherigen Knoten und der andere auf den nächsten Knoten zeigt. Nur der erste Knoten (Kopf) hat seinen vorherigen Knoten auf Null gesetzt und der letzte Knoten (Schwanz) hat seinen nächsten Zeiger auf Null gesetzt.

Da die doppelt verknüpfte Liste zwei Zeiger enthält, d. H. Vorherige und nächste, können wir sie in die Richtungen vorwärts und rückwärts durchlaufen. Dies ist der Hauptvorteil einer doppelt verknüpften Liste gegenüber der einfach verknüpften Liste.

Fragen zum Selen-Interview für 8 Jahre Erfahrung

Erklärung

In der Deklaration im C-Stil wird ein Knoten der doppelt verknüpften Liste wie folgt dargestellt:

struct node { struct node *prev; int data; struct node *next; };

Abgesehen von der obigen Deklaration können wir in C ++ auch einen Knoten in der doppelt verknüpften Liste als Klasse darstellen. Eine doppelt verknüpfte Liste wird als Klasse dargestellt, wenn wir STL in C ++ verwenden. Wir können eine doppelt verknüpfte Liste auch mit einer Klasse in Java implementieren.

Grundoperationen

Im Folgenden sind einige der Vorgänge aufgeführt, die wir für eine doppelt verknüpfte Liste ausführen können.

Einfügen

Durch das Einfügen der doppelt verknüpften Liste wird ein neuer Knoten in die verknüpfte Liste eingefügt. Abhängig von der Position, an der der neue Knoten eingefügt werden soll, können die folgenden Einfügevorgänge ausgeführt werden.

  • Einfügung vorne - Fügt einen neuen Knoten als ersten Knoten ein.
  • Einfügung am Ende - Fügt am Ende einen neuen Knoten als letzten Knoten ein.
  • Einfügen vor einem Knoten - Fügt bei einem gegebenen Knoten einen neuen Knoten vor diesem Knoten ein.
  • Einfügen nach einem Knoten - Fügt bei einem gegebenen Knoten einen neuen Knoten nach diesem Knoten ein.

Streichung

Durch das Löschen wird ein Knoten von einer bestimmten Position in der doppelt verknüpften Liste gelöscht.

  • Löschen des ersten Knotens - Löscht den ersten Knoten in der Liste
  • Löschen des letzten Knotens - Löscht den letzten Knoten in der Liste.
  • Löschen eines Knotens angesichts der Daten - Bei den gegebenen Daten vergleicht die Operation die Daten mit den Knotendaten in der verknüpften Liste und löscht diesen Knoten.

Durchquerung

Traversal ist eine Technik zum Besuchen jedes Knotens in der verknüpften Liste. In einer doppelt verknüpften Liste gibt es zwei Arten von Durchquerungen, da die doppelt verknüpfte Liste zwei Zeiger mit unterschiedlichen Richtungen enthält.

  • Vorwärtsdurchquerung - Das Durchlaufen erfolgt mit dem nächsten Zeiger in Vorwärtsrichtung.
  • Rückwärtsdurchquerung - Das Durchlaufen erfolgt mit dem vorherigen Zeiger, der die Rückwärtsrichtung darstellt.

Umkehren

Diese Operation kehrt die Knoten in der doppelt verknüpften Liste um, so dass der erste Knoten der letzte Knoten wird, während der letzte Knoten der erste Knoten wird.

Suche

Der Suchvorgang in der doppelt verknüpften Liste wird verwendet, um nach einem bestimmten Knoten in der verknüpften Liste zu suchen. Zu diesem Zweck müssen wir die Liste durchlaufen, bis übereinstimmende Daten gefunden werden.

Einfügen

Fügen Sie vorne einen Knoten ein

Fügen Sie vorne einen Knoten ein

Das Einfügen eines neuen Knotens am Anfang der Liste ist oben dargestellt. Wie zu sehen ist, wird der vorherige neue Knoten N auf Null gesetzt. Head zeigt auf den neuen Knoten. Der nächste Zeiger von N zeigt jetzt auf N1 und der vorherige von N1, der früher auf Null zeigte, zeigt jetzt auf N.

Knoten am Ende einfügen

Knoten am Ende einfügen

Das Einfügen eines Knotens am Ende der doppelt verknüpften Liste erfolgt durch Zeigen des nächsten Zeigers des neuen Knotens N auf Null. Der vorherige Zeiger von N zeigt auf N5. Der 'Next'-Zeiger von N5 zeigt auf N.

Fügen Sie den Knoten vor / nach dem angegebenen Knoten ein

Fügen Sie den Knoten vor und nach dem angegebenen Knoten ein

Wie im obigen Diagramm gezeigt, ändern wir, wenn wir einen Knoten vor oder nach einem bestimmten Knoten hinzufügen müssen, den vorherigen und den nächsten Zeiger des Vorher- und Nachher-Knotens, um entsprechend auf den neuen Knoten zu zeigen. Außerdem werden die neuen Knotenzeiger entsprechend auf die vorhandenen Knoten gezeigt.

Das folgende C ++ - Programm demonstriert alle oben genannten Methoden zum Einfügen von Knoten in die doppelt verknüpfte Liste.

#include using namespace std; // A doubly linked list node struct Node { int data; struct Node* next; struct Node* prev; }; //inserts node at the front of the list void insert_front(struct Node** head, int new_data) { //allocate memory for New node struct Node* newNode = new Node; //assign data to new node newNode->data = new_data; //new node is head and previous is null, since we are adding at the front newNode->next = (*head); newNode->prev = NULL; //previous of head is new node if ((*head) != NULL) (*head)->prev = newNode; //head points to new node (*head) = newNode; } /* Given a node as prev_node, insert a new node after the given node */ void insert_After(struct Node* prev_node, int new_data) { //check if prev node is null if (prev_node == NULL) { coutnext = prev_node->next; //set next of prev node to newnode prev_node->next = newNode; //now set prev of newnode to prev node newNode->prev = prev_node; //set prev of new node's next to newnode if (newNode->next != NULL) newNode->next->prev = newNode; } //insert a new node at the end of the list void insert_end(struct Node** head, int new_data) { //allocate memory for node struct Node* newNode = new Node; struct Node* last = *head; //set last node value to head //set data for new node newNode->data = new_data; //new node is the last node , so set next of new node to null newNode->next = NULL; //check if list is empty, if yes make new node the head of list if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } //otherwise traverse the list to go to last node while (last->next != NULL) last = last->next; //set next of last to new node last->next = newNode; //set last to prev of new node newNode->prev = last; return; } // This function prints contents of linked list starting from the given node void displayList(struct Node* node) { struct Node* last; while (node != NULL) { coutnext; } if(node == NULL) cout

Ausgabe:

Die doppelt verknüpfte Liste lautet wie folgt:

1020304050NULL

Das obige Programm erstellt eine doppelt verknüpfte Liste durch Einfügen der Knoten unter Verwendung von drei Einfügemethoden, d. H. Einfügen des Knotens an der Vorderseite, Einfügen des Knotens am Ende und Einfügen des Knotens nach dem angegebenen Knoten.

Als nächstes demonstrieren wir den gleichen Vorgang wie eine Java-Implementierung.

// Java Class for Doubly Linked List class Doubly_linkedList { Node head; // list head /* Doubly Linked list Node*/ class Node { int data; Node prev; Node next; //create a new node using constructor Node(int d) { data = d; } } // insert a node at the front of the list public void insert_front(int new_data) { /* 1. allocate node * 2. put in the data */ Node new_Node = new Node(new_data); /* 3. Make next of new node as head and previous as NULL */ new_Node.next = head; new_Node.prev = null; /* 4. change prev of head node to new node */ if (head != null) head.prev = new_Node; /* 5. move the head to point to the new node */ head = new_Node; } //insert a node after the given prev node public void Insert_After(Node prev_Node, int new_data) { //check that prev node is not null if (prev_Node == null) { System.out.println('The previous node is required,it cannot be NULL '); return; } //allocate new node and set it to data Node newNode = new Node(new_data); //set next of newNode as next of prev node newNode.next = prev_Node.next; //set new node to next of prev node prev_Node.next = newNode; //set prev of newNode as prev node newNode.prev = prev_Node; //set prev of new node's next to newnode if (newNode.next != null) newNode.next.prev = newNode; } // Add a node at the end of the list void insert_end(int new_data) { //allocate the node and set the data Node newNode = new Node(new_data); Node last = head; //set last as the head //set next of new node to null since its the last node newNode.next = null; //set new node as head if the list is null if (head == null) { newNode.prev = null; head = newNode; return; } //if list is not null then traverse it till the last node and set last next to last while (last.next != null) last = last.next; last.next = newNode; //set last next to new node newNode.prev = last; //set last as prev of new node } // display the contents of linked list starting from the given node public void displaylist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + ''); last = node; node = node.next; } if(node == null) System.out.print('null'); System.out.println(); } } class Main{ public static void main(String() args) { /* Start with the empty list */ Doubly_linkedList dll = new Doubly_linkedList(); // Insert 40. dll.insert_end(40); // Insert 20 at the beginning. dll.insert_front(20); // Insert 10 at the beginning. dll.insert_front(10); // Insert 50 at the end. dll.insert_end(50); // Insert 30, after 20. dll.Insert_After(dll.head.next, 30); System.out.println('Doubly linked list created is as follows: '); dll.displaylist(dll.head); } }

Ausgabe:

Die doppelt verknüpfte Liste wurde wie folgt erstellt:

Testfälle in Beispielen für Softwaretests

1020304050null

Streichung

Ein Knoten kann aus einer doppelt verknüpften Liste von einer beliebigen Position wie der Vorderseite, dem Ende oder einer anderen bestimmten Position oder von bestimmten Daten gelöscht werden.

Wenn Sie einen Knoten aus der doppelt verknüpften Liste löschen, positionieren Sie zuerst den Zeiger neu, der auf diesen bestimmten Knoten zeigt, sodass die vorherigen und nachfolgenden Knoten keine Verbindung zu dem zu löschenden Knoten haben. Wir können den Knoten dann einfach löschen.

Betrachten Sie die folgende doppelt verknüpfte Liste mit drei Knoten A, B, C. Nehmen wir an, wir müssen den Knoten B löschen.

doppelt verknüpfte Liste mit drei Knoten A, B, C.

Wie in der obigen Reihe des Diagramms gezeigt, haben wir das Löschen von Knoten B aus der gegebenen verknüpften Liste demonstriert. Die Reihenfolge der Operationen bleibt gleich, auch wenn der Knoten der erste oder der letzte ist. Die einzige Vorsicht, die beachtet werden sollte, besteht darin, dass beim Löschen des ersten Knotens der vorherige Zeiger des zweiten Knotens auf Null gesetzt wird.

In ähnlicher Weise wird beim Löschen des letzten Knotens der nächste Zeiger des vorherigen Knotens auf Null gesetzt. Wenn zwischen den Knoten gelöscht wird, ist die Reihenfolge wie oben.

Wir verlassen das Programm, um einen Knoten aus einer doppelt verknüpften Liste zu löschen. Beachten Sie, dass die Implementierung den Zeilen der Einfügeimplementierung entspricht.

Doppelt verknüpfte Liste umkehren

Das Umkehren einer doppelt verknüpften Liste ist eine wichtige Operation. In diesem Fall tauschen wir einfach den vorherigen und den nächsten Zeiger aller Knoten aus und tauschen auch die Kopf- und Endzeiger aus.

Im Folgenden finden Sie eine doppelt verknüpfte Liste:

Doppelt verknüpfte Liste umkehren

Die folgende C ++ - Implementierung zeigt die doppelt verknüpfte umgekehrte Liste.

#include using namespace std; //node declaration for doubly linked list struct Node { int data; struct Node *prev, *next; }; Node* newNode(int val) { Node* temp = new Node; temp->data = val; temp->prev = temp->next = nullptr; return temp; } void displayList(Node* head) { while (head->next != nullptr) { cout next; } cout next = *head; (*head)->prev = temp; (*head) = temp; } // reverse the doubly linked list void reverseList(Node** head) { Node* left = *head, * right = *head; // traverse entire list and set right next to right while (right->next != nullptr) right = right->next; //swap left and right data by moving them towards each other till they meet or cross while (left != right && left->prev != right) { // Swap left and right pointer data swap(left->data, right->data); // Advance left pointer left = left->next; // Advance right pointer right = right->prev; } } int main() { Node* headNode = newNode(5); insert(&headNode, 4); insert(&headNode, 3); insert(&headNode, 2); insert(&headNode, 1); cout << 'Original doubly linked list: ' << endl; displayList(headNode); cout << 'Reverse doubly linked list: ' << endl; reverseList(&headNode); displayList(headNode); return 0; }

Ausgabe:

Ursprüngliche doppelt verknüpfte Liste:

1 2 3 4 5

Doppelt verknüpfte Liste umkehren:

5 4 3 2 1

Hier tauschen wir den linken und den rechten Zeiger aus und bewegen sie aufeinander zu, bis sie sich treffen oder kreuzen. Dann werden der erste und der letzte Knoten vertauscht.

Das nächste Programm ist die Java-Implementierung zum Umkehren einer doppelt verknüpften Liste. In diesem Programm verwenden wir auch das Vertauschen des linken und rechten Knotens wie in unserem vorherigen Programm.

// Java Program to Reverse a doubly linked List using Data Swapping class Main{ static class Node { int data; Node prev, next; }; static Node newNode(int new_data) { Node temp = new Node(); temp.data = new_data; temp.prev = temp.next = null; return temp; } static void displayList(Node head) { while (head.next != null) { System.out.print(head.data+ ' '); head = head.next; } System.out.println( head.data ); } // Insert a new node at the head of the list static Node insert(Node head, int new_data) { Node temp = newNode(new_data); temp.next = head; (head).prev = temp; (head) = temp; return head; } // Function to reverse the list static Node reverseList(Node head) { Node left = head, right = head; // traverse the list, set right pointer to end of list while (right.next != null) right = right.next; // move left and right pointers and swap their data till they meet or cross each other while (left != right && left.prev != right) { // Swap data of left and right pointer int t = left.data; left.data = right.data; right.data = t; left = left.next; // Advance left pointer right = right.prev; // Advance right pointer } return head; } public static void main(String args()) { Node headNode = newNode(5); headNode = insert(headNode, 4); headNode = insert(headNode, 3); headNode = insert(headNode, 2); headNode = insert(headNode, 1); System.out.println('Original doubly linked list:'); displayList(headNode); System.out.println('Reversed doubly linked list:'); headNode=reverseList(headNode); displayList(headNode); } }

Ausgabe:

Ursprüngliche doppelt verknüpfte Liste:

1 2 3 4 5

Umgekehrte doppelt verknüpfte Liste:

5 4 3 2 1

Vor- / Nachteile gegenüber einfach verknüpfter Liste

Lassen Sie uns einige der Vor- und Nachteile einer doppelt verknüpften Liste gegenüber der einfach verknüpften Liste diskutieren.

Vorteile:

  • Die doppelt verknüpfte Liste kann sowohl in Vorwärts- als auch in Rückwärtsrichtung durchlaufen werden, im Gegensatz zu einfach verknüpften Listen, die nur in Vorwärtsrichtung durchlaufen werden können.
  • Die Löschoperation in einer doppelt verknüpften Liste ist effizienter als eine einzelne Liste, wenn ein bestimmter Knoten angegeben ist. In einer einfach verknüpften Liste müssen wir manchmal die Liste durchlaufen, um den vorherigen Knoten zu finden, da wir einen vorherigen Knoten benötigen, um den angegebenen Knoten zu löschen. Dies trifft die Leistung.
  • Der Einfügevorgang kann im Vergleich zur einfach verknüpften Liste problemlos in einer doppelt verknüpften Liste durchgeführt werden.

Nachteile:

  • Da die doppelt verknüpfte Liste einen zusätzlichen Zeiger enthält, d. H. Vorherige, ist der von der doppelt verknüpften Liste belegte Speicherplatz im Vergleich zur einfach verknüpften Liste größer.
  • Da zwei Zeiger vorhanden sind, d. H. Vorherige und nächste, müssen alle Operationen, die an der doppelt verknüpften Liste ausgeführt werden, sich um diese Zeiger kümmern und sie beibehalten, was zu einem Leistungsengpass führt.

Anwendungen der doppelt verknüpften Liste

Eine doppelt verknüpfte Liste kann in verschiedenen realen Szenarien und Anwendungen angewendet werden, wie unten erläutert.

  • Ein Kartenspiel in einem Spiel ist ein klassisches Beispiel für eine doppelt verknüpfte Liste. Da für jede Karte in einem Kartenspiel die vorherige und die nächste Karte nacheinander angeordnet sind, kann dieses Kartenspiel mithilfe einer doppelt verknüpften Liste leicht dargestellt werden.
  • Browserverlauf / Cache - Der Browser-Cache verfügt über eine Sammlung von URLs und kann mit den Vorwärts- und Zurück-Schaltflächen navigiert werden. Dies ist ein weiteres gutes Beispiel, das als doppelt verknüpfte Liste dargestellt werden kann.
  • Zuletzt verwendet (MRU) kann auch als doppelt verknüpfte Liste dargestellt werden.
  • Andere Datenstrukturen wie Stacks, Hash-Tabelle und der Binärbaum können ebenfalls mithilfe einer doppelt verknüpften Liste erstellt oder programmiert werden.

Fazit

Eine doppelt verknüpfte Liste ist eine Variation der einfach verknüpften Liste. Es unterscheidet sich von der einfach verknüpften Liste darin, dass jeder Knoten zusammen mit dem nächsten Zeiger einen zusätzlichen Zeiger auf den vorherigen Knoten enthält.

Dieses Vorhandensein eines zusätzlichen Zeigers erleichtert das Einfügen und Löschen von Operationen in der doppelt verknüpften Liste, erfordert jedoch gleichzeitig zusätzlichen Speicher zum Speichern dieser zusätzlichen Zeiger.

Wie bereits erwähnt, hat die doppelt verknüpfte Liste verschiedene Verwendungsmöglichkeiten in Echtzeitszenarien wie Browser-Cache, MRUs usw. Wir können auch andere Datenstrukturen wie Bäume, Hash-Tabellen usw. mithilfe einer doppelt verknüpften Liste darstellen.

In unserem nächsten Tutorial erfahren Sie mehr über die Circular Linked List.

=> Lesen Sie hier die beliebte C ++ - Schulungsserie.

Literatur-Empfehlungen

^