[संगीत बजाना] डौग लॉयड: ठीक है। तो अगर आप सिर्फ इतना है कि समाप्त हो गया है, तो अकेले-लिंक सूचियों खेद पर वीडियो मैं एक पर आप से दूर छोड़ दिया एक Cliffhanger का एक सा है। लेकिन मैं आप को समाप्त करने के लिए कर रहे हैं यहाँ खुश हूँ दोगुना-लिंक सूचियों की कहानी है। 

आप से याद करते हैं तो वीडियो है कि, हम बात की अकेले-लिंक्ड कैसे के बारे में सूचियों की हमारी क्षमता में भाग लेने करना जानकारी के साथ सौदा करने के लिए जहां तत्वों की संख्या या मदों की संख्या में एक सूची हो जाना या सिकुड़ कर सकते हैं। अब हम साथ सौदा कर सकते हैं ऐसा कुछ, जहां हम सरणियों के साथ इसके साथ सौदा नहीं कर सकता। 

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

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

जैसा कि मैंने कहा तो, हम सिर्फ जोड़ने के लिए है हमारे संरचना करने के लिए एक ही क्षेत्र इस धारणा definition-- एक पिछला सूचक की। एक अकेले लिंक्ड सूची के साथ तो, हम , मूल्य और अगला सूचक है इसलिए दोगुना-लिंक्ड सूची में बस गया है एक तरीके के रूप में अच्छी तरह से पीछे की ओर ले जाने के लिए। 

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

तो चलो एक नया नोड सम्मिलित जाने एक दोगुना-लिंक्ड सूची में। हम ऐसा करने के बारे में बात की थी के रूप में अच्छी तरह से सूचियों अकेले से जुड़े, लेकिन अतिरिक्त की एक जोड़ी है दोगुना से जुड़े सूचियों के साथ फैल जाती है। हम [रहे हैं? गुजर?] के सिर में यहाँ की सूची और कुछ मनमाना मूल्य, और हम नए सिर प्राप्त करना चाहते हैं इस समारोह की सूची से बाहर की। यह एक dllnode स्टार रिटर्न यही कारण है कि। तो कदम क्या हैं? वे फिर से, बहुत समान हैं, सूचियों अकेले से जुड़े करने के लिए एक अतिरिक्त अलावा के साथ। हम एक नए के लिए जगह का आवंटन करना चाहते हैं नोड और जांच में यह वैध है सुनिश्चित करने के लिए। हम उस नोड को भरने के लिए चाहते हैं जो कुछ भी जानकारी के साथ हम उस में डाल करना चाहते हैं। आखिरी बात यह है कि हम do-- करने की जरूरत है हम क्या करने की जरूरत अतिरिक्त बात है, rather-- पिछले सूचक ठीक करने के लिए है सूची के पुराने सिर की। याद रखें कि क्योंकि के दोगुना से जुड़े सूचियों, हम आगे बढ़ सकते हैं और backwards-- जो प्रत्येक नोड वास्तव में बताते हैं कि इसका मतलब है दो अन्य नोड्स के बजाय सिर्फ एक करने के लिए। और इसलिए हम ठीक करने की जरूरत सूची के पुराने सिर के नए प्रमुख के लिए पिछड़े बात करने के लिए कुछ था जो लिंक सूची, हम पहले करने की जरूरत नहीं थी। और पहले की तरह, हम सिर्फ एक वापसी सूची के नए प्रमुख के लिए सूचक। 

तो यहाँ एक सूची है। हम इस सूची में 12 सम्मिलित करना चाहते हैं। आरेख कि नोटिस थोड़ा अलग है। प्रत्येक नोड तीन fields-- शामिल डेटा, और लाल रंग में एक अगली सूचक, और नीले रंग में पिछले एक सूचक। कुछ नहीं, 15 नोड से पहले आता है इसलिए अपने पिछले सूचक रिक्त है। यह सूची की शुरुआत है। यह पहले कुछ भी नहीं है। और कुछ भी नहीं, 10 नोड के बाद आता है और इसलिए यह अगले सूचक के रूप में अच्छी तरह से अशक्त है। 

तो चलो इस सूची में 12 जोड़ दें। हम नोड के लिए [सुनाई] अंतरिक्ष की जरूरत है। हम इसके बारे में 12 के अंदर डाल दिया। और फिर, हम वास्तव में रहने की जरूरत है सावधान चेन तोड़ने के लिए नहीं। हम पुनर्व्यवस्थित करना चाहते हैं सही क्रम में संकेत दिए। और कभी कभी कि mean-- सकता है हम विशेष रूप से देखेंगे के रूप में delete-- के साथ हम कुछ की क्या ज़रूरत है कि बेमानी संकेत दिए, लेकिन यह ठीक है। 

इसलिए हम पहले क्या करना चाहते हैं? मैं सुझा होगा चीजों को आप शायद चाहिए ऐसा 12 के संकेत को भरने के लिए कर रहे हैं नोड आप किसी और को छूने से पहले। तो क्या 12 अगले करने के लिए बात करने के लिए जा रहा है? 15। क्या 12 से पहले आता है? कुछ भी नहीं। अब हम भर दिया है 12 में अतिरिक्त जानकारी इसलिए यह पिछले, अगले, और मूल्य है। 

अब हम कर सकते हैं 15-- इस अतिरिक्त हम about-- बात कर रहे थे कदम वापस 12 के लिए 15 बिंदु हो सकता है। और अब हम के सिर स्थानांतरित कर सकते हैं लिंक सूची भी 12 किया जाना है। तो यह करने के लिए बहुत इसी तरह की है कि हम क्या अकेले-लिंक्ड सूचियों के साथ क्या कर रहे थे, के अतिरिक्त कदम के लिए छोड़कर सूची के पुराने सिर को जोड़ने सूची के नए प्रमुख के लिए वापस। 

अब अंत में नष्ट करते हैं एक लिंक की गई सूची में से एक नोड। तो चलो हम हम कहते हैं कि कुछ अन्य समारोह है कि हम हटाना चाहते हैं एक नोड लग रहा है और वास्तव में करने के लिए हमें एक सूचक दिया है हम हटाना चाहते हैं नोड। हम भी कह need-- नहीं है सिर अभी भी विश्व स्तर पर घोषित किया जाता है। हम यहाँ सिर जरूरत नहीं है। सभी इस समारोह में क्या कर रहा है हम है है बिल्कुल नोड हम करने के लिए एक सूचक पाया से छुटकारा पाने के लिए चाहते हैं। के लिए इसे से छुटकारा मिलता है। इसके साथ एक बहुत आसान है सूचियों दोगुना से जुड़ा हुआ है। यह वास्तव में है First-- सिर्फ एक दो बातें। हम सिर्फ आसपास के ठीक करने की जरूरत नोड्स 'संकेत दिए कि वे पर छोड़ इतना है कि नोड हम हटाना चाहते हैं। और फिर हम उस नोड हटा सकते हैं। तो फिर, हम सिर्फ यहाँ के माध्यम से जा रहे हैं। हम जाहिरा तौर पर तय किया है कि हम नोड एक्स हटाना चाहते हैं और फिर, मैं क्या कर रहा हूँ way-- द्वारा here-- कर रही है एक के लिए एक सामान्य मामला है बीच में है कि नोड। के एक जोड़े हैं अतिरिक्त निरंतर कि आप आप हटा रहे हैं जब विचार करने की जरूरत सूची के बहुत शुरुआत या सूची के बहुत अंत। विशेष की एक जोड़ी है कोने मामलों वहाँ से निपटने के लिए। 

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

इसलिए हम अलग-थलग पड़ गए हैं एक्स एक्स नोड है हम सूची से हटाना चाहते हैं। हम क्या करें? सबसे पहले, हम पुनर्व्यवस्थित करने की जरूरत बाहर संकेत दिए। हम पुनर्व्यवस्थित करने की जरूरत 9 के अगले 13 से अधिक छोड़ करने के लिए और बिंदु 10-- जो हम तो बस क्या किया है। और हम भी करने की जरूरत है 10 के पिछले पुनर्व्यवस्थित बजाय 13 की ओर इशारा करते के 9 को इंगित करने के लिए। 

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

इसलिए हम 9 की अगली सूचक कह सकते हैं एक ही जगह पर बताते हैं कि तेरह का अगला सूचक अब ठीक बताते हैं। हम अंत में कर रहे हैं क्योंकि 13 से अधिक छोड़ना चाहते करने के लिए जा रहा है। इसलिए जहां भी 13 अंक अगले, आप नौ के बजाय वहां बात करना चाहते हैं। तो यह है कि वह है। और फिर जहाँ भी 13 अंक वापस करने के लिए, 13 से पहले जो भी आता है, हम बात करने के लिए 10 चाहते हैं कि बजाय 13 करने के लिए। आप का पालन करता है, तो अब, नोटिस तीर, हम 13 ड्रॉप कर सकते हैं वास्तव में किसी भी जानकारी को खोने के बिना। हम सूची की अखंडता रखा है आगे और पीछे दोनों घूम रहा है। और फिर हम बस की तरह कर सकते हैं का एक छोटा सा यह साफ एक साथ सूची खींच कर। तो हम पुन: व्यवस्थित दोनों तरफ संकेत दिए। और फिर हम एक्स मुक्त कर दिया 13 निहित है कि नोड, और हम श्रृंखला नहीं तोड़ा। इसलिए हम अच्छा किया। 

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

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

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

और हां एक खोजने की कोशिश किसी लिंक किए list-- में तत्व खोज important-- है यदि अब रैखिक समय लग सकता है। सूची लंबी हो जाता है, यह एक अतिरिक्त कदम ले सकता है सूची में हर एक तत्व में लिए आदेश के लिए हम क्या देख रहे हैं खोजने के लिए। तो व्यापार नापसंद नहीं है। एक समर्थक की एक सा है यहाँ और चुनाव तत्व। 

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

मैं डौग लॉयड हूँ। इस CS50 है।