दोहरी लिंक सूची: C++, Python (कोड उदाहरण)
सारा चेन
दोहरी लिंक्ड सूची क्या है?
डबल लिंक्ड लिस्ट में, प्रत्येक नोड में पिछले और अगले दोनों नोड से लिंक होते हैं। प्रत्येक नोड में तीन तत्व होते हैं: एक में डेटा होता है, और अन्य दो अगले और पिछले नोड के पॉइंटर्स होते हैं। ये दो पॉइंटर्स हमें किसी विशेष नोड से आगे या पीछे जाने में मदद करते हैं।
यहाँ दोहरी लिंक्ड सूची की मूल संरचना दी गई है।
हर लिंक्ड लिस्ट में एक हेड और टेल नोड होता है। हेड नोड में कोई “प्रीव” (पिछला पॉइंटर) नोड नहीं होता है, और टेल नोड में कोई “नेक्स्ट” नोड नहीं होता है।
दोहरी लिंक्ड सूची के लिए कुछ महत्वपूर्ण शब्द यहां दिए गए हैं:
- पिछला: प्रत्येक नोड अपने पिछले नोड से जुड़ा होता है। इसका उपयोग पॉइंटर या लिंक के रूप में किया जाता है।
- अगला: प्रत्येक नोड अपने अगले नोड से जुड़ा होता है। इसका उपयोग पॉइंटर या लिंक के रूप में किया जाता है।
- तारीख: इसका उपयोग नोड में डेटा संग्रहीत करने के लिए किया जाता है। “डेटा” अन्य को भी रख सकता है डेटा संरचनाएं इसके अंदर। उदाहरण के लिए, स्ट्रिंग, डिक्शनरी, सेट, हैशमैप, आदि को "डेटा" में संग्रहीत किया जा सकता है।
दोहरी लिंक्ड सूची में एकल नोड की मूल संरचना इस प्रकार है:
Operaडबल लिंक्ड सूची के परिणाम
दोहरी लिंक्ड सूची के कार्यों में नोड्स जोड़ना और हटाना, नोड्स सम्मिलित करना और हटाना, तथा लिंक्ड सूची को ऊपर से नीचे तक ले जाना शामिल है।
यहां उन कार्यों की सूची दी गई है जिन्हें हम दोहरी लिंक्ड सूची का उपयोग करके कार्यान्वित कर सकते हैं:
- सामने सम्मिलन
- पूंछ या अंतिम नोड में सम्मिलन
- नोड के बाद प्रविष्टि
- नोड से पहले प्रविष्टि
- सामने से हटाना
- पूंछ से विलोपन
- नोड खोजें और हटाएं
- सिर से पूंछ तक पार करें
- पूंछ से सिर तक ले जाएं
हम ऊपर दिए गए सभी कार्यों के कार्यान्वयन और छद्म कोड को देखेंगे।
डबली लिंक्ड सूची के सामने प्रविष्टि
सामने सम्मिलन का अर्थ है कि हमें लिंक्ड सूची में एक नोड बनाना होगा और उसे लिंक्ड सूची के आरंभ में रखना होगा।
उदाहरण के लिए, एक नोड “15” दिया गया है। हमें इसे हेड नोड में जोड़ना होगा।
इस ऑपरेशन को करते समय दो महत्वपूर्ण शर्तें हैं:
- यदि डबली लिंक्ड सूची में कोई नोड नहीं है तो नया नोड हेड नोड होगा।
- यदि पहले से ही कोई हेड नोड मौजूद है, तो पिछले हेड को नए नोड से प्रतिस्थापित कर दिया जाएगा।
इस ऑपरेशन के लिए छद्म कोड इस प्रकार है:
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
दोहरी लिंक्ड सूची के अंत में प्रविष्टि
"अंत में सम्मिलन" का अर्थ है कि हम लिंक्ड सूची में एक नोड बनाएंगे और इसे अंत में रखेंगे।
ऐसा करने के लिए हम दो तरीकों का उपयोग कर सकते हैं:
- विधि 1: डबली लिंक्ड लिस्ट के हेड से तब तक ट्रैवर्स करना शुरू करें जब तक कि “नेक्स्ट” शून्य न हो जाए। फिर नए नोड को “नेक्स्ट” से लिंक करें।
- विधि 2: डबली लिंक्ड लिस्ट का आखिरी नोड लें। फिर, आखिरी नोड का “अगला” नोड नए नोड से लिंक हो जाएगा। अब, नया नोड टेल नोड होगा।
यहां टेल नोड पर सम्मिलन के लिए छद्म कोड दिया गया है:
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
नोड के बाद प्रविष्टि
मान लीजिए कि हमारे पास निम्नलिखित जैसी एक दोहरी लिंक्ड सूची मौजूद है:
हम एक दिया गया नोड सम्मिलित करना चाहते हैं जो उस नोड के बाद लिंक किया जाएगा, जिसका मान “12” है।
इसके लिए ये चरण हैं:
चरण 1) सिर से अंतिम नोड तक जाएँ। जाँचें कि किस नोड का मान “12” है।
चरण 2) एक नया नोड बनाएँ और इसे नोड “12” के अगले पॉइंटर के रूप में असाइन करें। नए नोड का “अगला” नोड 15 होगा।
दोहरी लिंक्ड सूची में एक नोड के बाद एक नोड सम्मिलित करने के लिए छद्म कोड इस प्रकार है:
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
नोड से पहले प्रविष्टि
यह ऑपरेशन "नोड के बाद सम्मिलन" के समान है। इसे करने के लिए हमें एक विशिष्ट नोड के मान की खोज करनी होगी। फिर हम एक नया नोड बनाएंगे और उसे खोजे गए नोड से पहले डालेंगे।
मान लीजिए कि हम दिए गए नोड “15” को नोड “12” से पहले डालना चाहते हैं। तो ऐसा करने के लिए ये चरण हैं:
चरण 1) लिंक्ड सूची को हेड नोड से टेल नोड तक ले जाएँ।
चरण 2) जाँचें कि वर्तमान नोड के अगले पॉइंटर का मान “12” है या नहीं।
चरण 3) नए नोड को वर्तमान नोड के “अगले” नोड के रूप में सम्मिलित करें।
दोहरी लिंक्ड सूची में नोड से पहले नोड डालने के लिए छद्म कोड इस प्रकार है:
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
दोहरी लिंक्ड सूची का शीर्ष हटाएं
डबल लिंक्ड लिस्ट में हेड नोड जिसमें कोई पिछला नोड नहीं है। इसलिए, अगर हम हेड नोड को हटाना चाहते हैं तो अगला पॉइंटर नया हेड नोड होगा। नोड को हटाते समय हमें नोड द्वारा कब्जा की गई मेमोरी को भी खाली करना होगा।
हेड नोड को हटाने के चरण इस प्रकार हैं:
चरण 1) वर्तमान हेड नोड को एक चर निर्दिष्ट करें.
चरण 2) वर्तमान हेड नोड के "अगले" नोड पर जाएँ और "प्रीव" (पिछले पॉइंटर) नोड को ''NULL" बनाएँ। इसका मतलब है कि हम दूसरे नोड को पहले नोड से अलग कर रहे हैं।
चरण 3) पिछले हेड नोड द्वारा अधिगृहित मेमोरी को मुक्त करें।
यहां दोहरी लिंक्ड सूची से शीर्ष को हटाने के लिए छद्म कोड दिया गया है:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
किसी भी तरह के डिलीट ऑपरेशन को करने के बाद आवंटित मेमोरी को डिलीट करना ज़रूरी है। अन्यथा, प्रोग्राम के पूरे रनटाइम के दौरान, डिलीट किए गए ब्लॉक की मेमोरी भरी रहेगी। कोई भी दूसरा एप्लिकेशन उस मेमोरी सेगमेंट का इस्तेमाल नहीं कर सकता।
दोहरी लिंक्ड सूची की पूंछ को हटाएँ।
यह ऑपरेशन हेड को हटाने जैसा ही है। यहाँ, हेड के बजाय, हमें टेल को हटाना होगा। किसी नोड को टेल नोड के रूप में पहचानने के लिए, हमें यह जाँचना चाहिए कि अगला पॉइंटर या अगला नोड शून्य है या नहीं। टेल को हटाने के बाद, हमें मेमोरी को खाली करना होगा।
इस ऑपरेशन को “पीछे से हटाना” के नाम से भी जाना जाता है।
ऐसा करने के लिए ये चरण हैं:
चरण 1) दोहरी लिंक्ड सूची के टेल नोड तक आगे बढ़ें।
चरण 2) टेल नोड को एक चर या पॉइंटर असाइन करें.
चरण 3) “अगले” नोड को NULL बनाएं और टेल नोड की मेमोरी को मुक्त करें।
टेल नोड को हटाने के लिए छद्म कोड यहां दिया गया है:
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
डबली लिंक्ड सूची से नोड खोजें और हटाएं
यह ऑपरेशन हमें एक विशिष्ट नोड डेटा की खोज करने और उस नोड को हटाने की अनुमति देता है। हमें एक रैखिक खोज करने की आवश्यकता है क्योंकि लिंक्ड सूची एक रैखिक डेटा संरचना है। हटाने के बाद, हमें मेमोरी को भी खाली करना होगा।
दोहरी लिंक्ड सूची में नोड को खोजने और हटाने के चरण यहां दिए गए हैं:
चरण 1) लिंक्ड सूची को शीर्ष से तब तक पार करें जब तक कि नोड का मान खोज आइटम के बराबर न हो जाए।
चरण 2) सुमेलित नोड को एक चर “deleteNode” असाइन करें।
चरण 3) “deleteNode” के पिछले नोड को अगले नोड पर असाइन करें।
चरण 4) “डिलीट नोड” की मेमोरी को मुक्त करें
लिंक्ड सूची से नोड को खोजने और हटाने के लिए छद्म कोड यहां दिया गया है:
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
आगे से एक दोहरी लिंक्ड सूची को पार करें
हेड नोड से आगे बढ़ना और अगले नोड पर तब तक चलना जब तक हमें “NULL” न मिल जाए। प्रत्येक नोड से आगे बढ़ते समय, हम नोड का मान प्रिंट कर सकते हैं। आगे से आगे बढ़ने के लिए ये चरण दिए गए हैं:
चरण 1) वर्तमान हेड नोड को एक पॉइंटर या वेरिएबल असाइन करें.
चरण 2) “NULL” प्राप्त होने तक सिर के अगले नोड पर पुनरावृति करें
चरण 3) प्रत्येक पुनरावृत्ति में नोड का डेटा प्रिंट करें.
चरण 4) हेड नोड लौटाएं.
यहां डबली लिंक्ड सूची को सामने से पार करने के लिए छद्म कोड दिया गया है:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
यहाँ, रिटर्न अनिवार्य नहीं है। लेकिन ऑपरेशन के बाद हेड नोड को वापस करना एक अच्छा अभ्यास है।
पीछे से एक दोहरी लिंक्ड सूची को पार करें
यह ऑपरेशन सामने से ट्रैवर्स करने का उलटा है। दृष्टिकोण वही है, बस थोड़ा अंतर है। हमें अंतिम नोड तक ट्रैवर्स करना चाहिए और फिर अंतिम नोड से सामने वाले नोड तक ट्रैवर्स करना चाहिए।
दोहरी लिंक्ड सूची को पीछे से पार करने के चरण यहां दिए गए हैं:
चरण 1) तब तक आगे बढ़ते रहें जब तक हम टेल नोड तक न पहुंच जाएं।
चरण 2) टेल नोड से, हम तब तक आगे बढ़ेंगे जब तक हमें पिछला नोड “NULL” न मिल जाए। हेड नोड के लिए “prev” (पिछला पॉइंटर) शून्य होगा
चरण 3) प्रत्येक पुनरावृत्ति पर, हम नोड डेटा प्रिंट करेंगे।
पीछे से आगे बढ़ने के लिए छद्म कोड इस प्रकार है:
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
सिंगल और डबल लिंक्ड सूची के बीच अंतर
सिंगल और डबल लिंक्ड सूची के बीच मुख्य अंतर लिंक की संख्या है।
एकल लिंक्ड सूची के नोड्स और दोहरी लिंक्ड सूची के नोड संरचना के बीच अंतर इस प्रकार है:
| क्षेत्र | एकल रूप से लिंक की गई सूची | डबल लिंक्ड लिस्ट |
|---|---|---|
| संरचना | एकल रूप से लिंक की गई सूची इसमें एक डेटा फ़ील्ड और अगले नोड के लिए एक लिंक होता है। | डबल लिंक्ड लिस्ट में एक डेटा फ़ील्ड और दो लिंक होते हैं। एक पिछले नोड के लिए और दूसरा अगले नोड के लिए। |
| traversal | यह केवल सिर से पूंछ तक ही चल सकता है। | यह आगे और पीछे दोनों ओर जा सकता है। |
| याद | कम मेमोरी घेरता है. | यह एकल लिंक्ड सूची की तुलना में अधिक मेमोरी घेरता है। |
| आसान इस्तेमाल | सिंगल लिंक्ड लिस्ट कम कुशल होती हैं क्योंकि वे अगले नोड के लिए केवल एक लिंक का उपयोग करती हैं। पिछले नोड के लिए कोई लिंक नहीं है। | डबल लिंक्ड सूचियाँ, सिंगल लिंक्ड सूचियों की तुलना में अधिक कुशल होती हैं। |
डबल लिंक्ड सूची 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);
}
उत्पादन
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
डबल लिंक्ड सूची 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()
उत्पादन
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
डबल लिंक्ड सूची की जटिलता
सामान्यतः समय जटिलता को तीन प्रकारों में विभाजित किया जाता है।
वे हैं:
- सबसे अच्छा मामला
- औसत मामला
- सबसे खराब मामला
डबली लिंक्ड सूची के लिए सर्वोत्तम स्थिति में समय जटिलता:
- हेड या टेल में सम्मिलन की लागत O(1) होगी। क्योंकि हमें लिंक्ड सूची के अंदर जाने की आवश्यकता नहीं है। हेड और टेल पॉइंटर हमें O(1) समय जटिलता के साथ हेड और टेल नोड तक पहुँच प्रदान कर सकते हैं।
- सिर या पूंछ पर विलोपन की लागत O(1) होगी।
- नोड की खोज करने पर समय जटिलता O(1) होगी। क्योंकि लक्ष्य नोड हेड नोड हो सकता है।
डबली लिंक्ड सूची के लिए औसत मामले में समय जटिलता:
- शीर्ष या पूँछ पर सम्मिलन की समय जटिलता लागत O(1) होगी।
- शीर्ष या पूँछ पर विलोपन की समय जटिलता लागत O(1) होगी।
- नोड को खोजने में O(n) की समय जटिलता होगी। क्योंकि खोज आइटम लिंक्ड सूची के बीच कहीं भी रह सकता है। यहाँ, "n" लिंक्ड सूची में मौजूद कुल नोड है।
दोहरी लिंक्ड सूची की सबसे खराब स्थिति में समय जटिलता औसत स्थिति के समान ही होगी।
डबली लिंक्ड सूची की मेमोरी जटिलता
मेमोरी जटिलता O(n) है, जहाँ “n” नोड्स की कुल संख्या है। लिंक्ड लिस्ट को लागू करते समय हमें उस मेमोरी को खाली करना होगा जिसका हमने उपयोग किया है। अन्यथा, एक बड़ी लिंक्ड लिस्ट के लिए, यह मेमोरी लीकेज का कारण बनेगी।
सारांश
- लिंक्ड सूची एक प्रकार की रैखिक डेटा संरचना है, जो रैखिक तरीके से प्रदर्शित डेटा का संग्रह है।
- दोहरी लिंक्ड सूची एक प्रकार की लिंक्ड सूची है, जहां एक नोड का पिछले और अगले दोनों नोड के साथ लिंक होता है।
- दोहरी लिंक्ड सूची में सभी ऑपरेशन शामिल होते हैं जैसे नोड जोड़ना, नोड हटाना, किसी नोड को दूसरे नोड के बाद या पहले सम्मिलित करना, तथा लिंक्ड सूची को शीर्ष से लेकर अंत तक ले जाना।
- डबल लिंक्ड लिस्ट में एक डेटा फ़ील्ड और दो लिंक होते हैं। एक पिछले नोड के लिए और दूसरा अगले नोड के लिए।
- डबली लिंक्ड लिस्ट की जटिलता सर्वश्रेष्ठ मामला, औसत मामला
- और सबसे ख़राब स्थिति.
