Dobbeltkoblet liste: C++, Python (Kodeeksempel)

Hva er en dobbeltlenket liste?

I en dobbeltlenket liste har hver node lenker til både forrige og neste node. Hver node består av tre elementer: en holder dataene, og to andre er den neste og den forrige nodens pekere. Disse to pekerne hjelper oss å gå fremover eller bakover fra en bestemt node.

Her er den grunnleggende strukturen til den dobbeltkoblede listen.

Hver koblet liste har en hode- og halenode. Head-noden har ingen "prev" (forrige peker) node, og halenoden har ingen "neste" node.

Her er noen viktige termer for en dobbeltlenket liste:

• Prev: Hver node er knyttet til sin forrige node. Den brukes som en peker eller lenke.
• Neste: Hver node er knyttet til sin neste node. Den brukes som en peker eller lenke.
• Dato: Dette brukes til å lagre data i en node. "Data" kan inneholde andre Datastrukturer inne i den. For eksempel kan streng, ordbok, sett, hashmap osv. lagres i "Data".

Her er den grunnleggende strukturen til en enkelt node i den dobbeltkoblede listen:

Operasjoner av Doubly Linked List

Operasjonene til en dobbeltlenket liste inkluderer å legge til og slette noder, sette inn og fjerne noder og krysse den koblede listen fra topp til bunn.

Her er listen over operasjoner vi kan implementere ved å bruke den dobbeltkoblede listen:

• Innsetting foran
• Innsetting i halen eller siste node
• Innsetting etter en node
• Innsetting før en node
• Sletting forfra
• Sletting fra halen
• Søk og slett en node
• Traverser hode til hale
• Traverser hale til hode

Vi vil se implementeringen og pseudokoden for alle operasjonene ovenfor.

Innsetting foran Doubly Linked List

Innsetting foran betyr at vi må opprette en node i den koblede listen og plassere den i begynnelsen av den koblede listen.

For eksempel er det en gitt node "15". Vi må legge dette til hodenoden.

Her er to viktige forhold mens du utfører denne operasjonen:

1. Den nye noden vil være hodenoden hvis det ikke er noen node i dobbeltlenket liste.
2. Hvis det allerede er en hodenode, vil det forrige hodet bli erstattet av den nye noden.

Her er pseudokoden for denne operasjonen:

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

Innsetting på slutten av dobbeltlenket liste

"Innsetting på slutten" betyr at vi oppretter en node i den koblede listen og plasserer den på slutten.

For å utføre dette kan vi bruke to metoder:

• Metode 1: Begynn å krysse fra toppen av den dobbeltlenkede listen til "neste" blir null. Koble deretter den nye noden med "neste".
• Metode 2: Ta den siste noden av dobbeltlenkede listen. Deretter vil den "neste" noden til den siste noden koble til den nye noden. Nå vil den nye noden være halenoden.

Her er pseudokoden for innsetting ved haleknuten:

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

Innsetting etter en node

La oss si at vi har en eksisterende dobbeltlenket liste som følgende:

Vi ønsker å sette inn en gitt node som vil bli koblet etter noden, som har verdien "12".

Her er trinnene for dette:

Trinn 1) Traverser fra hodet til siste node. Sjekk hvilken node som har verdien "12".

Trinn 2) Opprett en ny node og tilordne den som neste peker for node "12". Den "neste" noden til den nye noden vil være 15.

Her er pseudokoden for å sette inn en node etter en node i dobbeltlenket 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

Innsetting før en node

Denne operasjonen ligner mer på "innsetting etter en node". Vi må søke etter en spesifikk nodes verdi for å utføre dette. Deretter vil vi opprette en ny node og sette den inn før den søkte noden.

La oss si at vi ønsker å sette inn en gitt node "15" før noden "12". Så her er trinnene for å gjøre det:

Trinn 1) Gå gjennom den koblede listen fra hodenoden til halenoden.

Trinn 2) Sjekk om den neste pekeren til gjeldende node har verdien "12" eller ikke.

Trinn 3) Sett inn den nye noden som "neste" node for gjeldende node.

Her er pseudokoden for å sette inn en node før en node i dobbel lenket 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

Slett toppen av den dobbeltlenkede listen

Hovednoden i den dobbeltkoblede listen som ikke har noen tidligere node. Så den neste pekeren vil være den nye hodenoden hvis vi ønsker å slette hodenoden. Vi må også frigjøre minnet som er okkupert av en node mens vi sletter en node.

Her er trinnene for å slette hodenoden:

Trinn 1) Tilordne en variabel til den gjeldende hodenoden.

Trinn 2) Besøk "neste" node til gjeldende hodenode og gjør "prev" (forrige peker) node som ''NULL». Dette betyr at vi kobler den andre noden fra den første noden.

Trinn 3) Frigjør det okkuperte minnet ved forrige hodenode.

Her er pseudokoden for å slette hodet fra en dobbeltlenket liste:

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

Det er nødvendig å slette det tildelte minnet etter å ha utført noen form for slettingsoperasjon. Ellers vil minnet for den slettede blokken forbli opptatt under hele programmets kjøretid. Ingen andre applikasjoner kan bruke det minnesegmentet.

Slett halen av den dobbeltlenkede listen.

Denne operasjonen er omtrent det samme som sletting av hodet. Her, i stedet for hodet, må vi slette halen. For å identifisere en node som en halenode, bør vi sjekke om neste peker eller neste node er null eller ikke. Etter å ha slettet halen, må vi frigjøre minnet.

Denne operasjonen er også kjent som "sletting fra baksiden".

Her er trinnene for å gjøre dette:

Trinn 1) Traverser til haleknuten til den dobbeltkoblede listen.

Trinn 2) Tilordne en variabel eller peker til haleknuten.

Trinn 3) Gjør den "neste" noden til NULL og frigjør minnet til halenoden.

Her er pseudokoden for å slette haleknuten:

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

Søk og slett en node fra Double Linked List

Denne operasjonen lar oss søke etter en spesifikk nodedata og slette den noden. Vi må utføre et lineært søk da den koblede listen er en lineær datastruktur. Etter sletting må vi også frigjøre minnet.

Her er trinnene for å søke og slette en node i den dobbeltkoblede listen:

Trinn 1) Gå gjennom den koblede listen fra hodet til nodens verdi er lik søkeelementet.

Trinn 2) Tilordne en variabel "deleteNode" til den matchede noden.

Trinn 3) Tilordne forrige node til "deleteNode" til neste node.

Trinn 4) Frigjør minnet til "deleteNode"

Her er pseudokoden for å søke og slette en node fra en koblet 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

Gå gjennom en dobbeltlenket liste forfra

Å gå fra hodenoden og iterere over neste node til vi finner "NULL". Mens vi krysser hver node, kan vi skrive ut verdien til noden. Her er trinnene for å krysse forfra (forover):

Trinn 1) Tilordne en peker eller variabel til den gjeldende hodenoden.

Trinn 2) Iterer til neste node i hodet til du får "NULL"

Trinn 3) Skriv ut nodens data i hver iterasjon.

Trinn 4) Returner hodenoden.

Her er pseudokoden for å krysse en dobbeltlenket liste fra forsiden:

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

Her er retur ikke obligatorisk. Men det er en god praksis å returnere hodenoden etter operasjonene.

Gå gjennom en dobbeltlenket liste bakfra

Denne operasjonen er invers av traversen fra forsiden. Tilnærmingen er den samme med litt forskjell. Vi må traversere til sluttnoden og deretter traversere fra sluttnoden til frontnoden.

Her er trinnene for å krysse en dobbeltlenket liste fra baksiden:

Trinn 1) Traverser til vi kommer til haleknuten.

Trinn 2) Fra halenoden vil vi krysse til vi får den forrige noden som "NULL". «Prev» (forrige peker) vil være null for hodenoden

Trinn 3) Ved hver iterasjon vil vi skrive ut nodedataene.

Her er pseudokoden for å krysse bakfra:

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

Forskjellen mellom enkelt- og dobbeltlenket liste

Hovedforskjellen mellom Singly og Doubly Linked-listen er antall lenker.

Her er forskjellen mellom nodene til en enkeltlenket liste og nodestrukturen til den dobbeltkoblede listen:

Felt	Enkeltlenket liste	Dobbeltkoblet liste
Structure	Enkeltlenket liste har ett datafelt og en lenke til neste node.	Dobbel lenket liste har ett datafelt og to lenker. En for forrige node og en annen for neste node.
traversering	Den kan bare krysse fra hode til hale.	Den kan gå både forover og bakover.
Minne	Opptar mindre minne.	Den opptar mer minne enn en enkeltlenket liste.
tilgjengelighet	Enkeltkoblede lister er mindre effektive da de bare bruker én lenke til neste node. Det er ingen kobling til forrige node.	Dobbeltkoblede lister er mer effektive enn enkeltlenkede lister.

Dobbeltkoblet liste i 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);
}

Produksjon

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

Dobbeltkoblet liste i 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()

Produksjon

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

Kompleksiteten til dobbeltlenket liste

Generelt er tidskompleksitet delt inn i tre typer.

De er:

1. Beste sak
2. Gjennomsnittlig sak
3. Verste tilfelle

Tidskompleksitet i beste fall for Doubly Linked List:

1. Innsetting i hode eller hale vil koste O(1). Fordi vi ikke trenger å gå gjennom den koblede listen. Hodet og halepekeren kan gi oss tilgang til hode- og halenoden med O(1) tidskompleksitet.
2. Sletting ved hode eller hale vil koste O(1).
3. Å søke i en node vil ha tidskompleksiteten til O(1). Fordi målnoden kan være hodenoden.

Tidskompleksitet i gjennomsnittlig tilfelle for dobbeltlenket liste:

1. Innsetting ved hode eller hale vil ha tidskompleksiteten til kostnad O(1).
2. Sletting ved hode eller hale vil ha tidskompleksiteten til kostnad O(1).
3. Å søke i en node vil ha tidskompleksiteten til O(n). Fordi søkeelementet kan ligge hvor som helst mellom den koblede listen. Her er "n" den totale noden som er tilstede i den koblede listen.

Den verste tidskompleksiteten til den dobbeltkoblede listen vil være den samme som gjennomsnittssaken.

Minnekompleksiteten til dobbeltlenket liste

Minnekompleksitet er O(n), der "n" er det totale antallet noder. Når vi implementerer den koblede listen, må vi frigjøre minnet vi brukte. Ellers, for en større koblet liste, vil det føre til minnelekkasjer.

Sammendrag

• En koblet liste er en slags lineær datastruktur, en samling av data representert på en lineær måte.
• En dobbeltkoblet liste er en type koblet liste der en node har koblinger til både forrige og neste node.
• Dobbeltkoblet liste inneholder alle operasjonene som å legge til en node, slette en node, sette inn en node etter eller før en annen node, og krysse den koblede listen fra topp til hale.
• Dobbel lenket liste har ett datafelt og to lenker. En for forrige node og en annen for neste node.
• Kompleksiteten til dobbelt lenket liste Best Case, Average Case
• Og i verste fall.