Dubbel gekoppelde lijst: C++, Python (Codevoorbeeld)
Sara Chen
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.
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:
Operavan de Dubbel Gelinkte 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 bekijken de implementatie en pseudocode voor alle bovenstaande bewerkingen.
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.
Er zijn twee belangrijke voorwaarden bij het uitvoeren van deze bewerking:
- Het nieuwe knooppunt zal het hoofdknooppunt zijn als er geen knooppunt in de dubbel gekoppelde lijst staat.
- 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 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 na een knooppunt
Stel dat we een bestaande dubbel gekoppelde lijst hebben, zoals de volgende:
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 vóór een knooppunt
Deze bewerking lijkt meer op de "insertion after a node". We moeten zoeken naar de waarde van een specifieke node om dit uit te voeren. Vervolgens maken we een nieuwe node en voegen deze in voor de gezochte node.
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
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 is noodzakelijk om het toegewezen geheugen te verwijderen na het uitvoeren van een verwijderingsbewerking. Anders blijft het geheugen voor het verwijderde blok tijdens de gehele looptijd van het programma bezet. Geen enkele andere toepassing kan dat geheugensegment gebruiken.
Verwijder de staart van de dubbel gelinkte lijst.
Deze bewerking is ongeveer hetzelfde als het verwijderen van de head. In plaats van de head moeten we hier de tail verwijderen. Om een node te identificeren als tail node, moeten we controleren of de next pointer of next node null is of niet. Nadat we de tail hebben verwijderd, moeten we het geheugen vrijmaken.
Deze operatie wordt ook wel ‘verwijderen van achteren’ 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
Zoek en verwijder een knooppunt uit de dubbel gekoppelde lijst
Met deze bewerking kunnen we zoeken naar specifieke node-gegevens en die node verwijderen. We moeten een lineaire zoekopdracht uitvoeren, omdat de gekoppelde lijst een lineaire datastructuur is. Na het verwijderen moeten we ook het geheugen vrijmaken.
Dit zijn de stappen voor het zoeken en 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 het zoeken en 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
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 de return niet verplicht. Maar het is een goede gewoonte om de head node na de operations te returnen.
Doorloop een dubbel gekoppelde lijst van achteren naar achteren
Deze operatie is het omgekeerde van de traverse vanaf de voorkant. De aanpak is hetzelfde met een klein verschil. We moeten naar het eindknooppunt traverseren en dan van het eindknooppunt naar het voorste knooppunt traverseren.
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.
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
Complexiteit van dubbel gekoppelde lijst
Over het algemeen wordt tijdcomplexiteit onderverdeeld in drie typen.
Dat zijn:
- Beste geval
- Gemiddeld geval
- Het slechtste geval
Tijdcomplexiteit in het beste geval voor een dubbel gekoppelde lijst:
- Insertie in head of tail kost O(1). Omdat we niet binnen de gekoppelde lijst hoeven te traverseren. De head en tail pointer kunnen ons toegang geven tot de head en tail node met O(1) tijdcomplexiteit.
- Verwijdering aan de kop of staart kost O(1).
- Het zoeken naar een knooppunt heeft een tijdcomplexiteit van O(1), omdat het doelknooppunt het hoofdknooppunt kan zijn.
Tijdcomplexiteit in het gemiddelde geval voor een dubbel gekoppelde lijst:
- Invoeging aan de kop of de staart heeft een tijdcomplexiteit van kosten O(1).
- Verwijdering aan de kop of de staart heeft een tijdcomplexiteit van kosten O(1).
- Het zoeken naar een knooppunt heeft de tijdcomplexiteit van O(n). Omdat het zoekitem overal in de gekoppelde lijst kan staan. Hierbij is "n" het totale knooppunt dat aanwezig is in de gekoppelde lijst.
De tijdscomplexiteit van de dubbel gekoppelde lijst in het slechtste geval zal gelijk zijn aan die in het gemiddelde geval.
Geheugencomplexiteit van dubbel gekoppelde lijst
Geheugencomplexiteit 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. Anders zal het voor een grotere gekoppelde lijst geheugenlekken veroorzaken.
Samenvatting
- 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.
- Een dubbel gekoppelde lijst bevat alle bewerkingen, zoals het toevoegen van een knooppunt, het verwijderen van een knooppunt, het invoegen van een knooppunt na of voor 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.
- Complexiteit van dubbel gekoppelde lijst Beste geval, gemiddeld geval
- En in het slechtste geval.
