तो, मुझे लिंक्ड सूची के बारे में बताओ
हाल ही में एक कोडिंग बूटकैम्प से स्नातक होने के बाद, मैं अपने मौलिक ज्ञान को बेहतर बनाने के लिए डेटा संरचनाओं और एल्गोरिदम का अध्ययन करने में गहन रहा हूं। लिंक की गई सूचियां अपेक्षाकृत सरल डेटा संरचना हैं, लेकिन अधिक जटिल डेटा संरचनाओं के आगे बढ़ने का आधार है। यह लेख लिंक की गई सूचियों पर चर्चा करेगा - उनकी ताकत, कमजोरियां, और उन्हें कैसे लागू किया जाए।
डेटा संरचनाएं, बस, कुशलता से डेटा को व्यवस्थित करने और धारण करने के तरीके हैं
डेटा संरचनाएं क्या हैं?
डेटा संरचनाएं, बस, कुशलता से डेटा को व्यवस्थित करने और धारण करने के तरीके हैं। ये हमें जानकारी रखने की अनुमति देते हैं ताकि हम बाद में उनके लिए उपयोग कर सकें - एक विशिष्ट वस्तु की खोज कर सकते हैं, या उन्हें एक निश्चित क्रम या बड़े डेटासेट प्रबंधित करने के लिए सॉर्ट कर सकते हैं। जावास्क्रिप्ट में डेटा संरचनाएं होती हैं, जिनसे आप संभवतः परिचित हैं - सरणियाँ और ऑब्जेक्ट। ये आदिम डेटा संरचनाएं हैं जो भाषा के मूल निवासी हैं। गैर-आदिम डेटा संरचनाएं डेटा संरचनाएं हैं जो प्रोग्रामर द्वारा परिभाषित की जाती हैं। उदाहरणों में ढेर, कतार, पेड़, ग्राफ और हैश टेबल शामिल हैं।
लिंक्ड सूची क्या हैं?
एक लिंक की गई सूची एक रैखिक डेटा संरचना है जो अनुक्रमिक क्रम में तत्वों को रखती है। जाना पहचाना? वे सरणियों के समान हैं, लेकिन वे समान नहीं हैं। सरणी शून्य-अनुक्रमित होती है , जिसका अर्थ है कि प्रत्येक सूचकांक को एक मूल्य पर मैप किया जाता है, और सरणी का पहला तत्व 0. के सूचकांक में शुरू होता है। आप आसानी से सरणी से तत्वों को खींच सकते हैं, इसलिए जब तक आप सूचकांक को नहीं जानते।
दूसरी ओर, एक लिंक की गई सूची में नोड्स होते हैं जो अन्य नोड्स को इंगित करते हैं। प्रत्येक नोड केवल स्वयं और अगले नोड को जानता है। एक रैखिक डेटा संरचना के रूप में, आइटम क्रम में व्यवस्थित होते हैं। आप इसके बारे में एक ट्रेन के रूप में सोच सकते हैं - प्रत्येक रेल कार अगले रेल कार से जुड़ी हुई है, और इसी तरह। लिंक की गई सूचियाँ अनुक्रमित नहीं हैं , इसलिए आप सीधे 5 वें तत्व तक नहीं पहुँच सकते। आपको शुरुआत में शुरू करना होगा, अगले पर जाना होगा, और अगले तक जाना होगा जब तक आप 5 वें तत्व को नहीं ढूंढ लेते। पहले नोड को सिर कहा जाता है, और अंतिम नोड को पूंछ कहा जाता है। विभिन्न प्रकार की लिंक्ड लिस्ट हैं- सिंगली लिंक्ड लिस्ट, डबल लिंक्ड लिस्ट और सर्कुलर लिंक्ड लिस्ट। इस लेख की खातिर, मैं एकल लिंक की गई सूची पर ध्यान केंद्रित करूंगा।
सरणी में तत्वों को एक्सेस करना आसान है, लेकिन यह एक लागत पर आता है।
क्यों Arrays पर लिंक्ड सूची का उपयोग करें?
आप सोच रहे होंगे - लेकिन अगर मैं एरे के साथ तत्वों को सीधे एक्सेस कर सकता हूं तो इसका उपयोग क्यों करें? यह सच है! सरणी में तत्वों को एक्सेस करना आसान है, लेकिन यह एक लागत पर आता है।
ऐरे को अनुक्रमित किया जाता है - इसलिए जब भी आपको शुरुआत या मध्य से किसी तत्व को निकालने की आवश्यकता होती है, तो निम्नलिखित सभी सूचकांकों को स्थानांतरित करने की आवश्यकता होती है। यह भी सच है यदि आपको एक तत्व सम्मिलित करने की आवश्यकता है - सभी निम्नलिखित तत्वों को फिर से जोड़ने की आवश्यकता है। किसी लिंक की गई सूची से तत्वों को सम्मिलित करते या निकालते समय, आपको पुन: जुड़ने की आवश्यकता नहीं होती है - यह सब परवाह करता है कि यह नोड है जो इसे इंगित करता है ।
एक लिंक्ड लिस्ट को लागू करना
विभिन्न प्रकार की लिंक्ड लिस्ट हैं- सिंगल, डबल और सर्कुलर। सिंगली लिंक्ड लिस्ट एक प्रकार की लिंक्ड लिस्ट होती है, जहां प्रत्येक नोड का मान और अगले नोड के लिए एक पॉइंटर होता है (यदि यह टेल बेल है तो शून्य)। दूसरी ओर, संदेह से जुड़ी सूचियाँ, पिछले नोड के लिए एक अतिरिक्त सूचक है। सर्कुलर लिंक्ड लिस्ट वहीं हैं जहां टेल नोड हेड हेड पर वापस जाता है।
नोट: यदि आप एक दृश्य शिक्षार्थी हैं, तो VisuAlgo चारों ओर खेलने और डेटा संरचना को परिवर्तनों के माध्यम से देखने के लिए एक शानदार जगह है।
यदि आप पूर्ण कोड के लिए आगे छोड़ना चाहते हैं: इस GitHub gist को चेकआउट करें ।
एक नोड बनाना
उपयोग करने के लिए एक नोड के निर्माण से शुरू करते हैं। इसका मान और अगला पॉइंटर होगा , जो इसके बाद के पड़ोसी को इंगित करेगा।
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
हम सिंगालीलिंकडलिस्ट नामक एक वर्ग का निर्माण शुरू करेंगे और इसे सिर, पूंछ और सूची की लंबाई के लिए एक आधार देंगे।
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
अंत में एक नोड जोड़ने के लिए, हम जांच करेंगे कि क्या सूची में पहले से ही घोषित किया गया सिर है। यदि नहीं, तो नव निर्मित नोड होने के लिए सिर और पूंछ सेट करें। यदि पहले से ही एक हेड प्रॉपर्टी है, तो अगली प्रॉपर्टी को टेल पर नए नोड में सेट करें, और टेल प्रॉपर्टी को नया नोड बनाने के लिए। हम 1 से लंबाई बढ़ाएंगे।
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
अंत में एक नोड को हटाने के लिए, हमें पहले यह देखना होगा कि सूची में नोड्स हैं या नहीं। यदि नोड्स हैं, तो हमें सूची तक लूप करना होगा जब तक हम पूंछ तक नहीं पहुंचते। हम दूसरी से अंतिम नोड तक की अगली संपत्ति को शून्य कर देंगे, टेल प्रॉपर्टी को उस नोड पर सेट करेंगे, लंबाई 1 से घटाएंगे, और हटाए गए नोड का मान वापस करेंगे।
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
नोड को शुरुआत से हटाने के लिए, हम जाँचते हैं कि सूची में नोड्स हैं या नहीं। हम वर्तमान मुख्य संपत्ति को एक चर में संग्रहीत करेंगे, और सिर को वर्तमान सिर के अगले नोड के रूप में सेट करेंगे। लंबाई 1 से घटाएं और हटाए गए नोड का मान लौटाएं।
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
शुरुआत में एक नोड जोड़ने के लिए, हम पहले नोड बनाते हैं और जांचते हैं कि क्या सूची में एक प्रमुख संपत्ति है। यदि ऐसा है, तो नए बनाए गए नोड की अगली संपत्ति को वर्तमान सिर पर सेट करें, नए नोड पर सिर सेट करें और लंबाई बढ़ाएँ।
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
सूची में अपनी स्थिति के आधार पर नोड तक पहुँचने के लिए, हम पहले जाँच करेंगे कि क्या सूचकांक एक वैध सूचकांक है। काउंटर चर रखने के बाद, हम सूची के माध्यम से लूप करेंगे। एक बार जब काउंटर चर सूचकांक से मेल खाता है, तो हम पाया गया नोड वापस कर देंगे
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
नोड की अपनी स्थिति के आधार पर बदलने के लिए, हम पहले नोड प्राप्त करते हैं, प्राप्त विधि का उपयोग करते हुए और नए मान पर मान सेट करते हैं।
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
नोड सम्मिलित करने के लिए, हम पहले इंडेक्स की जांच करते हैं। यदि यह 0 के बराबर है, तो हम अपनी अनशिफ्ट विधि का उपयोग करते हैं। यदि यह लंबाई के बराबर है, तो हम इसे सूची में धकेल देते हैं। अन्यथा, हम अनुक्रमणिका की तुलना में एक कम पर विधि प्राप्त करके पहले नोड प्राप्त करेंगे। अनिवार्य रूप से, हमें अपने सूचक को सही नोड की ओर निर्देशित करने के लिए चयनित सूचकांक से पहले और बाद में नोड का ट्रैक रखने की आवश्यकता है।
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
स्थिति के आधार पर एक नोड को निकालने के लिए, हम अपनी विधि को फिर से उपयोग करेंगे, और उसी सिद्धांत का उपयोग करेंगे जिसका उपयोग हमने नोड डालने के लिए किया था। चुने हुए अनुक्रमणिका के पिछले नोड का ट्रैक रखकर, हम अपने संकेत पैंतरेबाज़ी कर सकते हैं।
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
लिंक्ड सूची की ताकत
लिंक की गई सूची का उपयोग करने का लाभ तत्वों को जल्दी से सम्मिलित करने और निकालने की क्षमता है। क्योंकि लिंक की गई सूचियाँ अनुक्रमित नहीं हैं, इसलिए तत्व सम्मिलित करना त्वरित और आसान है।
लिंक की गई सूची के अंत में जोड़ने के लिए बस पुरानी पूंछ को नए नोड को इंगित करने की आवश्यकता होती है, और पूंछ की संपत्ति को नए नोड में सेट किया जाना है। लिंक की गई सूची की शुरुआत में जोड़ना एक ही आधार है, लेकिन नया नोड पुराने सिर को इंगित करता है, और सिर की संपत्ति नए नोड पर सेट होती है। मौलिक रूप से समान क्रियाएं, इसलिए सम्मिलन हे (1) है।
नोट: लिंक की गई सूची के बीच में सम्मिलित होकर, अपने नोड (O (N)) को खोजने और फिर नोड (O (1)) सम्मिलित करने की आवश्यकता होती है।
लिंक की गई सूची से एक नोड को निकालना आसान हो सकता है ... लेकिन यह भी नहीं। यह कहां पर निर्भर करता है। सूची की शुरुआत से एक नोड को हटाना सरल है - दूसरा नोड नया सिर बन जाता है, और हम पुराने सिर के अगले सूचक को शून्य करने के लिए सेट करते हैं। अंत से हटाना मुश्किल है क्योंकि इसके लिए पूरी सूची से गुजरना पड़ता है और दूसरे से अंतिम नोड तक रुकना पड़ता है। सबसे खराब मामला ओ (एन), और सबसे अच्छा मामला ओ (1)।
लिंक्ड सूची की कमजोरियाँ
लिंक की गई सूची की कमजोरियाँ इसकी रीइंडेक्सिंग की कमी के कारण होती हैं। क्योंकि आप तत्वों को सीधे एक्सेस नहीं कर सकते हैं, यह तत्वों को खोजना और एक्सेस करना कठिन बनाता है।
लिंक की गई सूची में एक नोड को खोजना और एक्सेस करना सूची की शुरुआत में शुरू होता है और सूची के नीचे ब्रेडक्रंब के निशान का पालन करना होता है। यदि हम सूची के अंत में नोड की खोज कर रहे हैं, तो हमें पूरी तरह से लिंक की गई सूची से गुजरना होगा, प्रभावी रूप से समय जटिलता ओ (एन)। जैसे-जैसे सूची बढ़ती है, संचालन की संख्या बढ़ती है। एक ऐसी सरणी की तुलना में जिसमें यादृच्छिक अभिगम होता है - किसी तत्व तक पहुंचने में निरंतर समय लगता है।
बस!
लिंक्ड सूचियाँ सरणियों के महान विकल्प हैं जब शुरुआत में प्रविष्टि और विलोपन प्रमुख क्रियाएं हैं। एरे को अनुक्रमित किया जाता है, जबकि लिंक की गई सूची नहीं होती है। लिंक की गई सूचियाँ भी मूलभूत डेटा संरचना हैं, जिनके ढेर और कतारें निर्मित हैं, जिनकी मैं बाद के लेख में चर्चा करूंगा। यदि आपने इसे यहाँ पर बना दिया है, तो आपके लिए यश और मुझे आशा है कि आपने अपनी प्रोग्रामिंग यात्रा के साथ-साथ थोड़ी डली सीख ली है!
