लिंक्ड लिस्ट का परिचय

निश्चित रूप से, यहां अपडेट किए गए नोट्स दिए गए हैं:

लिंक्ड लिस्ट का परिचय

• लिंक्ड लिस्ट कंप्यूटर विज्ञान में एक मूलभूत डेटा संरचना है।
• इनका उपयोग तत्वों के संग्रह को संग्रहीत करने के लिए किया जाता है।
• एरे के विपरीत, लिंक्ड लिस्ट तत्वों को सन्निहित मेमोरी स्थानों में संग्रहीत नहीं करती हैं।
• लिंक्ड लिस्ट में प्रत्येक तत्व, जिसे नोड कहा जाता है, में डेटा और क्रम में अगले नोड के लिए एक पॉइंटर (या लिंक) होता है।

बुनियादी अवधारणाएँ और शब्दावली

• नोड: एक लिंक्ड लिस्ट का एक बुनियादी घटक, जिसमें डेटा और अगले नोड का पॉइंटर होता है।
• डेटा: नोड में संग्रहीत वास्तविक जानकारी।
• पॉइंटर (अगला): लिस्ट में अगले नोड का संदर्भ। यह नल भी हो सकता है, जो लिस्ट के अंत को दर्शाता है।
• हेड: लिंक्ड लिस्ट का पहला नोड। यह लिस्ट के लिए प्रवेश बिंदु के रूप में कार्य करता है।
• टेल: लिंक्ड लिस्ट का अंतिम नोड, जिसका अगला पॉइंटर नल पर सेट है।

लिंक्ड लिस्ट के प्रकार

• सिंगल लिंक्ड लिस्ट: प्रत्येक नोड क्रम में केवल अगले नोड की ओर इशारा करता है। ट्रैवर्सल केवल एक दिशा में संभव है।
• डबल लिंक्ड लिस्ट: प्रत्येक नोड में अगले और पिछले दोनों नोड्स के पॉइंटर होते हैं। ट्रैवर्सल दोनों दिशाओं में संभव है।
• सर्कुलर लिंक्ड लिस्ट: अंतिम नोड पहले नोड की ओर वापस इशारा करता है, एक चक्र बनाता है। यह सिंगल या डबल लिंक्ड हो सकता है।

सिंगल लिंक्ड लिस्ट: विस्तृत स्पष्टीकरण

• संरचना: प्रत्येक नोड में डेटा और अगले नोड का पॉइंटर होता है। अंतिम नोड का पॉइंटर नल होता है।
• ट्रैवर्सल: हेड से शुरू करें और लिस्ट के अंत (नल पॉइंटर) तक अगले पॉइंटर्स का अनुसरण करें।
• सम्मिलन: लिस्ट में एक नया नोड जोड़ना। इसे लिस्ट की शुरुआत, अंत या बीच में किया जा सकता है।
• विलोपन: लिस्ट से एक नोड को हटाना, जिसमें आसन्न नोड्स के पॉइंटर्स को अपडेट करना शामिल है।

डबल लिंक्ड लिस्ट: विस्तृत स्पष्टीकरण

• संरचना: प्रत्येक नोड में डेटा, अगले नोड का पॉइंटर और पिछले नोड का पॉइंटर होता है।
• ट्रैवर्सल: आगे (अगले पॉइंटर्स का उपयोग करके) या पीछे (पिछले पॉइंटर्स का उपयोग करके) ट्रैवर्स कर सकते हैं।
• सम्मिलन: सिंगल लिंक्ड लिस्ट के समान लेकिन पिछले पॉइंटर्स को भी अपडेट करने की आवश्यकता होती है।
• विलोपन: आसन्न नोड्स के अगले और पिछले दोनों पॉइंटर्स को अपडेट करने की आवश्यकता होती है।
• लाभ: पीछे की ओर ट्रैवर्स करना और विलोपन करना आसान है, क्योंकि आपके पास पिछले नोड तक सीधी पहुंच है।

सर्कुलर लिंक्ड लिस्ट: विस्तृत स्पष्टीकरण

• संरचना: अंतिम नोड पहले नोड की ओर वापस इशारा करता है, एक चक्र बनाता है।
• ट्रैवर्सल: अनंत लूप से बचने के लिए सावधानीपूर्वक हैंडलिंग की आवश्यकता होती है।
• उपयोग के मामले: उन अनुप्रयोगों में उपयोगी जहां आपको तत्वों के माध्यम से बार-बार चक्र करने की आवश्यकता होती है।

लिंक्ड लिस्ट पर सामान्य संचालन

• सम्मिलन:
  • शुरुआत में: हेड को नए नोड की ओर इशारा करने के लिए अपडेट करें।
  • अंत में: अंतिम नोड पर ट्रैवर्स करें और उसके अगले पॉइंटर को अपडेट करें।
• बीच में: आसन्न नोड्स के अगले पॉइंटर्स को अपडेट करें।
• विलोपन:
  • पहले नोड को हटाना: हेड को अगले नोड पर अपडेट करें।
  • अंतिम नोड को हटाना: दूसरे से अंतिम नोड पर ट्रैवर्स करें और उसके अगले पॉइंटर को नल पर सेट करें।
  • एक मध्य नोड को हटाना: वर्तमान नोड को छोड़ने के लिए पिछले नोड के अगले पॉइंटर को अपडेट करें।
• खोज: लिस्ट को ट्रैवर्स करें और प्रत्येक नोड के डेटा की तुलना लक्षित मान से करें।

लिंक्ड लिस्ट के लाभ

• गतिशील आकार: लिंक्ड लिस्ट रनटाइम के दौरान बढ़ या सिकुड़ सकती हैं, फिक्स्ड आकार वाले एरे के विपरीत।
• कुशल सम्मिलन और विलोपन: लिस्ट के बीच में नोड्स को सम्मिलित करना या हटाना एरे की तुलना में अधिक कुशल है।
• मेमोरी आवंटन: नोड्स को गैर-सन्निहित मेमोरी स्थानों में संग्रहीत किया जा सकता है, जिससे मेमोरी का बेहतर उपयोग होता है।

लिंक्ड लिस्ट के नुकसान

• मेमोरी ओवरहेड: प्रत्येक नोड को पॉइंटर्स को संग्रहीत करने के लिए अतिरिक्त मेमोरी की आवश्यकता होती है।
• यादृच्छिक एक्सेस: लिंक्ड लिस्ट में एक तत्व तक पहुंचने के लिए हेड से ट्रैवर्सल की आवश्यकता होती है, जो बड़ी लिस्ट के लिए धीमा हो सकता है।
• कैश अक्षमता: गैर-सन्निहित मेमोरी आवंटन से खराब कैश उपयोग हो सकता है।

उपयोग के मामले

• स्टैक और कतारों का कार्यान्वयन: लिंक्ड लिस्ट का उपयोग इन अमूर्त डेटा प्रकारों को लागू करने के लिए किया जा सकता है।
  • गतिशील मेमोरी आवंटन: मेमोरी प्रबंधन प्रणालियों में उपयोग किया जाता है।
• बहुपदों का प्रतिनिधित्व करना: प्रत्येक नोड एक पद (गुणांक और घातांक) संग्रहीत कर सकता है।
  • हैश टेबल: टकराव समाधान के लिए उपयोग किया जाता है।
  • ग्राफ़ प्रतिनिधित्व: आसन्नता लिस्ट को अक्सर लिंक्ड लिस्ट का उपयोग करके लागू किया जाता है।

एरे के साथ तुलना

• एरे:
  • फिक्स्ड आकार।
  • सन्निहित मेमोरी आवंटन।
  • कुशल यादृच्छिक एक्सेस।
  • बीच में अक्षम सम्मिलन और विलोपन।
• लिंक्ड लिस्ट:
  • गतिशील आकार।
  • गैर-सन्निहित मेमोरी आवंटन।
  • अक्षम यादृच्छिक एक्सेस।
  • बीच में कुशल सम्मिलन और विलोपन।