Dobbelt linket liste: C++, Python (Code Eksempel)

Hvad er en dobbeltlinket liste?

I en dobbelt linket liste har hver node links til både den forrige og den næste node. Hver node består af tre elementer: det ene indeholder dataene, og de to andre er pointere til den næste og den forrige node. Disse to pointere hjælper med at bevæge sig fremad eller tilbage fra en bestemt node.

Her er den grundlæggende struktur af den dobbeltlænkede liste.

Strukturen af ​​en dobbeltforbundet liste

Enhver linket liste har en hoved- og en halenode. Hovednoden har ingen prev (forrige pointer) node, og haleknuden har ingen næste node.

Her er nogle vigtige termer for en dobbeltlinket liste:

• forrige: Hver node er knyttet til dens tidligere node. Det bruges som en pointer eller et link.
• Næste: Hver node er knyttet til dens næste node. Det bruges som en pointer eller et link.
• dato: Dette bruges til at gemme data i en node. Data kan indeholde andre Datastrukturer indeni. For eksempel kan strenge, ordbøger, sæt, hashmaps og andre strukturer gemmes i datafeltet.

Her er den grundlæggende struktur for en enkelt node i den dobbeltlinkede liste:

Struktur af en node i en dobbeltforbundet liste

Operationer af dobbeltforbundet liste

Funktionerne i en dobbeltlænket liste omfatter tilføjelse, sletning, indsættelse og fjernelse af noder, samt at gennemløbe listen fra top til bund eller bund til top.

Her er listen over operationer, der kan implementeres på en dobbeltlinket liste:

• Indsættelse foran
• Indsættelse ved halen eller sidste knude
• Indsættelse efter en node
• Indsættelse før en node
• Sletning forfra
• Sletning fra halen
• Søg og slet en node
• Kør hoved til hale
• Kør hale til hoved

Implementeringen og pseudokoden for hver af disse operationer følger nedenfor.

Indsættelse foran dobbeltlænket liste

Indsættelse foran betyder at oprette en node i den sammenkædede liste og placere den i begyndelsen af ​​listen.

For eksempel er der en given node 15Den skal tilføjes som hovednoden.

To vigtige betingelser gælder, når denne operation udføres:

1. Den nye node bliver hovednoden, hvis den dobbeltlænkede liste er tom.
2. Hvis der allerede er en hovednode, erstattes den forrige hovednode af den nye node.

Her er pseudokoden for denne operation:

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

Indsættelse i frontnode

Indsættelse i slutningen af ​​dobbeltlænket liste

Indsættelse til sidst betyder at oprette en node i den linkede liste og placere den i halen.

To metoder udfører denne operation:

• Metode 1: Start med at gå fra toppen af ​​den dobbeltlænkede liste indtil næste bliver null. Forbind derefter den nye node med næste markør.
• Metode 2: Tag den sidste node i den dobbeltlænkede liste. Derefter næste Den sidste nodes markør peger på den nye node. Den nye node bliver halenoden.

Her er pseudokoden til indsættelse ved haleknoden:

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

Indsættelse i slutningen af ​​den linkede liste

Indsættelse efter en node

Overvej en eksisterende dobbeltlinket liste som den følgende:

Målet er at indsætte en given node, der vil blive linket efter noden med værdien 12.

Trin 1) Gå fra hovedet til den sidste node. Kontroller hvilken node der har værdien 12.

Trin 2) Opret en ny node og tildel den som den næste pointer for noden 12. Det næste Noden på den nye node vil være 15.

Her er pseudokoden til at indsætte en node efter en node i en dobbelt linket 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

Indsættelse efter en node

Indsættelse før en node

Denne handling ligner indsættelse efter en node. Der søges efter en specifik nodeværdi, hvorefter en ny node oprettes og indsættes før den søgte node.

Sådan indsætter du en given node 15 før noden 12, følg disse trin:

Trin 1) Gå gennem den sammenkædede liste fra hovedknuden til haleknuden.

Trin 2) Kontroller om den næste pointer for den aktuelle node har værdien 12.

Trin 3) Indsæt den nye node som næste node for den aktuelle node.

Her er pseudokoden til at indsætte en node før en node i en dobbelt linket 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

Indsættelse af en node før en node

Slet hovedet på den dobbelttilknyttede liste

Hovednoden i den dobbeltlinkede liste har ingen tidligere node. Så næste pointeren bliver den nye hovednode, når den nuværende hovednode fjernes. Det er også nødvendigt at frigøre den hukommelse, der er optaget af en slettet node.

Her er trinnene til at slette hovednoden:

Trin 1) Tildel en variabel til den aktuelle hovedknude.

Trin 2) Besøg næste node for den aktuelle hovednode og lav prev pointer NULL. Dette afbryder den anden node fra den første node.

Trin 3) Frigør den hukommelse, der var optaget af den forrige hovednode.

Her er pseudokoden til at slette head-et fra en dobbeltlinket liste:

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

Sletter hovedknudepunktet

Det er nødvendigt at frigøre allokeret hukommelse efter enhver sletning. Ellers forbliver hukommelsen til den slettede blok optaget i hele programmets kørselstid, og ingen andre applikationer kan bruge det pågældende hukommelsessegment.

Slet halen af ​​den dobbelttilknyttede liste

Denne operation ligner sletning af hovedet. I stedet for hovedet fjernes halen. For at identificere en node som halen skal du kontrollere, om den næste pointer er nul. Efter sletning af halen skal hukommelsen frigøres.

Denne operation er også kendt som sletning fra bagsiden.

Her er trinnene til at gøre dette:

Trin 1) Gå gennem indtil haleknuden på den dobbeltlænkede liste.

Trin 2) Tildel en variabel eller pointer til haleknuden.

Trin 3) Indstil næste pointer til NULL og frigør hukommelsen i haleknuden.

Her er pseudokoden til sletning af 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øg og slet en node fra en dobbeltlinket liste

Denne handling søger efter en specifik nodeværdi og sletter den node. En lineær søgning er påkrævet, fordi den sammenkædede liste er en lineær datastruktur. Efter sletning skal hukommelsen frigøres.

Her er trinnene til at søge efter og slette en node i den dobbelttilknyttede liste:

Trin 1) Gennemgå den sammenkædede liste fra overskriften, indtil nodeværdien er lig med søgeelementet.

Trin 2) Tildel en variabel sletNode til den matchende node.

Trin 3) Forbind den forrige node af sletNode til dens næste node, og indstil den næste nodes prev peger til den forrige node.

Trin 4) Befri hukommelsen om sletNode.

Her er pseudokoden til at søge efter og slette en node fra en linket 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øg og slet handling

Gennemgå en dobbeltlænket liste fremad

Gennemgang fra hovednoden itererer over den næste node, indtil NULL findes. Mens man gennemløber hver node, kan værdien udskrives. Her er trinnene for gennemgang i fremadgående retning:

Trin 1) Tildel en pointer eller variabel til den aktuelle hovedknude.

Trin 2) Iterer til den næste node i headet, indtil NULL opnås.

Trin 3) Udskriv nodedataene i hver iteration.

Trin 4) Returner hovedknuden.

Her er pseudokoden til at gennemløbe en dobbelt linket liste forfra:

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

Returneringen er ikke obligatorisk. Det er dog god praksis at returnere hovednoden efter operationer.

Gennemgå en dobbeltlænket liste bagfra

Denne operation er den omvendte af traversen forfra. Fremgangsmåden er den samme med én lille forskel: nå først slutknuden, og gå derefter baglæns til hovedet ved hjælp af prev markør.

Her er trinnene til at gennemgå en dobbelt linket liste bagfra:

Trin 1) Bevæg dig indtil haleknuden er nået.

Trin 2) Fra haleknuden, kryds ved hjælp af prev indtil den forrige node er NULL. prev Pointeren er null for hovednoden.

Trin 3) Udskriv nodedataene ved hver iteration.

Her er pseudokoden for at gå tilbage fra bagsiden:

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

Forskellen mellem enkelt- og dobbeltlinket liste

Den væsentligste forskel mellem en enkeltlænket liste og en dobbeltlænket liste er antallet af links, som hver node indeholder.

Her er forskellen mellem noderne i en enkeltlænket liste og en dobbeltlænket liste:

Dobbeltforbundet liste i C++

Nedenfor er en komplet C++ Implementering af en dobbelt linket liste med indsættelses-, sletnings-, søge- og gennemløbsoperationer.

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

Produktion

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

Dobbeltforbundet liste i Python

Nedenfor er en komplet Python Implementering af en dobbelt linket liste ved hjælp af 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()

Produktion

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 af ​​dobbeltforbundet liste

Tidskompleksitet opdeles generelt i tre typer: bedste tilfælde, gennemsnitligt tilfælde og værst tænkeligt tilfælde.

Tidskompleksitet i bedste tilfælde for dobbeltforbundet liste:

1. Indsættelse ved hoved- eller halepunktet koster O(1), fordi der ikke er behov for gennemgang inden for den linkede liste. Hoved- og halepointerne giver direkte adgang til hoved- og halenoderne.
2. Sletning ved spidsen eller halen koster O(1).
3. Det koster O(1) at søge efter en node, når målnoden er hovednoden.

Tidskompleksitet i det gennemsnitlige tilfælde for dobbeltforbundet liste:

1. Indsættelse ved hovedet eller halen koster O(1).
2. Sletning ved spidsen eller halen koster O(1).
3. Det koster O(n) at søge efter en node, fordi målet kan være hvor som helst på listen. Her, n er det samlede antal noder.

Den værst tænkelige tidskompleksitet for den dobbeltlænkede liste er den samme som i gennemsnitstilfældet.

Hukommelseskompleksitet af dobbeltforbundet liste

Hukommelseskompleksiteten er O(n), hvor n er det samlede antal noder. Under implementeringen af ​​den linkede liste skal hukommelsen frigøres. Ellers forårsager større linkede lister hukommelseslækager.

Anvendelser af dobbelttilknyttede lister

Dobbelt linkede lister driver adskillige virkelige datastrukturer, fordi tovejs traversal forenkler mange almindelige operationer.

• LRU-cache: Mindst nyligt brugte cacher bruger en dobbelt linket liste med et hash-kort til O(1) flytning til forsiden og udsættelse.
• Browserhistorik: Navigation frem og tilbage fører den linkede liste i begge retninger.
• Fortryd og gentag stakke: Redaktører og IDE'er track dokumentversioner med forrige og næste pointers.
• Deque: Double-afsluttede køer skubber og popper fra begge ender i O(1) tid.
• Musikafspilningslister: Forrige og næste track-knapper er afhængige af fremad- og bagudpegere.

Ofte Stillede Spørgsmål