Dubbel gekoppelde lijst: C++, Python (codevoorbeeld)

Wat is een dubbel gekoppelde lijst?

In een dubbel gekoppelde lijst heeft elk knooppunt links naar zowel het vorige als het volgende knooppunt. Elk knooppunt bestaat uit drie elementen: één bevat de gegevens en nog eens twee zijn de aanwijzers van het volgende en het vorige knooppunt. Deze twee aanwijzingen helpen ons vooruit of achteruit te gaan vanaf een bepaald knooppunt.

Hier is de basisstructuur van de dubbel gekoppelde lijst.

Structuur van een dubbel gekoppelde lijst
Structuur van een dubbel gekoppelde lijst

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

Hier volgen enkele belangrijke termen voor een dubbel gelinkte 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 bevatten Data structuren in het. Tekenreeks, woordenboek, set, hashmap, enz. Kunnen bijvoorbeeld worden opgeslagen in de "Gegevens".

Hier is de basisstructuur van een enkel knooppunt in de dubbel gekoppelde lijst:

Structuur van een knooppunt in een dubbel gekoppelde lijst

Structuur van een knooppunt in een dubbel gekoppelde lijst

Bewerkingen van dubbel gekoppelde lijst

De bewerkingen van een dubbel gekoppelde lijst omvatten het toevoegen en verwijderen van knooppunten, het invoegen en verwijderen van knooppunten, en het doorlopen van de gekoppelde lijst van boven naar beneden.

Hier is de lijst met bewerkingen die we kunnen implementeren met behulp van de dubbel gekoppelde lijst:

  • Invoeging vooraan
  • Inbrengen in de staart of 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

We zullen de implementatie en pseudocode voor alle bovenstaande bewerkingen zien.

Invoeging vóór dubbel gekoppelde lijst

Invoeging vooraan betekent dat we een knooppunt in de gekoppelde lijst moeten maken en dit aan het begin van de gekoppelde lijst moeten plaatsen.

Er is bijvoorbeeld een bepaald knooppunt “15”. We moeten dit toevoegen aan het hoofdknooppunt.

Hier zijn twee belangrijke voorwaarden tijdens het uitvoeren van deze bewerking:

  1. Het nieuwe knooppunt zal het hoofdknooppunt zijn als er geen knooppunt in de dubbel gekoppelde lijst staat.
  2. Als er al een hoofdknooppunt is, wordt het vorige hoofd vervangen door het nieuwe knooppunt.

Hier is 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 het voorknooppunt
Invoeging in voorknoop

Invoeging aan het einde van de dubbel gekoppelde lijst

“Invoeging aan het einde” betekent dat we een knooppunt in de gekoppelde lijst zullen maken en dit aan het einde zullen plaatsen.

Om dit uit te voeren, kunnen we twee methoden gebruiken:

  • Methode 1: Begin vanaf het begin van de dubbel gekoppelde lijst totdat de “volgende” nul wordt. Koppel vervolgens het nieuwe knooppunt met de “volgende”.
  • Methode 2: Neem het laatste knooppunt van de dubbelgekoppelde lijst. Vervolgens zal het “volgende” knooppunt van het laatste knooppunt linken naar het nieuwe knooppunt. Het nieuwe knooppunt zal nu het staartknooppunt zijn.

Hier is de pseudocode voor invoeging bij het staartknooppunt:

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
Invoeging aan het einde van de gekoppelde lijst

Invoeging aan het einde van de gekoppelde lijst

Invoeging na een knooppunt

Laten we zeggen dat we een bestaande, dubbel gekoppelde lijst hebben, zoals de volgendewing:

Invoeging na een knooppunt

We willen een bepaald knooppunt invoegen dat wordt gekoppeld na het knooppunt, dat de waarde "12" heeft.

Hier zijn de stappen hiervoor:

Stap 1) Ga van het hoofd naar het laatste knooppunt. Controleer welk knooppunt de waarde “12” heeft.

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

Hier is de pseudocode voor het invoegen van een knooppunt na een knooppunt in een dubbel gekoppelde lijst:

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
Invoeging na een knooppunt

Invoeging na een knooppunt

Invoeging vóór een knooppunt

Deze handeling lijkt meer op het “inbrengen na een knooppunt”. Om dit uit te voeren, moeten we zoeken naar de waarde van een specifiek knooppunt. Vervolgens zullen we een nieuw knooppunt maken en dit vóór het gezochte knooppunt invoegen.

Laten we zeggen dat we een bepaald knooppunt “15” vóór het knooppunt “12” willen invoegen. Dan zijn hier de stappen om dit te doen:

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

Stap 2) Controleer of de volgende pointer van het huidige knooppunt de waarde “12” heeft of niet.

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

Hier is de pseudocode voor het invoegen van een knooppunt vóór een knooppunt in een dubbel gekoppelde lijst:

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
Een knooppunt vóór een knooppunt invoegen

Een knooppunt vóór een knooppunt invoegen

Verwijder de kop van de dubbel gekoppelde lijst

Het hoofdknooppunt in de dubbel gekoppelde lijst dat geen vorig knooppunt heeft. De volgende aanwijzer is dus het nieuwe hoofdknooppunt als we het hoofdknooppunt willen verwijderen. We moeten ook het geheugen vrijmaken dat door een knooppunt wordt ingenomen terwijl we een knooppunt verwijderen.

Hier volgen de stappen voor het verwijderen van het hoofdknooppunt:

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

Stap 2) Bezoek het “volgende” knooppunt van het huidige hoofdknooppunt en maak het “vorige” (vorige pointer) knooppunt als ''NULL''. Dit betekent dat we het tweede knooppunt loskoppelen van het eerste knooppunt.

Stap 3) Maak het bezette geheugen vrij door het vorige hoofdknooppunt.

Hier is de pseudocode voor het verwijderen van het hoofd uit een dubbel gekoppelde lijst:

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

Het hoofdknooppunt verwijderen

Het is noodzakelijk om het toegewezen geheugen te verwijderen na het uitvoeren van een wisbewerking. Anderwise, gedurende de gehele looptijd van het programma blijft het geheugen voor het verwijderde blok bezet. Geen enkele andere toepassing kan dat geheugensegment gebruiken.

Verwijder de staart van de dubbel gelinkte lijst.

Deze operatie is ongeveer hetzelfde als het verwijderen van het hoofd. Hier moeten we in plaats van het hoofd de staart verwijderen. Om een ​​knooppunt als staartknooppunt te identificeren, moeten we controleren of de volgende pointer of het volgende knooppunt nul is of niet. Nadat we de staart hebben verwijderd, moeten we het geheugen vrijmaken.

Deze handeling wordt ook wel het “verwijderen vanaf de achterkant” genoemd.

Hier zijn de stappen om dit te doen:

Stap 1) Beweeg tot aan het staartknooppunt van de dubbel gekoppelde lijst.

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

Stap 3) Maak het “volgende” knooppunt als NULL en maak het geheugen van het staartknooppunt vrij.

Hier is de pseudocode voor het verwijderen van het staartknooppunt:

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

Verwijder de staart van de dubbel verbondenen

Zoek en verwijder een knooppunt uit de dubbel gekoppelde lijst

Met deze bewerking kunnen we naar specifieke knooppuntgegevens zoeken en dat knooppunt verwijderen. We moeten een lineaire zoekopdracht uitvoeren, omdat de gekoppelde lijst een lineaire gegevensstructuur is. Na het verwijderen moeten we ook het geheugen vrijmaken.

Hier zijn de stappen voor searching en het verwijderen van een knooppunt in de dubbel gekoppelde lijst:

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

Stap 2) Wijs een variabele “deleteNode” toe aan het overeenkomende knooppunt.

Stap 3) Wijs het vorige knooppunt van de “deleteNode” toe aan het volgende knooppunt.

Stap 4) Maak het geheugen van de “deleteNode” vrij

Hier is de pseudocode voor searching en het verwijderen van een knooppunt uit een gekoppelde lijst:

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
Zoek- en verwijderbewerking

Zoek- en verwijderbewerking

Doorloop een dubbel gekoppelde lijst van voren

Om vanaf het hoofdknooppunt te doorlopen en over het volgende knooppunt te itereren totdat we "NULL" vinden. Terwijl we elk knooppunt doorlopen, kunnen we de waarde van het knooppunt afdrukken. Hier zijn de stappen voor het passeren vanaf de voorkant (voorwaartse richting):

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

Stap 2) Herhaal naar het volgende knooppunt van het hoofd totdat u “NULL” krijgt

Stap 3) Druk de gegevens van het knooppunt in elke iteratie af.

Stap 4) Retourneer het hoofdknooppunt.

Hier is de pseudocode voor het doorkruisen van een dubbel gekoppelde lijst vanaf de voorkant:

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

Hier is retourneren niet verplicht. Maar het is een goede gewoonte om het hoofdknooppunt na de bewerkingen terug te sturen.

Doorloop een dubbel gekoppelde lijst van achteren naar achteren

Deze bewerking is het omgekeerde van de verplaatsing vanaf de voorkant. De aanpak is hetzelfde, met een klein verschil. We moeten naar het eindknooppunt gaan en dan van het eindknooppunt naar het voorste knooppunt.

Hier volgen de stappen voor het doorlopen van een dubbel gekoppelde lijst vanaf de achterkant:

Stap 1) Loop door totdat we het staartknooppunt bereiken.

Stap 2) Vanaf het staartknooppunt zullen we doorlopen totdat we het vorige knooppunt als "NULL" krijgen. De “vorige” (vorige aanwijzer) is nul voor het hoofdknooppunt

Stap 3) Bij elke iteratie zullen we de knooppuntgegevens afdrukken.

Hier is de pseudocode voor het doorlopen vanaf de achterkant:

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

Verschil tussen enkelvoudig en dubbel gekoppelde lijst

Het belangrijkste verschil tussen Singly en de Doubly Linked-lijst is het aantal links.

Verschil tussen enkelvoudig en dubbel gekoppelde lijst

Hier ziet u het verschil tussen de knooppunten van een Singly Linked-lijst en de knooppuntstructuur van de Dubbel Gelinkte Lijst:

Veld Afzonderlijk gekoppelde lijst Dubbel gelinkte lijst
Structuur Afzonderlijk gekoppelde lijst heeft één gegevensveld en één link naar het volgende knooppunt. Dubbel gekoppelde lijst heeft één gegevensveld en twee koppelingen. Eén voor het vorige knooppunt en één voor het volgende knooppunt.
traversal Het kan alleen van kop tot staart bewegen. Het kan zowel voorwaarts als achterwaarts bewegen.
Geheugen Neemt minder geheugen in beslag. Het neemt meer geheugen in beslag dan een afzonderlijk gekoppelde lijst.
Toegankelijkheid Enkelvoudig gekoppelde lijsten zijn minder efficiënt omdat ze slechts één link naar het volgende knooppunt gebruiken. Er is geen link voor het vorige knooppunt. Dubbel gelinkte lijsten zijn efficiënter dan de enkelvoudig gelinkte lijsten.

Dubbel gekoppelde lijst 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);
}

uitgang

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

Dubbel gekoppelde lijst 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()

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

complexvan de dubbel gekoppelde lijst

Over het algemeen is tijd complexheid is verdeeld in drie typen.

Dat zijn:

  1. Beste geval
  2. Gemiddeld geval
  3. Het slechtste geval

Tijd complexin het beste geval voor dubbel gelinkte lijst:

  1. Inbrengen in kop of staart kost O(1). Omdat we niet binnen de gekoppelde lijst hoeven te bladeren. De kop- en staartwijzer kunnen ons toegang geven tot het hoofd- en staartknooppunt met O(1) time complexheid.
  2. Verwijdering aan de kop of staart kost O(1).
  3. SearchiAls een knooppunt de tijd heeft complexiteit van O(1). Omdat het doelknooppunt het hoofdknooppunt kan zijn.

Tijd complexin het gemiddelde geval voor Dubbel Gelinkte Lijst:

  1. Het inbrengen aan de kop of staart zal de tijd hebben complexkostengraad O(1).
  2. Verwijdering aan de kop of staart heeft de tijd complexkostengraad O(1).
  3. SearchiAls een knooppunt de tijd heeft complexiteit van O(n). Omdat het zoekitem zich overal tussen de gekoppelde lijst kan bevinden. Hier is “n” het totale knooppunt dat aanwezig is in de gekoppelde lijst.

De slechtste tijd complexDe kwaliteit van de dubbel gekoppelde lijst zal hetzelfde zijn als in het gemiddelde geval.

Geheugen complexvan de dubbel gekoppelde lijst

Geheugen complexity is O(n), waarbij “n” het totale aantal knooppunten is. Tijdens het implementeren van de gekoppelde lijst moeten we het geheugen vrijmaken dat we hebben gebruikt. Anderwise, voor een grotere gekoppelde lijst zal dit geheugenlekken veroorzaken.

Samengevat

  • Een gekoppelde lijst is een soort lineaire datastructuur, een verzameling gegevens die op een lineaire manier wordt weergegeven.
  • Een dubbel gekoppelde lijst is een soort gekoppelde lijst waarbij een knooppunt links heeft met zowel het vorige als het volgende knooppunt.
  • Dubbel gekoppelde lijst bevat alle bewerkingen zoals het toevoegen van een knooppunt, het verwijderen van een knooppunt, het invoegen van een knooppunt na of vóór een ander knooppunt en het doorlopen van de gekoppelde lijst van kop tot staart.
  • Dubbel gekoppelde lijst heeft één gegevensveld en twee koppelingen. Eén voor het vorige knooppunt en één voor het volgende knooppunt.
  • complexheid van dubbel gekoppelde lijst Beste case, gemiddelde case
  • En in het slechtste geval.