Doppelt verknüpfte Liste: C++, Python (Codebeispiel)

Was ist eine doppelt verkettete Liste?

In einer doppelt verknüpften Liste verfügt jeder Knoten über Links sowohl zum vorherigen als auch zum nächsten Knoten. Jeder Knoten besteht aus drei Elementen: eines enthält die Daten und zwei weitere sind die Zeiger des nächsten und des vorherigen Knotens. Diese beiden Zeiger helfen uns, von einem bestimmten Knoten aus vorwärts oder rückwärts zu gehen.

Hier ist die Grundstruktur der doppelt verknüpften Liste.

Struktur einer doppelt verknüpften Liste
Struktur einer doppelt verknüpften Liste

Jede verknüpfte Liste hat einen Kopf- und einen Endknoten. Der Kopfknoten hat keinen „vorherigen“ Knoten (vorheriger Zeiger) und der Endknoten hat keinen „nächsten“ Knoten.

Hier sind einige wichtige Begriffe für eine doppelt verkettete Liste:

  • Zurück: Jeder Knoten ist mit seinem vorherigen Knoten verknüpft. Es wird als Zeiger oder Link verwendet.
  • Nächster: Jeder Knoten ist mit seinem nächsten Knoten verknüpft. Es wird als Zeiger oder Link verwendet.
  • Datum: Dies wird verwendet, um Daten in einem Knoten zu speichern. „Daten“ können andere enthalten Datenstrukturen im Inneren. Beispielsweise können Zeichenfolgen, Wörterbücher, Sätze, Hashmaps usw. in den „Daten“ gespeichert werden.

Hier ist die Grundstruktur eines einzelnen Knotens in der doppelt verknüpften Liste:

Struktur eines Knotens in einer doppelt verknüpften Liste

Struktur eines Knotens in einer doppelt verknüpften Liste

Operationen einer doppelt verknüpften Liste

Zu den Vorgängen einer doppelt verknüpften Liste gehören das Hinzufügen und Löschen von Knoten, das Einfügen und Entfernen von Knoten sowie das Durchlaufen der verknüpften Liste von oben nach unten.

Hier ist die Liste der Operationen, die wir mithilfe der doppelt verknüpften Liste implementieren können:

  • Einschub vorne
  • Einfügung in den Schwanz oder letzten Knoten
  • Einfügung nach einem Knoten
  • Einfügung vor einem Knoten
  • Löschung von vorne
  • Löschung vom Schwanz
  • Suchen und löschen Sie einen Knoten
  • Von Kopf bis Schwanz queren
  • Schwanz zum Kopf kreuzen

Wir werden die Implementierung und den Pseudocode für alle oben genannten Operationen sehen.

Einfügung vor der doppelt verknüpften Liste

Das Einfügen vorn bedeutet, dass wir einen Knoten in der verknüpften Liste erstellen und ihn am Anfang der verknüpften Liste platzieren müssen.

Beispielsweise gibt es einen gegebenen Knoten „15“. Wir müssen dies zum Hauptknoten hinzufügen.

Bei diesem Vorgang gelten zwei wichtige Bedingungen:

  1. Der neue Knoten ist der Hauptknoten, wenn in der doppelt verknüpften Liste kein Knoten vorhanden ist.
  2. Wenn bereits ein Kopfknoten vorhanden ist, wird der vorherige Kopfknoten durch den neuen Knoten ersetzt.

Hier ist der Pseudocode für diesen Vorgang:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead
Einfügung in den Frontknoten
Einfügung in den vorderen Knoten

Einfügung am Ende der doppelt verknüpften Liste

„Einfügung am Ende“ bedeutet, dass wir einen Knoten in der verknüpften Liste erstellen und ihn am Ende platzieren.

Um dies durchzuführen, können wir zwei Methoden verwenden:

  • Verfahren 1: Beginnen Sie mit dem Durchlaufen vom Kopf der doppelt verknüpften Liste, bis das „nächste“ null wird. Verknüpfen Sie dann den neuen Knoten mit dem „nächsten“.
  • Verfahren 2: Nehmen Sie den letzten Knoten der doppelt verknüpften Liste. Dann wird der „nächste“ Knoten des letzten Knotens mit dem neuen Knoten verknüpft. Jetzt wird der neue Knoten der Endknoten sein.

Hier ist der Pseudocode zum Einfügen am Endknoten:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
	then ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead
Einfügung am Ende der verknüpften Liste

Einfügung am Ende der verknüpften Liste

Einfügung nach einem Knoten

Nehmen wir an, wir haben eine doppelt verknüpfte Liste wie die folgendewing:

Einfügen nach einem Knoten

Wir möchten einen bestimmten Knoten einfügen, der nach dem Knoten mit dem Wert „12“ verknüpft werden soll.

Hier sind die Schritte dafür:

Schritt 1) Vom Kopf zum letzten Knoten durchlaufen. Überprüfen Sie, welcher Knoten den Wert „12“ hat.

Schritt 2) Erstellen Sie einen neuen Knoten und weisen Sie ihn als nächsten Zeiger des Knotens „12“ zu. Der „nächste“ Knoten des neuen Knotens wird 15 sein.

Hier ist der Pseudocode zum Einfügen eines Knotens nach einem Knoten in einer doppelt verknüpften Liste:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.value is not equal searchItem
	then List = ListHead.next
  List = List.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode
Einfügen nach einem Knoten

Einfügen nach einem Knoten

Einfügung vor einem Knoten

Diese Operation ähnelt eher dem „Einfügen nach einem Knoten“. Dazu müssen wir nach dem Wert eines bestimmten Knotens suchen. Dann erstellen wir einen neuen Knoten und fügen ihn vor dem gesuchten Knoten ein.

Nehmen wir an, wir möchten einen bestimmten Knoten „15“ vor dem Knoten „12“ einfügen. Dann sind hier die Schritte dazu:

Schritt 1) Durchlaufen Sie die verknüpfte Liste vom Kopfknoten zum Endknoten.

Schritt 2) Überprüfen Sie, ob der nächste Zeiger des aktuellen Knotens den Wert „12“ hat oder nicht.

Schritt 3) Fügen Sie den neuen Knoten als „nächsten“ Knoten des aktuellen Knotens ein.

Hier ist der Pseudocode zum Einfügen eines Knotens vor einem Knoten in einer doppelt verknüpften Liste:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.next.value is not equal searchItem
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode
Einfügen eines Knotens vor einem Knoten

Einfügen eines Knotens vor einem Knoten

Löschen Sie den Kopf der doppelt verknüpften Liste

Der Hauptknoten in der doppelt verknüpften Liste, der keinen vorherigen Knoten hat. Der nächste Zeiger ist also der neue Kopfknoten, wenn wir den Kopfknoten löschen möchten. Wir müssen auch den von einem Knoten belegten Speicher freigeben, während wir einen Knoten löschen.

Hier sind die Schritte zum Löschen des Hauptknotens:

Schritt 1) Weisen Sie dem aktuellen Hauptknoten eine Variable zu.

Schritt 2) Besuchen Sie den „nächsten“ Knoten des aktuellen Hauptknotens und machen Sie den „vorherigen“ Knoten (vorheriger Zeiger) zu „NULL“. Das bedeutet, dass wir den zweiten Knoten vom ersten Knoten trennen.

Schritt 3) Geben Sie den vom vorherigen Hauptknoten belegten Speicher frei.

Hier ist der Pseudocode zum Löschen des Kopfes aus einer doppelt verknüpften Liste:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead
Löschen des Hauptknotens

Löschen des Hauptknotens

Nach jedem Löschvorgang muss der zugewiesene Speicher gelöscht werden. Andernfalls bleibt während der gesamten Laufzeit des Programms der Speicher für den gelöschten Block belegt. Keine andere Anwendung kann dieses Speichersegment verwenden.

Löschen Sie das Ende der doppelt verknüpften Liste.

Dieser Vorgang ähnelt in gewisser Weise dem Löschen des Kopfes. Hier müssen wir anstelle des Kopfes den Schwanz löschen. Um einen Knoten als Endknoten zu identifizieren, sollten wir prüfen, ob der nächste Zeiger oder nächste Knoten null ist oder nicht. Nachdem wir den Schwanz gelöscht haben, müssen wir den Speicher freigeben.

Dieser Vorgang wird auch als „Löschen von hinten“ bezeichnet.

Hier sind die Schritte dazu:

Schritt 1) Durchlaufen Sie bis zum Endknoten der doppelt verknüpften Liste.

Schritt 2) Weisen Sie dem Endknoten eine Variable oder einen Zeiger zu.

Schritt 3) Machen Sie den „nächsten“ Knoten zu NULL und geben Sie den Speicher des Endknotens frei.

Hier ist der Pseudocode zum Löschen des Endknotens:

function DeleteTail( ListHead ):
  head = ListHead
  while ListHead.next is not NULL:
	ListHead = ListHead.next
  Tail = ListHead.next
  ListHead.next = NULL
  free memory( Tail )
  return head

Löschen Sie den Schwanz der doppelten Verknüpfung

Suchen und löschen Sie einen Knoten aus der doppelt verknüpften Liste

Mit dieser Operation können wir nach bestimmten Knotendaten suchen und diesen Knoten löschen. Wir müssen eine lineare Suche durchführen, da die verknüpfte Liste eine lineare Datenstruktur ist. Nach dem Löschen müssen wir auch den Speicher freigeben.

Here’re the steps for searching and deleting a node in the doubly linked list:

Schritt 1) Durchlaufen Sie die verknüpfte Liste vom Kopf bis der Wert des Knotens dem Suchelement entspricht.

Schritt 2) Weisen Sie dem übereinstimmenden Knoten eine Variable „deleteNode“ zu.

Schritt 3) Weisen Sie den vorherigen Knoten des „deleteNode“ dem nächsten Knoten zu.

Schritt 4) Den Speicher des „deleteNode“ freigeben

Here’s the pseudocode for searching and deleting a node from a linked list:

function SearchAndDelete(ListHead, searchItem):
  head = ListHead
  while ListHead.next.value not equals searchItem:
	head = head.next
  deleteNode = head.next
  head.next = head.next.next
  head.next.prev = head
  deleteNode.next, deleteNode.next = NULL
  free memory(deleteNode)
  return ListHead
Such- und Löschvorgang

Such- und Löschvorgang

Durchlaufen Sie eine doppelt verknüpfte Liste von vorne

Vom Kopfknoten aus durchlaufen und über den nächsten Knoten iterieren, bis wir „NULL“ finden. Während wir jeden Knoten durchlaufen, können wir den Wert des Knotens drucken. Hier sind die Schritte zum Queren von vorne (Vorwärtsrichtung):

Schritt 1) Weisen Sie dem aktuellen Hauptknoten einen Zeiger oder eine Variable zu.

Schritt 2) Iterieren Sie zum nächsten Knoten des Kopfes, bis Sie „NULL“ erhalten.

Schritt 3) Drucken Sie die Daten des Knotens in jeder Iteration.

Schritt 4) Geben Sie den Hauptknoten zurück.

Hier ist der Pseudocode zum Durchlaufen einer doppelt verknüpften Liste von vorne:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals to NULL:
	print head.data
	head = head.next
  return ListHead

Hierbei ist die Rückgabe nicht verpflichtend. Es empfiehlt sich jedoch, den Hauptknoten nach den Vorgängen zurückzugeben.

Durchlaufen Sie eine doppelt verknüpfte Liste von hinten

Dieser Vorgang ist die Umkehrung der Traverse von vorne. Der Ansatz ist derselbe, mit einem kleinen Unterschied. Wir müssen zum Endknoten und dann vom Endknoten zum vorderen Knoten durchlaufen.

Hier sind die Schritte zum Durchlaufen einer doppelt verknüpften Liste von hinten:

Schritt 1) Durchqueren Sie, bis wir den Endknoten erreichen.

Schritt 2) Vom Endknoten aus werden wir durchlaufen, bis wir den vorherigen Knoten als „NULL“ erhalten. Der „prev“ (vorheriger Zeiger) ist für den Kopfknoten null

Schritt 3) Bei jeder Iteration drucken wir die Knotendaten.

Hier ist der Pseudocode für die Durchquerung von hinten:

function traverseFromBack(ListHead):
  head = ListHead
  while head not equals NULL:
	head = head.next
  tail = head
  while tail not equal to NULL:
	print tail.value
	tail = tail.prev
  return ListHead

Unterschied zwischen einfach und doppelt verknüpfter Liste

Der Hauptunterschied zwischen der Single- und der Double Linked-Liste besteht in der Anzahl der Links.

Unterschied zwischen einfach und doppelt verknüpfter Liste

Hier ist der Unterschied zwischen den Knoten einer einfach verknüpften Liste und der Knotenstruktur der doppelt verknüpften Liste:

Feld Einfach verknüpfte Liste Doppelt verknüpfte Liste
Struktur Einfach verknüpfte Liste hat ein Datenfeld und einen Link zum nächsten Knoten. Eine doppelt verknüpfte Liste verfügt über ein Datenfeld und zwei Links. Eine für den vorherigen Knoten und eine für den nächsten Knoten.
Traversal Es kann nur von Kopf bis Schwanz wandern. Es kann sowohl vorwärts als auch rückwärts fahren.
Memory Belegt weniger Speicher. Sie belegt mehr Speicher als eine einfach verknüpfte Liste.
Zugänglichkeit Einfach verknüpfte Listen sind weniger effizient, da sie nur einen Link zum nächsten Knoten verwenden. Für den vorherigen Knoten gibt es keinen Link. Doppelt verknüpfte Listen sind effizienter als einfach verknüpfte Listen.

Doppelt verknüpfte Liste in C++

#include<iostream>
using namespace std;
  struct node{
  int data;
  struct node *next;
  struct node *prev;
  };
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead!=NULL)
  {
	listHead->prev = newNode;
  	newNode->next = listHead;
  }
  
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
  }
void insertEnd(node * &listHead, int value){
  if(listHead==NULL)
  {
  	insertFront(listHead,value);
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next!=NULL){
  head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
  }
void insertAfter(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;
  node *head = listHead;	
  while(head->next!=NULL &&  head->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
  }
void insertBefore(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;	
  node *head = listHead;	
  while(head->next!=NULL &&  head->next->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;	
  }
void traverseFromFront(node *listHead){
  node* head = new node();
  head = listHead;
  cout<<"Traversal from head:\t";	
  while(head!=NULL){	
  cout<<head->data<<"\t ";	
  head = head->next;	
  }	
  cout<<endl;
  }	
void traverseFromEnd(node *listHead){
  node* head = new node();
  head = listHead;	
  cout<<"Traversal from head:\t";	
  while(head->next!=NULL){	
  head = head->next;	
  }	
  node *tail = head;	
  while(tail!=NULL){	
  cout<<tail->data<<"\t";	
  tail = tail->prev;	
  }	
  cout<<endl;	
  }
void searchAndDelete(node **listHead, int searchItem){
  node* head = new node();
  head = (*listHead);
  while(head->next!=NULL &&  head->data!=searchItem){
  head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
  	*listHead = head->next;
  }
  if(head->next != NULL){
  	head->next->prev = head->prev;
  }
  
  if(head->prev != NULL){
  	head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
  }
int main(){
  node *head = NULL;
  insertFront(head,5);
  insertFront(head,6);
  insertFront(head,7);
  insertEnd(head,9);
  insertEnd(head,10);
  insertAfter(head,5,11);
  insertBefore(head,5,20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head,7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Output

Added 5 at the front
Added 6 at the front
Added 7 at the front
Aded 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Doppelt verknüpfte Liste in Python

class node:
  def __init__(self,data = None, prev=None, next = None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def insertFront(self, val):
    newNode = node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))

  def insertEnd(self,val):
    newNode = node(data=val)
    if self.head is None:
      self.insertFront(val)
    
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))

  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()

  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from Tail:\t",end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data),end="")
      tail = tail.prev
    print()
  
  def insertAfter(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value,searchItem))

  def insertBefore(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value,searchItem))

  def searchAndDelete(self,searchItem):
    temp = self.head

    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is temp.data:
      self.head = temp.next

    if temp.next is not None:
      temp.next.prev = temp.prev
    
    if temp.prev is not None:
      temp.prev.next = temp.next
    
    print("Deleted Node\t{}".format(searchItem))
    return

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Output

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6

Mitplexität der doppelt verknüpften Liste

Im Allgemeinen ist time complexDie Stadt ist in drei Typen unterteilt.

Sie sind:

  1. I'm besten fall
  2. Durchschnittlicher Fall
  3. Schlimmsten Fall

Team mitplexity im besten Fall für Double Linked List:

  1. Das Einfügen in Kopf oder Schwanz kostet O(1). Weil wir die verknüpfte Liste nicht durchlaufen müssen. Der Kopf- und der Schwanzzeiger können uns mit O(1)-Zeitpunkt Zugriff auf den Kopf- und Schwanzknoten ermöglichenplexkeit.
  2. Das Löschen am Anfang oder am Ende kostet O(1).
  3. Searching a node will have the time complexität von O(1). Weil der Zielknoten der Kopfknoten sein kann.

Team mitplexität im durchschnittlichen Fall für doppelt verknüpfte Listen:

  1. Das Einsetzen am Kopf oder am Schwanz hat die ZeitplexKostenart O(1).
  2. Das Löschen an der Spitze oder am Ende hat die Zeit complexKostenart O(1).
  3. Searching a node will have the time complexität von O(n). Weil sich das Suchelement irgendwo zwischen der verknüpften Liste befinden kann. Hier ist „n“ der Gesamtknoten, der in der verknüpften Liste vorhanden ist.

Der Worst-Case-Zeit-ComplexDie Funktionalität der doppelt verketteten Liste entspricht dem Durchschnittsfall.

Speicher complexität der doppelt verknüpften Liste

Speicher complexity ist O(n), wobei „n“ die Gesamtzahl der Knoten ist. Bei der Implementierung der verknüpften Liste müssen wir den von uns verwendeten Speicher freigeben. Andernfalls kommt es bei einer größeren verknüpften Liste zu Speicherverlusten.

Zusammenfassung

  • Eine verknüpfte Liste ist eine Art lineare Datenstruktur, eine Sammlung von Daten, die linear dargestellt werden.
  • Eine doppelt verknüpfte Liste ist eine Art verknüpfter Liste, bei der ein Knoten Verknüpfungen sowohl zum vorherigen als auch zum nächsten Knoten aufweist.
  • Eine doppelt verknüpfte Liste enthält alle Vorgänge wie das Hinzufügen eines Knotens, das Löschen eines Knotens, das Einfügen eines Knotens nach oder vor einem anderen Knoten und das Durchlaufen der verknüpften Liste von Kopf bis Ende.
  • Eine doppelt verknüpfte Liste verfügt über ein Datenfeld und zwei Links. Eine für den vorherigen Knoten und eine für den nächsten Knoten.
  • Mitplexität der doppelt verknüpften Liste Best Case, Average Case
  • Und im schlimmsten Fall.