Dobbeltkoblet liste: C++, Python (Code Eksempel)

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: ett inneholder dataene, og de to andre er pekere til neste og forrige node. Disse to pekerne hjelper til med å bevege seg fremover eller bakover fra en bestemt node.

Her er den grunnleggende strukturen til den dobbeltlenkede listen.

Strukturen til en dobbeltlenket liste

Hver lenket liste har en hode- og en halenode. Hovednoden har ingen prev (forrige peker) node, og halenoden har ingen neste node.

Her er noen viktige begreper 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 inni den. For eksempel kan strenger, ordbøker, sett, hashmap og andre strukturer lagres i datafeltet.

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

Strukturen til en node i en dobbeltlenket liste

Operasjoner av Doubly Linked List

Operasjonene til en dobbeltlenket liste inkluderer å legge til, slette, sette inn og fjerne noder, samt å gå gjennom listen fra topp til bunn eller bunn til topp.

Her er listen over operasjoner som kan implementeres på en dobbeltlenket liste:

• Innsetting foran
• Innsetting ved 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

Implementeringen og pseudokoden for hver av disse operasjonene følger nedenfor.

Innsetting foran dobbeltlenket liste

Innsetting foran betyr å opprette en node i den lenkede listen og plassere den i begynnelsen av listen.

For eksempel finnes det en gitt node 15Den må legges til som hovednoden.

To viktige betingelser gjelder når du utfører denne operasjonen:

1. Den nye noden blir hovednoden hvis den dobbeltlenkede listen er tom.
2. Hvis det allerede finnes en hodenode, erstattes den forrige hodenoden med 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 i frontnode

Innsetting på slutten av dobbeltlenket liste

Innsetting på slutten betyr å opprette en node i den lenkede listen og plassere den på halen.

To metoder utfører denne operasjonen:

• Metode 1: Begynn å gå fra toppen av den dobbeltlenkede listen til neste blir null. Koble deretter den nye noden til neste pekeren.
• Metode 2: Ta den siste noden i den dobbeltlenkede listen. Deretter, neste Pekeren til den siste noden peker til den nye noden. Den nye noden blir halenoden.

Her er pseudokoden for innsetting ved halenoden:

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

Innsetting på slutten av den koblede listen

Innsetting etter en node

Tenk deg en eksisterende dobbeltlenket liste som den følgende:

Målet er å sette inn en gitt node som skal lenkes etter noden med verdien 12.

Trinn 1) Travers fra hodet til den siste noden. Sjekk hvilken node som har verdien 12.

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

Her er pseudokoden for å sette inn en node etter en node i en dobbeltlenket liste:

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

Innsetting etter en node

Innsetting før en node

Denne operasjonen ligner på innsetting etter en node. En spesifikk nodeverdi søkes etter, deretter opprettes en ny node som settes inn før den søkte noden.

Å sette inn en gitt node 15 før noden 12, Følg disse instruksjonene:

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

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

Trinn 3) Sett inn den nye noden som neste noden til den gjeldende noden.

Her er pseudokoden for å sette inn en node før en node i en dobbeltlenket liste:

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

Sette inn en node før en node

Slett hodet på den dobbeltlenkede listen

Hovednoden i den dobbeltlenkede listen har ingen tidligere node. Så neste pekeren blir den nye hodenoden når den gjeldende hodenoden fjernes. Det er også nødvendig å frigjøre minnet som er opptatt av en slettet node.

Her er trinnene for å slette head-noden:

Trinn 1) Tilordne en variabel til den gjeldende hodenoden.

Trinn 2) Besøk neste noden til gjeldende hovednode og gjør prev pekeren NULL. Dette kobler den andre noden fra den første noden.

Trinn 3) Frigjør minnet som var opptatt av den forrige hovednoden.

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

Sletter hodenoden

Det er nødvendig å frigjøre allokert minne etter enhver sletting. Ellers forblir minnet for den slettede blokken opptatt i hele programmets kjøretid, og ingen andre applikasjoner kan bruke det minnesegmentet.

Slett halen av den dobbeltlenkede listen

Denne operasjonen ligner på sletting av hodet. I stedet for hodet fjernes halen. For å identifisere en node som halen, sjekk om den neste pekeren er null. Etter at halen er slettet, må minnet frigjøres.

Denne operasjonen er også kjent som sletting fra baksiden.

Her er trinnene for å gjøre dette:

Trinn 1) Traverser til halenoden til den dobbeltlenkede listen.

Trinn 2) Tilordne en variabel eller peker til haleknuten.

Trinn 3) Sett neste pekeren til NULL og frigjør minnet til halenoden.

Her er pseudokoden for å slette halenoden:

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

Søk etter og slett en node fra en dobbeltlenket liste

Denne operasjonen søker etter en spesifikk nodeverdi og sletter noden. Et lineært søk er nødvendig fordi den lenkede listen er en lineær datastruktur. Etter sletting må minnet frigjøres.

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

Trinn 1) Gå gjennom den lenkede listen fra toppen til nodeverdien er lik søkeelementet.

Trinn 2) Tilordne en variabel slettnode til den samsvarende noden.

Trinn 3) Koble den forrige noden til slettnode til neste node, og sett neste nodes prev pekeren til den forrige noden.

Trinn 4) Frigjør minnet om slettnode.

Her er pseudokoden for å søke etter og slette en node fra en koblet liste:

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

Søk og slett operasjon

Gå gjennom en dobbeltlenket liste forfra

Traversering fra hovednoden itererer over neste node til NULL blir funnet. Verdien kan skrives ut mens man traverserer hver node. Her er trinnene for traversering i fremoverretning:

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 nodedataene i hver iterasjon.

Trinn 4) Returner hodenoden.

Her er pseudokoden for å krysse en dobbeltlenket liste forfra:

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

Returen er ikke obligatorisk. Det er imidlertid god praksis å returnere hovednoden etter operasjoner.

Gå gjennom en dobbeltlenket liste bakfra

Denne operasjonen er det motsatte av traversen forfra. Fremgangsmåten er den samme med én liten forskjell: nå endenoden først, og gå deretter bakover til hodet ved hjelp av prev pekeren.

Her er trinnene for å gå gjennom en dobbeltlenket liste bakfra:

Trinn 1) Traverser til haleknuten er nådd.

Trinn 2) Fra halenoden, traverser ved hjelp av prev helt til den forrige noden er NULL. prev Pekeren er null for hodenoden.

Trinn 3) Skriv ut nodedataene ved hver iterasjon.

Her er pseudokoden for å gå bakfra:

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

Forskjellen mellom enkelt- og dobbeltlenket liste

Hovedforskjellen mellom en enkeltlenket liste og en dobbeltlenket liste er antall lenker hver node har.

Her er forskjellen mellom nodene i en enkeltlenket liste og en dobbeltlenket liste:

Dobbeltkoblet liste i C++

Nedenfor er en komplett C++ Implementering av en dobbeltlenket liste med innsettings-, slettings-, søke- og traverseringsoperasjoner.

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

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
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

Dobbeltkoblet liste i Python

Nedenfor er en komplett Python implementering av en dobbeltlenket liste ved bruk av klasser for noder og selve listen.

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

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

Tidskompleksitet deles vanligvis inn i tre typer: beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle.

Tidskompleksitet i beste fall for Doubly Linked List:

1. Innsetting ved hodet eller halen koster O(1) fordi det ikke er nødvendig med traversering innenfor den lenkede listen. Hode- og halepekerne gir direkte tilgang til hode- og halenodene.
2. Sletting ved hodet eller halen koster O(1).
3. Det koster O(1) å søke etter en node når målnoden er hovednoden.

Tidskompleksitet i gjennomsnittlig tilfelle for dobbeltlenket liste:

1. Innsetting ved hodet eller halen koster O(1).
2. Sletting ved hodet eller halen koster O(1).
3. Det koster O(n) å søke etter en node, fordi målet kan befinne seg hvor som helst i listen. Her, n er det totale antallet noder.

Den verst tenkelige tidskompleksiteten til den dobbeltlenkede listen er den samme som gjennomsnittstilfellet.

Minnekompleksiteten til dobbeltlenket liste

Minnekompleksiteten er O(n), hvor n er det totale antallet noder. Når den lenkede listen implementeres, må minnet frigjøres. Ellers forårsaker større lenkede lister minnelekkasjer.

Bruksområder for dobbeltlenket liste

Dobbeltlenkede lister driver flere virkelige datastrukturer fordi toveis traversering forenkler mange vanlige operasjoner.

• LRU-hurtigbuffer: Minst nylig brukte cacher bruker en dobbeltlenket liste med et hash-kart for O(1) flytting til front og utkastelse.
• Nettleserhistorikk: Navigering frem og tilbake går i den lenkede listen i begge retninger.
• Angre og gjenta stabler: Redaktører og IDE-er track-dokumentversjoner med forrige og neste pekere.
• Dekk: Double-endede køer pusher og popper fra begge ender i O(1)-tid.
• Musikkspillelister: Forrige og neste track-knappene er avhengige av pekere fremover og bakover.

Spørsmål og svar