Doppelt verkettete 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.

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:

Operationen der doppelt verknüpften Liste

Zu den Operationen einer doppelt verketteten Liste gehören das Hinzufügen und Löschen von Knoten, das Einfügen und Entfernen von Knoten sowie das Durchlaufen der verketteten Liste von oben nach unten.

Hier ist die Liste der Operationen, die wir mit der doppelt verketteten 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 uns die Implementierung und den Pseudocode für alle oben genannten Operationen ansehen.

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.

Für diesen Vorgang sind zwei wichtige Bedingungen zu beachten:

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 diese Operation:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead

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:

• Methode 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“.
• Methode 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 nach einem Knoten

Nehmen wir an, wir haben eine vorhandene doppelt verkettete Liste wie die folgende:

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ügung vor einem Knoten

Dieser Vorgang ä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

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

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

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

Dieser Vorgang ist ähnlich wie das Löschen des Kopfes. Hier müssen wir anstelle des Kopfes das Ende löschen. Um einen Knoten als Endeknoten zu identifizieren, sollten wir prüfen, ob der nächste Zeiger oder der nächste Knoten null ist oder nicht. Nachdem wir das Ende gelöscht haben, müssen wir den Speicher freigeben.

Dieser Vorgang wird auch als „Löschung von der Rückseite“ 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

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

Mit diesem Vorgang 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.

Hier sind die Schritte zum Suchen und Löschen eines Knotens in der doppelt verknüpften Liste:

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

Hier ist der Pseudocode zum Suchen und Löschen eines Knotens aus einer verknüpften Liste:

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

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

Hier ist die Rückgabe nicht zwingend erforderlich. Es empfiehlt sich jedoch, den Kopfknoten nach den Vorgängen zurückzugeben.

Durchlaufen Sie eine doppelt verknüpfte Liste von hinten

Dieser Vorgang ist das Gegenteil der Traverse von vorne. Der Ansatz ist der gleiche, mit einem kleinen Unterschied. Wir müssen zum Endknoten und dann vom Endknoten zum vorderen Knoten traversieren.

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.

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

Ausgang

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 verkettete 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()

Ausgang

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

Komplexität einer doppelt verketteten Liste

Im Allgemeinen wird die Zeitkomplexität in drei Typen unterteilt.

Sie sind:

1. besten Case
2. Durchschnittlicher Fall
3. Schlimmsten Fall

Zeitliche Komplexität im besten Fall für doppelt verkettete Listen:

1. Das Einfügen in Kopf oder Ende kostet O(1). Weil wir die verknüpfte Liste nicht durchlaufen müssen. Der Kopf- und der Endzeiger können uns mit einer Zeitkomplexität von O(1) Zugriff auf den Kopf- und Endknoten geben.
2. Das Löschen am Anfang oder am Ende kostet O(1).
3. Die Suche nach einem Knoten hat eine Zeitkomplexität von O(1), da der Zielknoten der Kopfknoten sein kann.

Zeitliche Komplexität im Durchschnittsfall für doppelt verkettete Listen:

1. Das Einfügen am Anfang oder Ende hat eine Zeitkomplexität von O(1).
2. Das Löschen am Anfang oder Ende hat eine Zeitkomplexität von O(1).
3. Die Suche nach einem Knoten hat eine Zeitkomplexität von O(n). Denn das Suchelement kann sich an beliebiger Stelle in der verknüpften Liste befinden. Dabei ist „n“ die Gesamtzahl der in der verknüpften Liste vorhandenen Knoten.

Die Zeitkomplexität der doppelt verketteten Liste im schlimmsten Fall ist die gleiche wie im Durchschnittsfall.

Speicherkomplexität einer doppelt verknüpften Liste

Die Speicherkomplexität beträgt O(n), wobei „n“ die Gesamtzahl der Knoten ist. Während 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 verkettete Liste enthält alle Operationen 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 verketteten Liste von Anfang 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.
• Komplexität einer doppelt verketteten Liste, bester Fall, durchschnittlicher Fall
• Und im schlimmsten Fall.