लिंक्ड सूचियों में हेड नोड

Question

मुझे एक लिंक किए गए सूची डेटा संरचना में पहले नोड, या तथाकथित सिर की प्रकृति क्या है, यह समझने में समस्याएं हैं। एक लिंक्ड सूची में नोड्स होते हैं, और प्रत्येक नोड में कुछ डेटा और सूची में किसी अन्य नोड का लिंक होता है। लेकिन क्या पहला नोड एक नोड है जिसमें डेटा और दूसरा नोड का लिंक होता है? या इसमें नोड में केवल एक लिंक (और कोई डेटा नहीं) है? मैंने सोचा कि एक लिंक्ड सूची में पहले नोड में डेटा और दूसरे नोड के लिए एक लिंक है, लेकिन एक प्रारंभिक पुस्तक में यह समझाया गया है कि सिर एक नोड है लेकिन एक लिंक जो आपको पहले नोड में ले जाता है। उसी समय सिर नोड के प्रकार का एक चर है। यह इस तरह क्यों है? (यदि जावा मायने रखता है, तो मैं जावा में काम कर रहा हूं)। धन्यवाद।

Answer 1

आप इसे किसी भी तरह से कार्यान्वित कर सकते हैं। एक पहला नोड जिसमें कोई डेटा नहीं है और केवल एक लिंक है, हालांकि यह एक बहुत अजीब कार्यान्वयन होगा।

Answer 2

एक हेड नोड आमतौर पर किसी अन्य नोड की तरह होता है सिवाय इसके कि यह सूची की शुरुआत में तार्किक रूप से आता है, और कोई अन्य नोड्स इंगित करता है (जब तक कि आपके पास दोगुनी-लिंक्ड सूची न हो)।

चूंकि कोई अन्य नोड इंगित करता है, और आपको सूची की शुरुआत खोजने का एक आसान तरीका भी चाहिए, यह एक नोड को अलग पॉइंटर स्टोर करना आम है जो हेड नोड को इंगित करता है। यह पॉइंटर नोड-खुद नहीं है, सिर्फ एक पॉइंटर है।

Answer 3

इन्हें "डमी" हेडर नोड कहा जाता है, और वे आपको सामान्य कोड लिखने की अनुमति देते हैं जो खाली और खाली रिक्त सूचियों के लिए काम करता है।

नियमित रूप से, यदि आप अपनी सूची के अंत में Node डालना चाहते हैं, तो आपको दो मामलों की आवश्यकता है। यदि head शून्य है, तो यह इंगित करता है कि सूची खाली है, तो आप नए Node पर head सेट करेंगे। यदि head शून्य नहीं है, तो आप next पॉइंटर्स का पालन करते हैं जब तक कि आपके पास अंतिम Node न हो, और next पॉइंटर को नए Node पर सेट करें।

हालांकि, यदि आप एक डमी हेडर का उपयोग करते हैं, तो head कभी भी शून्य नहीं होगा। यह एक Node होगा जिसमें शून्य next पॉइंटर होगा, जिसे आप अपने नए Node पर इंगित कर सकते हैं, बस सूची में नोड्स होने पर आप कैसे होंगे।

Answer 4

यदि यह सी ++ में था, तो यह समझना आपके लिए आसान हो सकता है, लेकिन हेडर नोड अधिक संदर्भ है जिसका उपयोग आप पूरी सूची में प्रारंभिक पहुंच प्राप्त करने के लिए करते हैं। यह सूची में पहला "पूर्ण" नोड संदर्भित करता है जिसमें सूची के डेटा सेट के भीतर अपना डेटा आइटम और अगले नोड का संदर्भ होता है। यदि यह सी ++ था, तो एक नोड वास्तव में डेटा संरचना में "सूचक" होगा, जो कि कंपाइलर के लिए केवल स्मृति पता है। यदि आपके पास हेडर नोड नहीं था जो आपकी लिंक्ड-लिस्ट की ओर इशारा करता है, तो यह फिर भी "ईथर" में खो जाएगा, कभी भी फिर से एक्सेस नहीं किया जा सकता - जबकि अभी भी स्मृति में स्थान ले रहा है।

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

अवधारणा में, सरणी एक प्रकार की सूची होती है, जैसे लिंक-सूचियां भी एक प्रकार की सूची होती हैं। सरणी क्रम में अनुक्रमिक क्रम में रखी जाती है जबकि लिंक्ड सूचियां नहीं होती हैं। एक सरणी का सदस्य केवल अपने डेटा आइटम का संदर्भ देता है, लेकिन चूंकि सदस्यों को स्मृति में रखा जाता है, इसलिए आप उस डेटा आइटम के डेटा प्रकार के आकार से गुणा पूर्णांक जोड़कर संपूर्ण सरणी के संदर्भ में एक पूर्णांक मान जोड़कर उन्हें एक्सेस कर सकते हैं। यह इस तथ्य से जुड़ा हुआ सूचियों से अलग है कि लिंक्ड सूचियों को अनुक्रमिक क्रम में नहीं रखा गया है और इस प्रकार सूची बनाने के लिए एक और जटिल डेटा संरचना का उपयोग किया जाना चाहिए - यानी "नोड"।

लेकिन, चूंकि लिंक की गई सूची स्मृति में किसी भी प्रकार के क्रम में नहीं रखी गई है, इसलिए संकलक को इसके लिए डेटा का एक हिस्सा अलग करने की आवश्यकता नहीं है और इसीलिए इसकी लंबाई कितनी हो सकती है हर बार जब आप इसकी लंबाई बदलते हैं तो एक नया निर्माण करने के बिना। यह सरणी से अलग है क्योंकि सरणी की लंबाई स्थिर है। इसके अतिरिक्त, एक सरणी अपनी पहली सदस्य द्वारा संदर्भित है, वह यह है कि ("एक" का नाम एक सरणी के लिए) इस होगा "एक [0]" या समकक्ष "एक" अगर यह सी हालांकि थे, एक लिंक्ड सूची नहीं है इस तरह काम करें और यही कारण है कि पूरी चीज का संदर्भ देने के लिए आपके पास "हेडर" या "डमी" नोड है।

हेडर नोड के बारे में एक और बात यह है कि एक लिंक-सूची पर विभिन्न संचालन करते समय, आप सूची में अपना ऑपरेशन करने में मदद के लिए अपने "हेड नोड" में संरचना में समान नोड भी बना सकते हैं। एक नोड की तरह इसके बारे में

Answer 5

लगता है कि एक वस्तु जो एक चर "डाटा" मूल्य और अन्य चर "अगले" जो एक और नोड वस्तु की ओर इशारा करता एक लिंक बनाने के लिए धारण करने के लिए है। नीचे जावा क्लास देखें।

public class ListNode { 
private int data; 
private ListNode next = null; 

public ListNode() { 
    // TODO Auto-generated constructor stub 
} 
//constructor for creating a listNode 
public ListNode(int data){ 
    this.data = data; 
} 
/*below are setters and getters */ 
public void setData(int data){ 
    this.data = data; 
} 
public int getData(){ 
    return this.data; 
} 
public void setNext(ListNode next){ 
    this.next = next; 
} 
public ListNode getNext(){ 
    return this.next; 
} 
} 

और इस तरह मैं इसे लिंक करूंगा।

//create 3 list node objects 
    ListNode one = new ListNode(1); 
    ListNode two = new ListNode(2); 
    ListNode three = new ListNode(3); 

    one.setNext(two); 
    two.setNext(three); 

लेकिन ध्यान दें कि हम, अंत में एक ListNode जोड़ने शुरुआत या सूची में एक यादृच्छिक जगह पर की तरह किसी भी आगे हेरफेर के लिए सिर नोड जानना चाहते हैं।

एक प्रमुख नोड जहां सूची श्रृंखला शुरू कर दिया है से हमारे मामले में एक है।

यह साफ करता है :)

धन्यवाद Punith

Answer 6

एक @falmarri जवाब आशा है, आप इसे किसी भी तरह से लागू कर सकते हैं। हेड नोड सिंगल लिंक्ड सूची में किसी भी अन्य नोड के समान है। यह सिर्फ एक प्रारंभिक नोड है जिसके साथ हम बाकी की लिंक्ड सूची को पार कर सकते हैं। हम सिर को या तो नोड या पॉइंटर के रूप में कार्यान्वित कर सकते हैं।