डेटा संरचनाओं में एकल लिंक्ड सूची
सारा चेन
सिंगल लिंक्ड सूची क्या है?
सिंगल लिंक्ड लिस्ट एक रैखिक और एकदिशात्मक डेटा संरचना है, जहाँ डेटा नोड्स पर सहेजा जाता है, और प्रत्येक नोड अपने अगले नोड से लिंक के माध्यम से जुड़ा होता है। प्रत्येक नोड में एक डेटा फ़ील्ड और अगले नोड के लिए एक लिंक होता है। सिंगल लिंक्ड लिस्ट को केवल एक दिशा में पार किया जा सकता है, जबकि डबल लिंक्ड लिस्ट को दोनों दिशाओं में पार किया जा सकता है।
यहां एकल लिंक्ड सूची की नोड संरचना दी गई है:
सारणी के स्थान पर लिंक्ड सूची का उपयोग क्यों करें?
ऐसे कई मामले हैं जब लिंक्ड सूची का उपयोग करना बेहतर होता है। ऐरेयहां कुछ परिदृश्य दिए गए हैं:
- तत्वों की अज्ञात संख्या: जब आपको यह पता नहीं होता कि प्रोग्राम रनटाइम के दौरान आपको कितने एलिमेंट स्टोर करने की ज़रूरत है, तो आप लिंक्ड लिस्ट का इस्तेमाल कर सकते हैं। जब आप लिंक्ड लिस्ट में एलिमेंट जोड़ते हैं, तो मेमोरी डायनेमिक रूप से आवंटित होती है।
- यादृच्छिक अभिगम: ऐसे परिदृश्य में, जहां आपको तत्वों से यादृच्छिक अभिगम का उपयोग करने की आवश्यकता नहीं है, आप लिंक्ड सूची का उपयोग कर सकते हैं।
- मध्य में सम्मिलन: किसी सरणी के बीच में प्रविष्टि करना एक जटिल कार्य है। क्योंकि आपको अन्य तत्वों को दाईं ओर धकेलना पड़ता है। हालाँकि, एक लिंक्ड सूची आपको किसी भी स्थान पर एक तत्व जोड़ने की अनुमति देती है।
Operaसिंगल लिंक्ड लिस्ट के लाभ
सिंगल लिंक्ड लिस्ट गतिशील रूप से मेमोरी आवंटित करने के लिए अच्छी है। यह लिंक्ड लिस्ट के सभी बुनियादी ऑपरेशन प्रदान करता है, जैसे कि, सम्मिलन, विलोपन, खोज, अद्यतन, दो लिंक्ड लिस्ट को मर्ज करना, ट्रैवर्सिंग, आदि।
यहां हम लिंक्ड सूची के निम्नलिखित संचालन पर चर्चा करेंगे:
- सिर पर लगाना
- पूंछ में सम्मिलित करना
- नोड के बाद सम्मिलित करना
- नोड से पहले सम्मिलित करना
- हेड नोड हटाएँ
- टेल नोड को हटाएँ
- नोड खोजें और हटाएं
- लिंक्ड सूची को पार करना
यहां चार नोड्स वाली लिंक्ड सूची का एक उदाहरण दिया गया है।
एकल लिंक्ड सूची के शीर्ष पर प्रविष्टि
यह एक सरल ऑपरेशन है। आम तौर पर, इसे सिंगल लिंक्ड लिस्ट को पुश करना कहते हैं। आपको एक नया नोड बनाना होगा और इसे लिंक्ड लिस्ट के शीर्ष पर रखना होगा।
इस ऑपरेशन को करने के लिए हमें दो महत्वपूर्ण शर्तों का पालन करना होगा।
- यदि सूची रिक्त है, तो नव निर्मित नोड हेड नोड होगा, और हेड का अगला नोड "NULL" होगा।
- यदि सूची रिक्त नहीं है, तो नया नोड हेड नोड होगा, तथा अगला नोड पिछले हेड नोड की ओर संकेत करेगा।
लिंक्ड सूची के शीर्ष पर नोड सम्मिलित करने के लिए छद्म कोड इस प्रकार है:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
एकल लिंक्ड सूची के अंत में प्रविष्टि
लिंक्ड लिस्ट के अंत में नोड डालने में हेड डालने के समान ही कुछ समानताएं हैं। आपको बस इतना करना है कि अंतिम नोड या टेल नोड तक जाएं। फिर अंतिम नोड के "अगले" नोड को नए बनाए गए नोड की ओर इंगित करें। यदि हेड नोड शून्य है, तो नया नोड हेड नोड होगा।
यहाँ कदम हैं:
चरण 1) तब तक आगे बढ़ें जब तक कि वर्तमान नोड का "अगला" नोड शून्य न हो जाए।
चरण 2) निर्दिष्ट मान के साथ एक नया नोड बनाएँ.
चरण 3) नये नोड को टेल नोड के अगले नोड के रूप में निर्दिष्ट करें।
एकल सूची के अंतिम छोर पर नोड सम्मिलित करने के लिए छद्म कोड:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
एकल लिंक्ड सूची में नोड के बाद प्रविष्टि
नोड के बाद डालने के दो भाग हैं: नोड की खोज करें और खोजे गए नोड के बाद संलग्न करें। हमें सभी नोड्स को पार करना होगा। प्रत्येक नोड के लिए, हमें खोज तत्व के साथ मिलान करने की आवश्यकता है। यदि कोई मिलान है, तो हम खोजे गए नोड के बाद नया नोड जोड़ देंगे।
यहाँ कदम हैं:
चरण 1) अगले नोड पर तब तक जाएँ जब तक कि वर्तमान नोड का मान खोज आइटम के बराबर न हो जाए।
चरण 2) नये नोड का अगला पॉइंटर वर्तमान नोड का अगला पॉइंटर होगा।
चरण 3) वर्तमान नोड का अगला नोड नया नोड होगा।
एक नोड के बाद एक नोड सम्मिलित करने के लिए छद्म कोड इस प्रकार है:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
एकल लिंक्ड सूची में नोड से पहले प्रविष्टि
यह फ़ंक्शन नोड के बाद सम्मिलन के समान है। हमें एक नया नोड बनाना होगा और लिंक्ड सूची को तब तक पार करना होगा जब तक कि वर्तमान नोड खोज नोड से मेल नहीं खाता। उसके बाद, हम नए नोड को वर्तमान नोड के पिछले नोड के रूप में जोड़ देंगे।
यहाँ कदम हैं:
चरण 1) तब तक आगे बढ़ें जब तक कि अगले नोड का मान खोज आइटम के बराबर न हो जाए।
चरण 2) एक नया नोड बनाएं और नोड के "अगले" को वर्तमान नोड के अगले नोड के साथ असाइन करें।
चरण 3) नये नोड को वर्तमान नोड के अगले नोड के रूप में निर्दिष्ट करें।
यहाँ छद्म कोड है:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
एकल लिंक्ड सूची का शीर्ष हटाएं
लिंक्ड लिस्ट के हर फंक्शन में हेड पॉइंटर को पैरामीटर के रूप में दिया जाता है। आपको हेड नोड को डिलीट करना होगा और हेड नोड के अगले नोड को लिंक्ड लिस्ट का नया हेड बनाना होगा। हमें डिलीट किए गए नोड की मेमोरी को भी खाली करना होगा। अन्यथा, जब कोई दूसरा प्रोग्राम इसे एक्सेस करने की कोशिश करेगा तो मेमोरी को ऑक्यूपाइड के रूप में चिह्नित किया जाएगा।
एकल लिंक्ड सूची के शीर्ष को हटाने के चरण यहां दिए गए हैं:
चरण 1) हेड नोड के अगले नोड को नए हेड के रूप में निर्दिष्ट करें।
चरण 2) पिछले हेड नोड द्वारा आवंटित मेमोरी को मुक्त करें.
चरण 3) नया हेड नोड लौटाएँ.
हेड नोड को हटाने के लिए छद्म कोड:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
एकल लिंक्ड सूची का अंतिम भाग हटाएँ
टेल नोड को हटाना हेड नोड को हटाने से ज़्यादा परिचित है। अंतर यह है कि हमें लिंक्ड लिस्ट के अंत तक जाना होगा और उसे हटाना होगा। सिंगल लिंक्ड लिस्ट में, अगला नोड "NULL" वाला नोड टेल नोड होता है।
लिंक्ड सूची के टेल नोड को हटाने के चरण यहां दिए गए हैं:
चरण 1) टेल नोड से पहले ट्रैवर्स करें। वर्तमान नोड को सेव करें।
चरण 2) वर्तमान नोड के अगले नोड की मेमोरी को मुक्त करें।
चरण 3) वर्तमान नोड के अगले नोड को NULL के रूप में सेट करें.
टेल नोड को हटाने के लिए छद्म कोड यहां दिया गया है:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
एकल लिंक्ड सूची से नोड खोजें और हटाएं
इस फ़ंक्शन के दो कार्य हैं, खोज और हटाना। हमें सिंगल लिंक्ड लिस्ट के अंत तक खोजना होगा। अगर हमें कोई समान नोड मिलता है, तो हम उसे हटा देंगे। उसके बाद, हमें हटाए गए नोड के बाएं और दाएं नोड को मर्ज या लिंक करना होगा। ऐसा करने के लिए ये चरण दिए गए हैं:
चरण 1) लिंक्ड सूची के अंत तक जाएँ। जाँचें कि वर्तमान नोड खोज नोड के बराबर है या नहीं।
चरण 2) यदि कोई नोड मेल खाता है, तो नोड पॉइंटर को वर्तमान नोड पर संग्रहीत करें।
चरण 3) पिछले नोड का “अगला” वर्तमान नोड का अगला नोड होगा।
चरण 4) वर्तमान नोड की मेमोरी को हटाएँ और मुक्त करें.
एकल लिंक्ड सूची से नोड को खोजने और हटाने के लिए छद्म कोड:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
एकल लिंक्ड सूची को पार करें
सिंगल लिंक्ड लिस्ट में केवल हेड से टेल तक जाने की कार्यक्षमता होती है। पिछले नोड के लिए कोई पॉइंटर पॉइंट नहीं हैं; इसलिए हम सिंगल लिंक्ड लिस्ट को उल्टे क्रम में नहीं पार कर सकते। हम प्रत्येक नोड को पार करेंगे और वर्तमान नोड का मान तब तक प्रिंट करेंगे जब तक कि हमें शून्य न मिल जाए।
यहाँ कदम हैं:
चरण 1) प्रत्येक नोड को तब तक पार करें जब तक हमें अगला नोड शून्य न मिल जाए।
चरण 2) वर्तमान नोड का मान प्रिंट करें.
एकल लिंक्ड सूची को पार करने के लिए छद्म कोड:
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
सिंगल लिंक्ड सूची का उदाहरण C++
#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
void insertAtHead(Node* &head, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if(head!=NULL){
newNode->next = head;
}
head = newNode;
cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
if(head==NULL){
insertAtHead(head,value);
}
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newNode;
cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
Node *temp = new Node();
if( (*headPtr)->data == searchItem ){
temp = *headPtr;
*headPtr = (*headPtr)->next;
free(temp);
}else{
Node *currentNode = *headPtr;
while(currentNode->next != NULL){
if(currentNode->next->data == searchItem){
temp = currentNode->next;
currentNode->next = currentNode->next->next;
free(temp);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->next->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
Node* tempNode = new Node();
tempNode = headPointer;
cout<<"Traversal from head:\t";
while(tempNode !=NULL){
cout<<tempNode->data;
if(tempNode->next)
cout<<" --> ";
tempNode = tempNode ->next;
}
cout<<endl;
}
int main(){
Node *head = NULL;
insertAtHead(head,5);
insertAtHead(head,6);
insertAtHead(head,7);
insertEnd(head,9);
traverse(head);
searchAndDelete(&head,6);
traverse(head);
insertAfter(head,7,10);
insertBefore(head,9,11);
traverse(head);
}
आउटपुट:
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9
सिंगल लिंक्ड सूची का उदाहरण Python कार्यक्रम
class Node:
def __init__(self,data = None, next = None):
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def insertAtHead(self, value):
newNode = Node(data=value)
if self.head is not None:
newNode.next = self.head
self.head = newNode
print(f'Added {newNode.data} at the front.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
newNode = Node(value)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
print(f'Added {newNode.data} at the end.')
def searchAndDelete(self,searchItem):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
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
print(f'Inserted {value} after node\t{searchItem}')
return
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
print(f'Inserted {value} before node\t{searchItem}')
return
def traverse(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()
आउटपुट:
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
सिंगल लिंक्ड सूची की जटिलता
जटिलता के दो प्रकार हैं: समय जटिलता और स्थान जटिलता। सबसे खराब और औसत मामले में समय जटिलता सिंगल लिंक्ड सूची के लिए समान है।
सर्वोत्तम स्थिति के लिए समय जटिलता:
- हेड में सम्मिलन O(1) में किया जा सकता है। क्योंकि हमें लिंक्ड सूची के अंदर जाने की आवश्यकता नहीं है।
- यदि खोज तत्व हेड नोड में मौजूद है तो खोज और डिलीट ऑपरेशन O(1) में किया जा सकता है।
औसत मामले के लिए समय जटिलता:
- यदि एकल लिंक्ड सूची में “n” तत्व मौजूद हैं, तो लिंक्ड सूची के अंदर प्रविष्टि O(n) लेगी।
- सर्च और डिलीट में O(n) भी लग सकता है, क्योंकि सर्च एलिमेंट टेल नोड में मौजूद हो सकता है। उस स्थिति में, आपको पूरी सूची को पार करना चाहिए।
सिंगल लिंक्ड सूची की स्थान जटिलता
सिंगल लिंक्ड लिस्ट गतिशील रूप से मेमोरी आवंटित करती है। यदि हम n तत्वों को संग्रहीत करना चाहते हैं, तो यह n मेमोरी यूनिट आवंटित करेगी। इसलिए, स्पेस जटिलता O(n) है।
