Dubbel gekoppelde lijst: C++, Python (Code Voorbeeld)

Wat is een dubbelgelinkte lijst?

In een dubbelgelinkte lijst heeft elk knooppunt links naar zowel het vorige als het volgende knooppunt. Elk knooppunt bestaat uit drie elementen: één element bevat de gegevens, en de andere twee zijn pointers naar respectievelijk het volgende en het vorige knooppunt. Deze twee pointers helpen om vooruit of achteruit te navigeren vanaf een bepaald knooppunt.

Hieronder staat de basisstructuur van een dubbelgelinkte lijst.

Structuur van een dubbel gekoppelde lijst

Elke gekoppelde lijst heeft een hoofd- en een staartknooppunt. Het hoofdknooppunt heeft geen vorige (vorige aanwijzer) knooppunt, en het staartknooppunt heeft geen volgende knooppunt.

Hieronder volgen enkele belangrijke termen voor een dubbel gekoppelde lijst:

• Vorige: Elk knooppunt is gekoppeld aan het vorige knooppunt. Het wordt gebruikt als aanwijzer of link.
• Vervolg: Elk knooppunt is gekoppeld aan het volgende knooppunt. Het wordt gebruikt als aanwijzer of link.
• Datum: Dit wordt gebruikt om gegevens in een knooppunt op te slaan. Gegevens kunnen andere informatie bevatten. Data structuren Binnenin kunnen bijvoorbeeld strings, dictionaries, sets, hashmaps en andere structuren in het data-veld worden opgeslagen.

Hieronder ziet u de basisstructuur van een enkel knooppunt in een dubbelgelinkte lijst:

Structuur van een knooppunt in een dubbel gekoppelde lijst

Operavan de Dubbel Gelinkte Lijst

De bewerkingen van een dubbelgelinkte lijst omvatten het toevoegen, verwijderen, invoegen en weghalen van knooppunten, evenals het doorlopen van de lijst van boven naar beneden of van beneden naar boven.

Hieronder staat een lijst met bewerkingen die op een dubbelgelinkte lijst kunnen worden uitgevoerd:

• Invoeging vooraan
• Invoeging aan het eindknooppunt of de laatste knoop
• Invoeging na een knooppunt
• Invoeging vóór een knooppunt
• Verwijdering van voren
• Verwijdering uit de staart
• Zoek en verwijder een knooppunt
• Beweeg van kop tot staart
• Beweeg staart naar hoofd

De implementatie en pseudocode voor elk van deze bewerkingen vindt u hieronder.

Invoegen vóór een dubbel gekoppelde lijst

Invoegen aan het begin betekent dat je een knooppunt in de gekoppelde lijst aanmaakt en dit aan het begin van de lijst plaatst.

Er is bijvoorbeeld een bepaald knooppunt. 15Het moet als hoofdknooppunt worden toegevoegd.

Bij het uitvoeren van deze handeling gelden twee belangrijke voorwaarden:

1. Het nieuwe knooppunt wordt het hoofdknooppunt als de dubbelgelinkte lijst leeg is.
2. Als er al een hoofdknooppunt is, wordt het vorige hoofdknooppunt vervangen door het nieuwe knooppunt.

Hier volgt de pseudocode voor deze bewerking:

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

Invoeging in voorknoop

Invoegen aan het einde van een dubbel gekoppelde lijst

Invoegen aan het einde betekent dat er een knooppunt in de gekoppelde lijst wordt aangemaakt en aan het einde wordt geplaatst.

Deze bewerking wordt op twee manieren uitgevoerd:

• Methode 1: Begin met het doorlopen van de lijst vanaf het begin van de dubbelgelinkte lijst tot volgende wordt null. Verbind vervolgens het nieuwe knooppunt met de volgende wijzer.
• Methode 2: Neem het laatste knooppunt van de dubbelgelinkte lijst. Vervolgens, de volgende De pointer van het laatste knooppunt wijst naar het nieuwe knooppunt. Het nieuwe knooppunt wordt het staartknooppunt.

Hier volgt de pseudocode voor invoeging bij het eindknooppunt:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Invoeging aan het einde van de gekoppelde lijst

Invoeging na een knooppunt

Neem bijvoorbeeld een bestaande dubbelgelinkte lijst zoals de volgende:

Het doel is om een ​​bepaald knooppunt in te voegen dat na het knooppunt met de waarde wordt gekoppeld. 12.

Stap 1) Doorloop het knooppunt van begin tot eind. Controleer welk knooppunt de waarde bevat. 12.

Stap 2) Maak een nieuw knooppunt aan en wijs dit toe als de volgende aanwijzer van het knooppunt. 12. De volgende Het knooppunt van het nieuwe knooppunt zal 15 zijn.

Hieronder staat de pseudocode voor het invoegen van een knooppunt na een ander knooppunt in een dubbelgelinkte lijst:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Invoeging na een knooppunt

Invoegen vóór een knooppunt

Deze bewerking is vergelijkbaar met het invoegen na een knooppunt. Er wordt gezocht naar een specifieke knooppuntwaarde, waarna een nieuw knooppunt wordt aangemaakt en vóór het gevonden knooppunt wordt ingevoegd.

Om een ​​bepaald knooppunt in te voegen 15 vóór het knooppunt 12, Volg deze stappen:

Stap 1) Doorloop de gekoppelde lijst van het hoofdknooppunt naar het staartknooppunt.

Stap 2) Controleer of de volgende aanwijzer van het huidige knooppunt de waarde heeft. 12.

Stap 3) Voeg het nieuwe knooppunt in als de volgende knooppunt van het huidige knooppunt.

Hieronder staat de pseudocode voor het invoegen van een knooppunt vóór een ander knooppunt in een dubbelgelinkte lijst:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Een knooppunt vóór een knooppunt invoegen

Verwijder het hoofd van de dubbel gekoppelde lijst.

Het hoofdknooppunt in een dubbelgelinkte lijst heeft geen voorgaande knooppunten. Dus de volgende De pointer wordt het nieuwe hoofdknooppunt wanneer het huidige hoofdknooppunt wordt verwijderd. Het vrijmaken van het geheugen dat door een verwijderd knooppunt in beslag werd genomen, is ook vereist.

Hieronder volgen de stappen voor het verwijderen van het hoofdknooppunt:

Stap 1) Wijs een variabele toe aan het huidige hoofdknooppunt.

Stap 2) Bezoek de volgende knooppunt van het huidige hoofdknooppunt en maak de vorige pointer NULL. Dit verbreekt de verbinding tussen het tweede en het eerste knooppunt.

Stap 3) Maak het geheugen vrij dat door het vorige hoofdknooppunt werd gebruikt.

Hier is de pseudocode voor het verwijderen van het eerste element uit een dubbelgelinkte lijst:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Het hoofdknooppunt verwijderen

Het vrijgeven van toegewezen geheugen na een verwijdering is noodzakelijk. Anders blijft het geheugen voor het verwijderde blok gedurende de gehele looptijd van het programma bezet en kan geen enkele andere applicatie dat geheugensegment gebruiken.

Verwijder het uiteinde van de dubbelgekoppelde lijst

Deze bewerking is vergelijkbaar met het verwijderen van de kop. In plaats van de kop wordt de staart verwijderd. Om een ​​knooppunt als staart te identificeren, moet worden gecontroleerd of de pointer naar 'next' null is. Na het verwijderen van de staart moet het geheugen worden vrijgegeven.

Deze operatie staat ook bekend als verwijdering van de achterkant.

Dit zijn de stappen om dit te doen:

Stap 1) Doorloop de dubbelgelinkte lijst tot aan het eindknooppunt.

Stap 2) Wijs een variabele of pointer toe aan het staartknooppunt.

Stap 3) Kies het volgende De pointer moet op NULL worden gezet en het geheugen van het staartknooppunt moet worden vrijgegeven.

Hier is de pseudocode voor het verwijderen van het eindknooppunt:

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

Een knooppunt zoeken en verwijderen uit een dubbelgekoppelde lijst

Deze bewerking zoekt naar een specifieke knoopwaarde en verwijdert die knoop. Een lineaire zoekopdracht is vereist omdat de gekoppelde lijst een lineaire datastructuur is. Na het verwijderen moet het geheugen worden vrijgegeven.

Hieronder volgen de stappen voor het zoeken en verwijderen van een knooppunt in een dubbelgekoppelde lijst:

Stap 1) Doorloop de gekoppelde lijst vanaf het begin tot de waarde van het knooppunt gelijk is aan het zoekitem.

Stap 2) Wijs een variabele toe verwijderKnooppunt naar het overeenkomende knooppunt.

Stap 3) Verbind het vorige knooppunt van de verwijderKnooppunt naar het volgende knooppunt, en stel de volgende knooppunt in vorige verwijzing naar het vorige knooppunt.

Stap 4) Bevrijd de herinnering aan de verwijderKnooppunt.

Hieronder staat de pseudocode voor het zoeken naar en verwijderen van een knooppunt uit een gekoppelde lijst:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Zoek- en verwijderbewerking

Doorloop een dubbelgelinkte lijst van voor naar achter.

Door vanaf het beginpunt te beginnen, wordt het volgende knooppunt doorlopen totdat de waarde NULL wordt gevonden. Tijdens het doorlopen van elk knooppunt kan de waarde worden afgedrukt. Hieronder volgen de stappen voor het doorlopen in de voorwaartse richting:

Stap 1) Wijs een pointer of variabele toe aan het huidige hoofdknooppunt.

Stap 2) Ga door naar het volgende knooppunt van de kop totdat je NULL krijgt.

Stap 3) Print de knooppuntgegevens in elke iteratie.

Stap 4) Retourneer het hoofdknooppunt.

Hier volgt de pseudocode voor het doorlopen van een dubbelgelinkte lijst vanaf de voorkant:

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

Het is niet verplicht om terug te keren naar het hoofdknooppunt. Het is echter wel goede praktijk om na bewerkingen terug te keren naar het hoofdknooppunt.

Een dubbelgelinkte lijst van achter naar voren doorlopen

Deze bewerking is het omgekeerde van de traverse vanaf de voorkant. De aanpak is hetzelfde, met één klein verschil: bereik eerst het eindknooppunt en loop dan achterwaarts terug naar het beginpunt met behulp van de vorige wijzer.

Hieronder volgen de stappen om een ​​dubbelgelinkte lijst van achteren naar voren te doorlopen:

Stap 1) Doorloop de route totdat het eindknooppunt is bereikt.

Stap 2) Ga vanaf het eindknooppunt verder met behulp van vorige totdat het vorige knooppunt NULL is. vorige De pointer is null voor het hoofdknooppunt.

Stap 3) Print bij elke iteratie de knooppuntgegevens.

Hier is de pseudocode voor het doorlopen van de route vanaf de achterkant:

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

Verschil tussen een enkelvoudig en een dubbelvoudig gekoppelde lijst

Het belangrijkste verschil tussen een enkelvoudig gekoppelde lijst en een dubbelvoudig gekoppelde lijst is het aantal koppelingen dat elk knooppunt bevat.

Hieronder ziet u het verschil tussen de knooppunten van een enkelvoudig gekoppelde lijst en een dubbelvoudig gekoppelde lijst:

Dubbel gekoppelde lijst in C++

Hieronder staat een complete C++ Implementatie van een dubbelgelinkte lijst met invoeg-, verwijder-, zoek- en doorloopbewerkingen.

#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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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);
}

uitgang

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
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Dubbel gekoppelde lijst in Python

Hieronder staat een complete Python Implementatie van een dubbelgelinkte lijst met behulp van klassen voor knooppunten en de lijst zelf.

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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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()

uitgang

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

Complexiteit van dubbel gekoppelde lijst

De tijdscomplexiteit wordt over het algemeen onderverdeeld in drie typen: het beste geval, het gemiddelde geval en het slechtste geval.

Tijdcomplexiteit in het beste geval voor een dubbel gekoppelde lijst:

1. Invoegen aan het begin of einde kost O(1) omdat er geen doorloop binnen de gekoppelde lijst nodig is. De pointers naar het begin en einde geven direct toegang tot de respectievelijke knooppunten.
2. Verwijderen aan het begin of einde kost O(1).
3. Het doorzoeken van een knooppunt kost O(1) wanneer het doelknooppunt het hoofdknooppunt is.

Tijdcomplexiteit in het gemiddelde geval voor een dubbel gekoppelde lijst:

1. Invoegen aan het begin of einde kost O(1).
2. Verwijderen aan het begin of einde kost O(1).
3. Het zoeken naar een knooppunt kost O(n), omdat het doel zich overal in de lijst kan bevinden. Hier, n is het totale aantal knooppunten.

De tijdcomplexiteit in het slechtste geval van een dubbelgelinkte lijst is gelijk aan die in het gemiddelde geval.

Geheugencomplexiteit van dubbel gekoppelde lijst

De geheugencomplexiteit is O(n), waarbij n is het totale aantal knooppunten. Bij het implementeren van de gelinkte lijst moet het geheugen worden vrijgemaakt. Anders veroorzaken grotere gelinkte lijsten geheugenlekken.

Toepassingen van dubbelgelinkte lijsten

Dubbelgelinkte lijsten vormen de basis van diverse datastructuren in de praktijk, omdat bidirectionele traversering veel voorkomende bewerkingen vereenvoudigt.

• LRU-cache: Least-Recently-Used caches gebruiken een dubbelgelinkte lijst met een hashmap voor het verplaatsen naar voren en het verwijderen van elementen uit de cache in O(1) tijd.
• Browsergeschiedenis: De navigatieknoppen voor vooruit en achteruit bewegen door de gekoppelde lijst in beide richtingen.
• Ongedaan maken en opnieuw uitvoeren van acties: Editors en IDE's track documentversies met vorige en volgende aanwijzers.
• Deque: Double-ended wachtrijen kunnen aan beide uiteinden in O(1) tijd pushen en poppen.
• Muziek afspeellijsten: Vorige en volgende tracDe k-knoppen maken gebruik van vooruit- en achteruitwijzers.

Veelgestelde vragen