[Powered by Google Translate] प्रोग्रामिंग में, हम अक्सर मूल्यों की सूची का प्रतिनिधित्व करने की जरूरत है, इस तरह के एक खंड में छात्रों के नाम के रूप में या नवीनतम प्रश्नोत्तरी पर अपने स्कोर. 

सी भाषा में घोषणा की, arrays इस्तेमाल किया जा सकता है सूची की दुकान. यह आसान है एक सूची के तत्वों की गणना एक सरणी में संग्रहीत किया जाता है, और अगर आप का उपयोग करने की आवश्यकता है या ith सूची तत्व को संशोधित कुछ मनमाने ढंग से सूचकांक के लिए मैं, कि लगातार समय में किया जा सकता है, arrays लेकिन नुकसान भी है. 

जब हम उन्हें घोषित, हम कहने के लिए की आवश्यकता हो ऊपर सामने कितना बड़ा वे कर रहे हैं, कि है, वे कितने तत्वों स्टोर कर सकते हैं और कितना बड़ा इन तत्वों रहे हैं, जो अपने प्रकार से निर्धारित होता है. उदाहरण के लिए, int आगमन (10) 10 वस्तुओं की दुकान कर सकते हैं कि एक int के आकार के होते हैं. 

हम घोषणा के बाद एक सरणी के आकार को बदल नहीं सकते. हम एक नई सरणी बनाने के लिए है अगर हम और अधिक तत्वों को संग्रहीत करना चाहते हैं. कारण इस सीमा मौजूद है कि हमारे कार्यक्रम पूरे सरणी भंडार स्मृति का एक सन्निहित हिस्सा के रूप में. कहते हैं इस बफर जहां हम हमारे सरणी में संग्रहीत है. वहाँ अन्य चर हो सकता है सही सरणी के लिए बगल में स्थित स्मृति में है, तो हम नहीं कर सकते बस सरणी बड़ा बनाने के लिए. 

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

यहाँ पूर्णांकों की एक बहुत ही सरल लिंक सूची के लिए कुछ सी कोड है. आप देख सकते हैं कि हम प्रत्येक नोड का प्रतिनिधित्व किया है जिसमें 2 बातें एक struct के रूप में सूची में, स्टोर करने के लिए पूर्णांक 'वैल' कहा जाता है और सूची में अगले नोड के लिए एक कड़ी जो हम एक बुलाया सूचक के रूप में प्रतिनिधित्व करते हैं 'अगले.' इस तरह, हम पूरी सूची को ट्रैक कर सकते हैं सिर्फ 1 नोड के लिए एक ही सूचक के साथ, और फिर हम अगले संकेत का पालन कर सकते हैं 2 नोड के लिए, 3 नोड के लिए, 4 नोड के लिए, और इतने पर, जब तक हम सूची के अंत करने के लिए मिलता है. 

आप 1 लाभ यह है देखने में सक्षम हो सकता है स्थैतिक सरणी संरचना पर एक लिंक सूची के साथ, हम स्मृति का एक बड़ा हिस्सा पूरी तरह जरूरत नहीं है. सूची के 1 नोड स्मृति में इस स्थान पर रह सकता है, और 2 नोड यहाँ पर सभी तरह का हो सकता है. हम सभी नोड्स के लिए कोई फर्क नहीं पड़ता कि वे कहाँ स्मृति में कर सकते हैं, क्योंकि 1 नोड में शुरू, प्रत्येक नोड अगले सूचक वास्तव में हमें बताता जहां अगले जाना. 

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

उदाहरण के लिए, अगर हम करने के लिए बीच में एक नोड जगह चाहता था सूची के 2 और 3 नोड्स,  हम 2 या 3 नोड्स सब पर स्थानांतरित करने के लिए नहीं होता. हम कहते हैं कि हम इस लाल नोड डालने रहे हैं. सब हम करना चाहते हैं नए नोड अगले सूचक सेट कर दिया जाता है 3 नोड को इंगित करने के लिए और फिर अगले 2 नोड सूचक rewire हमारे नए नोड को इंगित. तो, हम मक्खी पर हमारी सूची का आकार बदल सकते हैं के बाद से हमारे कंप्यूटर अनुक्रमण पर भरोसा नहीं करता, बल्कि संकेत का उपयोग करने के लिए उन्हें स्टोर जोड़ने पर. 

हालांकि, एक नुकसान से जुड़े सूची है कि, एक स्थिर सरणी के विपरीत, कंप्यूटर सिर्फ सूची के बीच करने के लिए कूद नहीं कर सकता. चूंकि कंप्यूटर लिंक की गई सूची में प्रत्येक नोड पर जाएँ अगले एक करने के लिए मिलता है, यह अब लेने के लिए एक विशेष नोड को खोजने के लिए जा रहा है यह एक सरणी में से. पार पूरी सूची समय लेता है आनुपातिक सूची की लंबाई या O (n) उपगामी संकेतन में. औसत पर, किसी भी नोड तक पहुँचने भी समय लगता है पता करने के लिए आनुपातिक है. 

अब, हम वास्तव में कुछ कोड लिखने कि लिंक सूचियों के साथ काम करता है. हम कहते हैं कि हम पूर्णांकों की एक लिंक सूची चाहते हैं. हम हमारी सूची में फिर से एक नोड का प्रतिनिधित्व कर सकते हैं 2 क्षेत्रों के साथ एक struct के रूप में, एक पूर्णांक 'वैल' नामक मूल्य और सूची के अगले नोड के लिए एक अगली सूचक. खैर, काफी सरल लगता है. 

हम कहते हैं कि हम करने के लिए एक समारोह लिखने के लिए चाहते हैं जो बहती है और सूची से बाहर प्रिंट मूल्य सूची के अंतिम नोड में संग्रहीत. खैर, इसका मतलब है कि हम सूची में सभी नोड्स पार की आवश्यकता होगी पिछले एक मिल जाए, लेकिन जब से हम नहीं जोड़ रहे हैं या कुछ भी को हटाने, हम बदलने के लिए नहीं करना चाहती सूची में अगले संकेत की आंतरिक संरचना. 

तो, हम एक सूचक चंक्रमण के लिए विशेष रूप से की आवश्यकता होगी जिसे हम 'क्रॉलर.' फोन करता हूँ यह सूची के सभी तत्वों के माध्यम से क्रॉल जाएगा अगले संकेत की श्रृंखला के बाद. हम सभी संग्रहीत है 1 नोड के लिए एक सूचक है, या सूची के 'सर'. 1 नोड के लिए प्रमुख अंक. यह सूचक नोड प्रकार का है. 

सूची में वास्तविक 1 नोड प्राप्त करने के लिए, हम भिन्नता यह सूचक है, लेकिन इससे पहले कि हम यह भिन्नता कर सकते हैं, हम करने के लिए जांच की जरूरत है अगर सूचक अशक्त 1 है. यदि यह रिक्त है, सूची खाली है, और हम एक संदेश है कि, क्योंकि सूची खाली है प्रिंट चाहिए, वहाँ कोई अंतिम नोड है. लेकिन, हम कहते हैं कि सूची खाली नहीं है. यदि ऐसा नहीं है, तो हम पूरी सूची के माध्यम से क्रॉल चाहिए जब तक हम सूची में अंतिम नोड मिल, और हम कैसे बता सकते हैं अगर हम सूची में अंतिम नोड में देख रहे हैं? 

खैर, अगर एक नोड अगले सूचक अशक्त है, हम जानते हैं कि हम अंत में कर रहे हैं के बाद से पिछले अगले सूचक सूची में कोई अगले नोड के लिए बिंदु होगा. यह अच्छा अभ्यास है हमेशा पिछले नोड अगले अशक्त initialized सूचक रखने एक मानकीकृत संपत्ति है जो हमें सचेतक जब हम सूची के अंत तक पहुँच है. 

तो, अगर क्रॉलर → अगले रिक्त है, याद है कि तीर वाक्यविन्यास dereferencing के लिए एक शॉर्टकट है एक struct के लिए एक सूचक है, तब तक पहुँचने अपनी अगली अजीब के बराबर क्षेत्र: (क्रॉलर *) अगले. एक बार जब हम पिछले नोड पाया है, हम क्रॉलर → वैल प्रिंट चाहते हैं, वर्तमान नोड में मूल्य हम जानते हैं जो पिछले एक है. अन्यथा, अगर हम अभी तक सूची में अंतिम नोड में नहीं कर रहे हैं, हम सूची में अगले नोड के लिए आगे बढ़ना है और जांच अगर है कि पिछले एक है. ऐसा करने के लिए, हम सिर्फ हमारे क्रॉलर सूचक सेट लिए वर्तमान नोड के अगले मान बिंदु, कि है, सूची में अगले नोड. इस सेटिंग के द्वारा किया जाता है क्रॉलर = क्रॉलर अगला →. तो फिर हम उदाहरण के लिए एक पाश के साथ इस प्रक्रिया को दोहराने के लिए, जब तक हम पिछले नोड लगता है. तो, उदाहरण के लिए, अगर क्रॉलर सिर की ओर इशारा करते हुए किया गया था, हम क्रॉलर सेट क्रॉलर → अगले बात, जो 1 नोड के अगले क्षेत्र के रूप में एक ही है. तो, अब हमारे क्रॉलर 2 नोड को इशारा कर रहा है, और, फिर से, हम एक पाश के साथ यह दोहरा, जब तक हम पिछले नोड पाया है, कि है, नोड अगले सूचक अशक्त करने के लिए जहां इशारा कर रहा है. और वहाँ हम यह है, हम पिछले नोड सूची में पाया है, और अपने मूल्य मुद्रित, हम सिर्फ क्रॉलर → वैल का उपयोग करें. 

Traversing इतना बुरा नहीं है, लेकिन क्या डालने के बारे में? आओ हम कहते हैं कि हम 4 की स्थिति में एक पूर्णांक सम्मिलित करना चाहते हैं एक पूर्णांक सूची में. कि वर्तमान 3 और 4 नोड्स के बीच है. फिर, हम सूची में सिर्फ पार 3 तत्व है, एक के बाद हम डालने रहे हैं मिलता है. तो, हम एक क्रॉलर संकेतक को फिर से बनाने के लिए सूची को पार करने के लिए, अगर हमारे सिर सूचक अशक्त है, और अगर ऐसा नहीं है, सिर नोड में हमारे क्रॉलर सूचक बिंदु. तो, हम 1 तत्व पर कर रहे हैं. हम आगे 2 अधिक तत्वों को जाने से पहले हम सम्मिलित कर सकते हैं, तो हम एक पाश के लिए उपयोग कर सकते हैं int i = 1; i <3, मैं + + और लूप के प्रत्येक चलना में, 1 नोड द्वारा हमारे क्रॉलर सूचक आगे अग्रिम द्वारा जाँच अगर वर्तमान नोड अगले क्षेत्र रिक्त है, और अगर ऐसा नहीं है, अगले नोड के लिए हमारे क्रॉलर संकेतक चाल यह वर्तमान नोड अगले सूचक के लिए बराबर की स्थापना से. तो, के बाद से हमारे पाश के लिए क्या करना है कि कहते हैं दो बार, हम 3 नोड पहुँच गए हैं, और एक बार हमारे क्रॉलर सूचक नोड के बाद तक पहुँच गया है जो हम करने के लिए हमारी नई पूर्णांक सम्मिलित करना चाहते हैं, हम वास्तव में कैसे डालने करते हैं? 

खैर, हमारे नए पूर्णांक सूची में डाला जा सकता है अपने स्वयं के नोड struct के भाग के रूप में, क्योंकि यह वास्तव में नोड्स के एक दृश्य है. तो, चलो नोड के लिए एक नया सूचक 'new_node,' कहा जाता है और इसे स्थापित करने के लिए स्मृति का कहना है कि हम अब आवंटित नोड खुद के लिए ढेर पर, और हम कितना स्मृति आवंटित की जरूरत है? खैर, एक नोड के आकार, और हम पूर्णांक है कि हम सम्मिलित करना चाहते करने के लिए अपने वैल क्षेत्र स्थापित करना चाहते हैं. चलो कहना है, 6. अब, नोड हमारे पूर्णांक मान शामिल हैं. यह भी अच्छा अभ्यास करने के लिए नए नोड अगले क्षेत्र इनिशियलाइज़ को अशक्त बिंदु, लेकिन अब क्या? 

हम सूची की आंतरिक संरचना को बदलने के लिए है और अगले मौजूदा सूची में निहित संकेत 3 और 4 नोड्स. चूंकि अगले संकेत सूची के क्रम का निर्धारण करने के लिए, और जब से हम हमारे नए नोड डालने रहे हैं सही सूची के बीच में, यह थोड़ा मुश्किल हो सकता है. इस वजह से, याद है, हमारे कंप्यूटर सूची में केवल नोड्स के स्थान जानता अगले पिछले नोड्स में संग्रहीत संकेत की वजह से. तो, अगर हम कभी भी इन स्थानों में से किसी का ट्रैक खो दिया है, हमारी सूची में अगले संकेत की बदलती करके कहते हैं, उदाहरण के लिए कहते हैं, हम बदल 3 नोड अगले क्षेत्र यहाँ पर कुछ नोड को इंगित. हम भाग्य से बाहर हो सकता है, क्योंकि हम नहीं चाहते जहां सूची के बाकी खोजने के लिए किसी भी विचार है, और जाहिर है कि वास्तव में बुरा है. तो, हम वास्तव में आदेश के बारे में सावधान रहना होगा जिसमें हम प्रविष्टि के दौरान हमारी अगली संकेत हेरफेर. 

तो, इस सरल, चलो का कहना है कि हमारे 1 4 नोड्स कर रहे हैं ए, बी, सी, और डी संकेत के श्रृंखला का प्रतिनिधित्व तीर के साथ कहा जाता है, कि नोड्स कनेक्ट. तो, हम हमारे नए नोड डालने की जरूरत है नोड्स सी और डी के बीच में यह यह सही क्रम में करने के लिए महत्वपूर्ण है, और मैं तुम्हें दिखाता हूँ क्यों. 

चलो गलत रास्ते पर यह पहली बार ऐसा देखने. अरे, हम जानते नए नोड सी के बाद सही आ गया है, तो चलो सी अगले सूचक सेट करने के लिए new_node बिंदु. सब ठीक है, ठीक लगता है, हम अभी तक अब तक खत्म कर दिया है विकास के लिए नए नोड अगले सूचक बिंदु बना रही है, लेकिन रुकिए, कैसे हम कि कर सकते हैं? केवल एक चीज है कि हमें बताओ जहां विकास था सकता है, अगले सूचक पहले सी में संग्रहीत, लेकिन हम सिर्फ इतना है कि सूचक rewrote नए नोड को इंगित करने के लिए, तो हम अब कोई सुराग जहां विकास स्मृति में है, और हम सूची के बाकी खो दिया है. सभी में अच्छा नहीं है. 

तो, हम कैसे यह सही है? पहला, नए नोड डी. में अगले सूचक बिंदु अब, दोनों नए नोड और सी अगले संकेत उसी नोड, डी की ओर इशारा करते हुए कर रहे हैं, लेकिन वह ठीक है. अब हम सी नई नोड पर अगले सूचक बात कर सकते हैं. तो, हम किसी भी डेटा को खोने के बिना यह किया है. कोड में, सी वर्तमान नोड कि चंक्रमण सूचक क्रॉलर इशारा कर रहा है, और विकास नोड वर्तमान नोड अगले क्षेत्र द्वारा की ओर इशारा द्वारा प्रतिनिधित्व किया है, या क्रॉलर → अगले. तो, हम 1 नए नोड अगले सूचक सेट क्रॉलर → अगले बात है, उसी तरह हम कहा new_node अगले सूचक चाहिए चित्रण में विकास के लिए इशारा करते हैं. तो, हम वर्तमान नोड अगले सूचक सेट कर सकते हैं हमारे नए नोड के लिए, बस के रूप में हम करने के लिए बात करने के लिए सी ड्राइंग में new_node इंतजार करना पड़ा. अब सब कुछ क्रम में है, और हम खोना नहीं था किसी भी डेटा का ट्रैक, और हम सिर्फ करने में सक्षम थे सूची के बीच में हमारे नए नोड छड़ी पूरी बात पुनर्निर्माण या यहां तक ​​कि किसी भी तत्व स्थानांतरण के बिना जिस तरह से हम एक निश्चित - लम्बाई सरणी के साथ होता था. 

तो, लिंक सूचियों एक बुनियादी है, लेकिन महत्वपूर्ण, गतिशील डेटा संरचना जो दोनों के फायदे और नुकसान arrays और अन्य डेटा संरचनाओं की तुलना में, और के रूप में अक्सर कंप्यूटर विज्ञान में मामला है, यह जानना महत्वपूर्ण है कि जब प्रत्येक उपकरण का उपयोग करने के लिए, ताकि आप सही काम के लिए सही उपकरण चुन सकते हैं. 

अधिक अभ्यास के लिए, कार्य लिखने की कोशिश एक लिंक सूची से नोड्स नष्ट - जिस क्रम में आप को पुनर्व्यवस्थित करने के बारे में सावधान रहने की याद अपने अगले संकेत करने के लिए सुनिश्चित करें कि आप अपनी सूची का एक हिस्सा खोना नहीं है - या एक समारोह के लिए एक लिंक सूची में नोड्स गिनती या एक मजाक, एक लिंक सूची में नोड्स के सभी के आदेश रिवर्स. 

मेरा नाम जैक्सन STEINKAMP है, इस CS50 है.