लिंक्ड लिस्ट (Linked list) कॉन्सेप्ट को समझने से पहले, हम पहले देखते हैं कि लिंक्ड लिस्ट की आवश्यकता क्यों है।
यदि हम value को मेमोरी में स्टोर करना चाहते हैं, तो हमें एक मेमोरी मैनेजर की आवश्यकता होती है जो हर variable के लिए मेमोरी को मैनेज करे। उदाहरण के लिए, यदि हम integer प्रकार का एक variable बनाना चाहते हैं जैसे:
int x; उपरोक्त उदाहरण में, हमने integer प्रकार का एक variable ‘x’ बनाया है। जैसा कि हम जानते हैं कि integer variable 4 बाइट्स पर कब्जा कर लेता है, इसलिए ‘x’ variable integer को store करने के लिए 4 बाइट्स पर कब्जा कर लेगा।
मान लीजिए कि हम integer प्रकार की एक array बनाना चाहते हैं जैसे:
int x[3]; उपरोक्त उदाहरण में, हमने आकार 3 की एक array घोषित की है। जैसा कि हम जानते हैं, कि एक array के सभी मूल्यों को continous तरीके से संग्रहीत किया जाता है, इसलिए एक array के सभी तीन values sequential में संग्रहीत होते हैं। array द्वारा कब्जा कर लिया गया कुल मेमोरी स्पेस 3 * 4 = 12 बाइट्स होगा।
array का उपयोग करने की दो प्रमुख कमियां हैं: – Drawbacks of using array in Hindi
- हम उपरोक्त उदाहरण में 3 से अधिक elements सम्मिलित नहीं कर सकते क्योंकि 3 elements के लिए केवल 3 रिक्त स्थान आवंटित (allocate) किए गए हैं।
- एक array के मामले में, स्मृति का बहुत अधिक अपव्यय (wastage) हो सकता है। उदाहरण के लिए, यदि हम 50 आकार (size) की एक array घोषित करते हैं लेकिन हम एक array में केवल 10 elements सम्मिलित (insert) करते हैं। तो, इस मामले में, अन्य 40 तत्वों के लिए स्मृति स्थान बर्बाद हो जाएगा और किसी अन्य variable द्वारा उपयोग नहीं किया जा सकता क्योंकि यह पूरा स्थान एक array द्वारा कब्जा कर लिया गया है।
array में, हम संकलन-समय (compile time) पर निश्चित आकार (fixed size) प्रदान कर रहे हैं, जिसके कारण memory का westage होता है। इस समस्या का समाधान लिंक्ड लिस्ट (Linked List) का उपयोग करना है।
लिंक्ड लिस्ट क्या है? – What is Linked List in Hindi
एक लिंक्ड लिस्ट भी elements का संग्रह है, लेकिन तत्वों को लगातार स्थान (consecutive location) पर संग्रहीत नहीं किया जाता है।
मान लीजिए कि एक प्रोग्रामर ने integer value को संग्रहीत करने का अनुरोध किया है तो 4-बाइट मेमोरी ब्लॉक का आकार integer value को सौंपा गया है। प्रोग्रामर ने 3 और integer तत्वों को संग्रहीत करने के लिए एक और अनुरोध किया; फिर, इन तीन तत्वों को तीन अलग-अलग मेमोरी ब्लॉक सौंपे जाते हैं लेकिन मेमोरी ब्लॉक random places पर उपलब्ध होते हैं। तो, elements कैसे जुड़े हुए हैं?
ये तत्व एक तत्व के साथ एक अतिरिक्त जानकारी, यानी अगले तत्व का पता प्रदान करके एक दूसरे से जुड़े हुए हैं। Variable जो अगले element के एड्रेस को स्टोर करता है, पॉइंटर (Pointer) के रूप में जाना जाता है। इसलिए, हम यह निष्कर्ष निकालते हैं कि लिंक की गई लिस्ट में दो भाग होते हैं, अर्थात पहला डेटा तत्व है, और दूसरा सूचक (Pointer)है। सूचक चर 4 बाइट्स पर कब्जा कर लेगा जो अगले तत्व की ओर इशारा कर रहा है।
एक लिंक्ड लिस्ट को नोड्स (nodes) के संग्रह के रूप में भी परिभाषित किया जा सकता है जिसमें एक नोड दूसरे नोड से जुड़ा होता है, और नोड में दो भाग होते हैं, यानी, एक डेटा भाग (element) होता है और दूसरा पता भाग (pointer) होता है, जैसा कि में दिखाया गया है नीचे चित्र:
उपरोक्त आकृति में, हम देख सकते हैं कि प्रत्येक नोड में डेटा और अगले नोड का पता होता है। लिंक की गई लिस्ट के अंतिम नोड में पता भाग में NULL मान होता है।
हम लिंक्ड लिस्ट कैसे घोषित कर सकते हैं? – How can we declare the Linked list?
एक array की घोषणा बहुत सरल है क्योंकि यह एकल प्रकार (single type) की है। लेकिन लिंक की गई लिस्ट में दो भाग होते हैं, जो दो अलग-अलग प्रकार के होते हैं, यानी, एक साधारण variable है, और दूसरा pointer है।
एक लिंक्ड लिस्ट की संरचना को इस प्रकार परिभाषित किया जा सकता है:
उपरोक्त घोषणा में, हमने एक नोड के रूप में नामित एक संरचना को परिभाषित किया है जिसमें दो चर शामिल हैं: एक integer चर (डेटा), और दूसरा सूचक (pointer) है, जिसमें अगले नोड का पता होता है।
ऐरे पर एक लिंक्ड लिस्ट का उपयोग करने के लाभ – Advantages of using a Linked list over Array:
किसी array पर लिंक की गई लिस्ट का उपयोग करने के निम्नलिखित लाभ हैं:
- गतिशील डेटा संरचना – Dynamic data structure
- सम्मिलन और हटाना – Insertion and Deletion
- मेमोरी कुशल – Memory efficient
- कार्यान्वयन – Implementation
गतिशील डेटा संरचना – Dynamic data structure:
लिंक्ड लिस्ट का आकार निश्चित नहीं है क्योंकि यह हमारी आवश्यकताओं के अनुसार भिन्न हो सकता है।
सम्मिलन और हटाना – Insertion and Deletion:
लिंक की गई लिस्ट में insertion and deletion array की तुलना में आसान है क्योंकि किसी array में तत्व लगातार स्थान पर संग्रहीत होते हैं। इसके विपरीत, एक लिंक्ड लिस्ट के मामले में, तत्वों को एक यादृच्छिक (consecutive) स्थान पर संग्रहीत किया जाता है। शुरुआत से तत्वों को सम्मिलित करने और हटाने की जटिलता (complexity) लिंक की गई लिस्ट में O(1) है, जबकि एक array के मामले में, जटिलता O(n) होगी।
यदि हम किसी Array में element को इन्सर्ट या डिलीट करना चाहते हैं, तो हमें स्पेस बनाने के लिए एलिमेंट को शिफ्ट करना होगा। दूसरी ओर, Linked list में, हमें तत्वों को स्थानांतरित (shift) करने की आवश्यकता नहीं है। Linked list में, हमें बस नोड में पॉइंटर के पते को अपडेट करना होगा।
मेमोरी कुशल – Memory efficient
इसकी मेमोरी खपत कुशल है क्योंकि लिंक्ड लिस्ट का आकार हमारी आवश्यकताओं के अनुसार बढ़ या घट सकता है।
कार्यान्वयन – Implementation
स्टैक और क्यू दोनों को एक लिंक्ड लिस्ट का उपयोग करके लागू(implement) किया जा सकता है।
लिंक्ड लिस्ट के नुकसान Demerits of Linked List data structure in Hindi
लिंक्ड लिस्ट के नुकसान निम्नलिखित हैं:
स्मृति प्रयोग – Memory usage
ट्रेवेर्सल – Traversal
रिवर्स ट्रैवर्सिंग – Reverse traversing
स्मृति प्रयोग – Memory usage
Linked list में नोड array की तुलना में अधिक मेमोरी लेता है क्योंकि प्रत्येक नोड में दो प्रकार के चर (variable) होते हैं, अर्थात, एक साधारण चर (normal variable) है, और दूसरा एक सूचक चर (pointer) है जो मेमोरी में 4 बाइट्स रखता है।
ट्रेवेर्सल – Traversal
एक लिंक्ड लिस्ट में, ट्रैवर्सल आसान नहीं है। यदि हम किसी Linked list में element तक पहुंचना चाहते हैं, तो हम तत्व को यादृच्छिक (randomly) रूप से एक्सेस नहीं कर सकते हैं, लेकिन एक array के मामले में, हम इंडेक्स द्वारा तत्व को यादृच्छिक (random) रूप से एक्सेस कर सकते हैं। उदाहरण के लिए, यदि हम तीसरे नोड तक पहुंचना चाहते हैं, तो हमें इससे पहले सभी नोड्स को पार करना होगा। इसलिए, किसी विशेष नोड तक पहुंचने के लिए आवश्यक समय अधिक है।
रिवर्स ट्रैवर्सिंग – Reverse traversing
एक लिंक्ड लिस्ट में, बैकट्रैकिंग या रिवर्स ट्रैवर्सिंग मुश्किल है। एक डबल लिंक्ड लिस्ट में, यह आसान है लेकिन बैक पॉइंटर को स्टोर करने के लिए अधिक मेमोरी की आवश्यकता होती है।
लिंक्ड लिस्ट के अनुप्रयोग – Application of Linked List in Data Structure in Hindi
लिंक्ड लिस्ट के आवेदन नीचे दिए गए हैं:
- एक लिंक्ड लिस्ट की सहायता से, बहुपदों (polynomials) का प्रतिनिधित्व किया जा सकता है और साथ ही हम बहुपद (polynomials) पर संचालन (operations) भी कर सकते हैं। हम जानते हैं कि बहुपद (polynomials) पदों (terms) का एक संग्रह है जिसमें प्रत्येक पद में coefficient और power होती है। प्रत्येक पद के coefficient और power को एक linked list में अगले तत्व के लिए नोड और लिंक पॉइंटर पॉइंट के रूप में संग्रहीत किया जाता है, इसलिए लिंक की गई लिस्ट का उपयोग बहुपद (polynomial) को बनाने, हटाने और प्रदर्शित करने के लिए किया जा सकता है।
- वैज्ञानिक गणना (scientific computation) और संख्यात्मक विश्लेषण (umerical analysis) में एक विरल मैट्रिक्स (sparse matrix) का उपयोग किया जाता है। तो, विरल मैट्रिक्स का प्रतिनिधित्व करने के लिए एक लिंक्ड लिस्ट का उपयोग किया जाता है।
- छात्र के विवरण, कर्मचारी के विवरण या उत्पाद विवरण जैसे विभिन्न कार्यों को linked list का उपयोग किया जा सकता है क्योंकि linked list डेटा प्रकार (structure data) का उपयोग करती है जो विभिन्न डेटा प्रकार रख सकती है।
- एक लिंक्ड लिस्ट का उपयोग करके stack, queue, tree और विभिन्न अन्य डेटा संरचनाओं को लागू किया जा सकता है।
- ग्राफ़ edges and vertices का एक संग्रह है, और ग्राफ़ को adjacency matrix and adjacency list के रूप में दर्शाया जा सकता है। यदि हम ग्राफ को एक adjacency matrix के रूप में प्रस्तुत करना चाहते हैं, तो इसे एक array के रूप में लागू किया जा सकता है। यदि हम ग्राफ को एक adjacency list के रूप में प्रस्तुत करना चाहते हैं, तो इसे एक लिंक्ड लिस्ट के रूप में लागू किया जा सकता है।
- हैशिंग को लागू करने के लिए, हमें हैश टेबल की आवश्यकता होती है। हैश टेबल में ऐसी प्रविष्टियाँ (elements) हैं जो लिंक्ड लिस्ट का उपयोग करके कार्यान्वित (implement) की जाती हैं।
- Dynamic memory allocation को लागू करने के लिए एक लिंक्ड लिस्ट का उपयोग किया जा सकता है। dynamic memory allocation रन-टाइम पर किया गया जाता है।