Dobbelt linket liste: C++, Python (Kodeeksempel)
Sarah Chen
Hvad er en dobbeltlinket liste?
I en dobbelt linket liste har hver node links til både den forrige og næste node. Hver node består af tre elementer: en indeholder dataene, og to andre er den næste og den forrige nodes pointere. Disse to pointere hjælper os med at gå frem eller tilbage fra en bestemt knude.
Her er den grundlæggende struktur for den dobbeltforbundne liste.
Hver linket liste har en hoved- og halenode. Hovedknuden har ingen "prev" (forrige pointer)-knude, og haleknuden har ingen "næste" knude.
Her er nogle vigtige udtryk 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 inde i den. For eksempel kan streng, ordbog, sæt, hashmap osv. gemmes i "Data".
Her er den grundlæggende struktur for en enkelt node i den dobbeltforbundne liste:
Operationer af dobbeltforbundet liste
Operationerne af en dobbelt-linket liste omfatter tilføjelse og sletning af noder, indsættelse og fjernelse af noder og gennemgang af den linkede liste fra top til bund.
Her er listen over operationer, vi kan implementere ved hjælp af den dobbelt-linkede liste:
- Indsættelse foran
- Indsættelse i 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
Vi vil se implementeringen og pseudokoden for alle operationerne ovenfor.
Indsættelse foran Doubly Linked List
Indsættelse foran betyder, at vi skal oprette en node i den linkede liste og placere den i begyndelsen af den linkede liste.
For eksempel er der en given node "15". Vi skal tilføje dette til hovedknuden.
Her er to vigtige forhold, mens du udfører denne operation:
- Den nye knude vil være hovedknuden, hvis der ikke er nogen knude på listen med dobbelt lænke.
- Hvis der allerede er en hovedknude, vil det tidligere hoved blive erstattet af den nye knude.
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 slutningen af dobbeltforbundet liste
"Indsættelse i slutningen" betyder, at vi opretter en node i den linkede liste og placerer den i slutningen.
For at udføre dette kan vi bruge to metoder:
- Metode 1: Begynd at krydse fra hovedet af den dobbeltforbundne liste, indtil "næste" bliver nul. Forbind derefter den nye node med den "næste".
- Metode 2: Tag den sidste knude på listen med dobbelt kæder. Derefter vil den "næste" node i den sidste node linke til den nye node. Nu vil den nye knude være haleknuden.
Her er pseudokoden til indsættelse ved haleknuden:
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
Indsættelse efter en node
Lad os sige, at vi har en eksisterende dobbeltlinket liste som følgende:
Vi ønsker at indsætte en given node, der vil blive linket efter noden, som har værdien "12".
Her er trinene til dette:
Trin 1) Gå fra hovedet til den sidste knude. Tjek hvilken node der har værdien "12".
Trin 2) Opret en ny node og tildel den som den næste pointer for node "12". Den "næste" node i den nye node vil være 15.
Her er pseudo-koden til at indsætte en node efter en node i dobbelt linket 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
Indsættelse før en node
Denne operation ligner mere "indsættelsen efter en node". Vi skal søge efter en specifik nodes værdi for at udføre dette. Så vil vi oprette en ny node og indsætte den før den søgte node.
Lad os sige, at vi ønsker at indsætte en given node "15" før noden "12". Så her er trinene til at gøre det:
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" eller ej.
Trin 3) Indsæt den nye node som den "næste" node for den aktuelle node.
Her er pseudokoden til at indsætte en node før en node i dobbelt linket 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
Slet hovedet på den dobbeltforbundne liste
Hovedknuden i den dobbeltforbundne liste, der ikke har nogen tidligere knude. Så den næste pointer vil være den nye hovedknude, hvis vi ønsker at slette hovedknuden. Vi skal også frigøre hukommelsen optaget af en node, mens vi sletter en node.
Her er trinene til at slette hovednoden:
Trin 1) Tildel en variabel til den aktuelle hovedknude.
Trin 2) Besøg den "næste" knude på den aktuelle hovedknude, og gør "forrige" (forrige markør) node som ''NULL'. Det betyder, at vi afbryder den anden node fra den første node.
Trin 3) Frigør den optagede hukommelse af den forrige hovedknude.
Her er pseudokoden til at slette hovedet fra en dobbelt linket liste:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
Det er nødvendigt at slette den tildelte hukommelse efter at have udført enhver form for sletning. Ellers vil hukommelsen for den slettede blok forblive optaget under hele programmets køretid. Ingen anden applikation kan bruge det hukommelsessegment.
Slet halen af den dobbeltforbundne liste.
Denne operation er lidt det samme som sletningen af hovedet. Her skal vi i stedet for hovedet slette halen. For at identificere en node som en haleknude, bør vi kontrollere, om den næste pointer eller næste node er nul eller ej. Efter at have slettet halen, skal vi frigøre hukommelsen.
Denne operation er også kendt som "sletningen bagfra".
Her er trinene til at gøre dette:
Trin 1) Kør indtil haleknuden på den dobbeltforbundne liste.
Trin 2) Tildel en variabel eller pointer til haleknuden.
Trin 3) Gør den "næste" node til NULL og frigør hukommelsen til haleknuden.
Her er pseudokoden til sletning af haleknuden:
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øg og slet en node fra listen med dobbelt lænke
Denne operation giver os mulighed for at søge efter en specifik nodedata og slette den node. Vi skal udføre en lineær søgning, da den linkede liste er en lineær datastruktur. Efter sletning skal vi også frigøre hukommelsen.
Her er trinene til at søge og slette en node på listen med dobbelt link:
Trin 1) Gå gennem den linkede liste fra hovedet, indtil nodens værdi er lig med søgeelementet.
Trin 2) Tildel en variabel "deleteNode" til den matchede node.
Trin 3) Tildel den forrige node af "deleteNode" til den næste node.
Trin 4) Frigør hukommelsen til "deleteNode"
Her er pseudokoden til at søge og slette en node fra en linket 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
Gennemse en dobbeltforbundet liste fra fremadrettet
At krydse fra hovedknuden og iterere over den næste knude, indtil vi finder "NULL". Mens vi krydser hver node, kan vi udskrive værdien af noden. Her er trinene til at krydse forfra (retning fremad):
Trin 1) Tildel en pointer eller variabel til den aktuelle hovedknude.
Trin 2) Gentag til den næste knude i hovedet, indtil du får "NULL"
Trin 3) Udskriv nodens data i hver iteration.
Trin 4) Returner hovedknuden.
Her er pseudokoden til at krydse en dobbeltforbundet liste fra forsiden:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Her er returneringen ikke obligatorisk. Men det er en god praksis at returnere hovedknuden efter operationerne.
Gå gennem en dobbeltforbundet liste bagfra
Denne operation er det omvendte af traversen forfra. Fremgangsmåden er den samme med en lille forskel. Vi skal krydse til endeknudepunktet og derefter krydse fra endeknudepunktet til det forreste knudepunkt.
Her er trinene til at krydse en dobbelt linket liste fra bagsiden:
Trin 1) Traverse indtil vi når haleknuden.
Trin 2) Fra haleknuden vil vi krydse, indtil vi får den forrige knude som "NULL". "Prev" (forrige markør) vil være nul for hovedknuden
Trin 3) Ved hver iteration udskriver vi nodedataene.
Her er pseudokoden til at krydse bagfra:
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
Forskellen mellem enkelt- og dobbeltforbundet liste
Den største forskel mellem Singly og Double Linked-listen er antallet af links.
Her er forskellen mellem noderne på en enkelt lænket liste og dobbelt lænket listes nodestruktur:
| Felt | Enkeltforbundet liste | Dobbeltforbundet liste |
|---|---|---|
| Struktur | Enkeltforbundet liste har et datafelt og et link til den næste node. | Dobbelt linket liste har et datafelt og to links. En for den forrige node og en anden for den næste node. |
| Traversal | Den kan kun krydse fra hoved til hale. | Den kan køre både frem og tilbage. |
| Hukommelse | Optager mindre hukommelse. | Det optager mere hukommelse end en enkelt-linket liste. |
| Tilgængelighed | Singly Linked Lists er mindre effektive, da de kun bruger ét link til den næste node. Der er intet link til den forrige node. | Dobbeltlinkede lister er mere effektive end enkeltlinkede lister. |
Dobbeltforbundet 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);
}
Produktion
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
Dobbeltforbundet 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()
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
Generelt er tidskompleksitet opdelt i tre typer.
De er:
- Bedste Sag
- Gennemsnitlig sag
- Værste tilfælde
Tidskompleksitet i bedste tilfælde for dobbeltforbundet liste:
- Indsættelse i hoved eller hale vil koste O(1). Fordi vi ikke behøver at krydse inde i den linkede liste. Hovedet og haleviseren kan give os adgang til hoved- og haleknuden med O(1) tidskompleksitet.
- Sletning ved hovedet eller halen vil koste O(1).
- Søgning i en knude vil have tidskompleksiteten som O(1). Fordi målknuden kan være hovedknuden.
Tidskompleksitet i det gennemsnitlige tilfælde for dobbeltforbundet liste:
- Indsættelse ved hovedet eller halen vil have tidskompleksiteten af omkostningerne O(1).
- Sletning ved hovedet eller halen vil have tidskompleksiteten af omkostningerne O(1).
- Søgning i en knude vil have tidskompleksiteten af O(n). Fordi søgeelementet kan ligge hvor som helst mellem den linkede liste. Her er "n" den samlede node, der er til stede i den sammenkædede liste.
Den værst tænkelige tidskompleksitet af den dobbeltforbundne liste vil være den samme som den gennemsnitlige sag.
Hukommelseskompleksitet af dobbeltforbundet liste
Hukommelseskompleksitet er O(n), hvor "n" er det samlede antal noder. Mens vi implementerer den sammenkædede liste, skal vi frigøre den hukommelse, vi brugte. Ellers vil det for en større sammenkædet liste forårsage hukommelseslækager.
Resumé
- En sammenkædet liste er en slags lineær datastruktur, en samling af data repræsenteret på en lineær måde.
- En dobbelt linket liste er en type linket liste, hvor en node har links til både den forrige og næste node.
- Dobbelt linket liste indeholder alle operationer som at tilføje en node, slette en node, indsætte en node efter eller før en anden node og at krydse den linkede liste fra hoved til hale.
- Dobbelt linket liste har et datafelt og to links. En for den forrige node og en anden for den næste node.
- Kompleksiteten af dobbeltforbundet liste Bedste sag, gennemsnitlig sag
- Og Worst Case.
