क्या आप कभी जावास्क्रिप्ट में एक लिंक्ड सूची लागू करेंगे?

Question

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

कोई भी उदाहरण दे सकता है कि मैं जावास्क्रिप्ट में एक लिंक की गई सूची का उपयोग क्यों करना चाहता हूं?

Answer 1

टिप्पणी नोट के रूप में, यदि आप सूची से निरंतर समय सम्मिलन/हटाना चाहते हैं तो आप ऐसा करेंगे।

दो तरीके Array यथोचित लागू किया जा सकता है कि गैर-निरंतर सूचकांक को आबाद करने के लिए अनुमति देते हैं:

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

द्वारा, लागत अंत में सम्मिलित O(1) परिशोधित किया जा रहा है, लेकिन O(n) काम की कीलें किया साथ जब भी अंतर्निहित सी की क्षमता जैसे सरणी समाप्त हो गई है (या हैश लोड थ्रेसहोल्ड पार हो गया है) और एक पुनर्वितरण आवश्यक है।

यदि आप शुरुआत में या बीच में (और प्रश्न में सूचकांक उपयोग में है) डालें, तो आपके पास पहले से ही समान कार्य स्पाइक्स और नई समस्याएं हैं। नहीं, मौजूदा सूचकांक के लिए डेटा नहीं बदलता है। लेकिन जिस प्रविष्टि को आप मजबूर कर रहे हैं उसके ऊपर की सभी चाबियां बढ़ी हैं (वास्तव में या तार्किक रूप से)। यदि यह एक सादा सी-जैसे सरणी कार्यान्वयन है, तो यह ज्यादातर memmove (कचरा संग्रह की आवश्यकता मॉड्यूल और इसी तरह की है)। यदि यह हैश टेबल कार्यान्वयन है, तो आपको अनिवार्य रूप से प्रत्येक तत्व को पढ़ने की आवश्यकता है (उच्चतम सूचकांक से निम्नतम तक, जिसका मतलब है कि या तो कुंजी को सॉर्ट करना या मौजूदा लंबाई से नीचे प्रत्येक इंडेक्स को देखना, भले ही यह Array है), इसे पॉप आउट करें , और इसे एक महत्वपूर्ण मान के साथ दोबारा डालें जो एक उच्च है। एक बड़े Array के लिए, लागत बहुत अधिक हो सकती है। यह संभव है कि कुछ ब्राउज़रों में कार्यान्वयन कुछ "ऑफसेट" का उपयोग करके कुछ चालाक बकवास कर सकता है जो आंतरिक रूप से इंडेक्स 0 से पहले डालने के दौरान ऑफ़सेट से संबंधित नकारात्मक "कुंजी" का उपयोग करेगा, लेकिन यह सभी परिचालनों को और अधिक महंगा बना देगा shift/unshift सस्ता बनाने के लिए विनिमय करें।

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

• आप डालने या शुरुआत या अंत से हटाना चाहते हैं, तो यह निश्चित परिश्रम (एक आवंटन या आवंटन रद्द करने, और संदर्भ fixups है)
• आप पुनरावृत्ति और यात्रा की लागत से डालने/के रूप में तुम जाओ हटाने, एक तरफ रहे हैं, तो यह एक ही तय काम
• है अगर यह पता चला है कि ऑफसेट अपने ब्राउज़र के कार्यान्वयन में shift/unshift को लागू करने के लिए इस्तेमाल नहीं कर रहे हैं (उनके साथ, shift आमतौर पर सस्ता होगा, और unshift सस्ते होगा जब तक कि आपके पास unshift-और अधिक न हो की तुलना में आप shift एड है), तो आप निश्चित रूप से एक लिंक की गई सूची का उपयोग करने के लिए जब संभावित असीम आकार का एक फीफो कतार के साथ काम करना चाहेंगे

यह पूरी तरह संभव सभी ब्राउज़रों ऑफसेट का उपयोग करें (memmove या फिर से बचने के अनुकूलन करने के लिए है कुछ स्थितियों के तहत -किंग, हालांकि यह कभी-कभी realloc और memmove या स्मृति बर्बाद किए बिना रीहैशिंग से बच नहीं सकता है)। मुझे एक तरह से पता नहीं है कि प्रमुख ब्राउज़र क्या करते हैं, लेकिन यदि आप निरंतर प्रदर्शन के साथ पोर्टेबल कोड लिखने की कोशिश कर रहे हैं, तो शायद आप यह नहीं मानना ​​चाहते कि उन्होंने shift/unshift केस बनाने के लिए सामान्य प्रदर्शन का त्याग किया है विशाल Array एस के साथ तेज़ी से, उन्होंने अन्य सभी परिचालनों को तेज़ी से और shift/unshift माना होगा, केवल छोटे Array एस के साथ उपयोग किया जाएगा जहां लागत छोटी है।

Answer 2

@ noob में जरूरत मैं सुझाव है कि आप जावास्क्रिप्ट कचरा कलेक्टर के बारे में इस वीडियो को देखने: क्यों एक लिंक्ड सूची का उपयोग कर आप अपने कोड की गति पर बेहतर-अनाज नियंत्रण (दे सकते हैं ShadowRanger रूप https://www.youtube.com/watch?v=RWmzxyMf2cE

इसमें वे बताते हैं गहराई से चर्चा करता है) और अप्रत्याशित कचरा संग्रह मंदी को भी रोकता है। इसके अलावा इसे टॉक-ए-ए-समुद्री डाकू दिवस पर फिल्माया गया था। :)

Answer 3

मुझे लगता है कि कुछ कानूनी मामलों/कारणों से जुड़ा हुआ सूचियों को पसंद करते हैं देखते हैं:

कारण 1: दूसरों को पहले से ही बताया गया है, प्रविष्टि और हटाने के बाद ओ में तय प्रदर्शन (1) से जुड़ा हुआ सूचियों के लिए समय । यह आपकी समस्या के आधार पर एक महत्वपूर्ण लाभ हो सकता है।

कारण 2: आप लिंक की गई सूचियों वाली चीजें कर सकते हैं जिन्हें आप सरणी के साथ नहीं कर सकते हैं। यह एक लिंक्ड सूची की प्रकृति के कारण है -> प्रत्येक सूची प्रविष्टि को इसके अनुयायी के संदर्भ मिलते हैं (और पूर्ववर्ती यदि यह एक डबल लिंक्ड सूची है)।

example1:

तो अगर आप मदों की एक लिंक्ड सूची है cou एक "CurrentItem" एक चर में के लिए एक संदर्भ संग्रहीत कर सकती है। आप आइटम के पड़ोसियों का उपयोग करने की जरूरत है तुम सिर्फ लिख सकते हैं:

curItem.getNext(); 

या

curItem.getPrev(); 

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

myArray = []; 
myArray[10] = 'a'; 
myArray[20] = 'b'; 

आप स्थिति उस तरह में अपने आप को मिल जाए, शायद किसी लिंक किए गए IST बेहतर विकल्प है।

हालांकि, यदि आपको डेटा तक यादृच्छिक पहुंच की आवश्यकता है (जो अधिकतर मामलों में ऐसा लगता है उससे अधिक शायद ही कभी) तो आप लगभग हर बार सरणी के साथ जाते हैं।

Example2:

आप "विभाजन" 2 अलग-अलग सूचियों में अपनी सूची, यह भी संभव हे (1) समय होगा चाहते हैं। सरणी के साथ आपको स्लाइस का उपयोग करने की आवश्यकता होगी, जो अधिक अपूर्ण है। हालांकि, यह केवल एक मुद्दा है यदि आप बड़े डेटासेट के साथ काम करते हैं और अक्सर इस ऑपरेशन को निष्पादित करते हैं। 10 मिलियन तारों की सरणी के टुकड़े करने की 20 पुनरावृत्तियों ने मेरी मशीन पर लगभग 4 सेकंड का समय लिया, जबकि एक सूची को 2 में विभाजित करने से < 1 सेकंड लिया गया (आपको पहले से ही सूची तत्व का संदर्भ दिया गया है जहां आप अलगाव शुरू करना चाहते हैं बेशक!)।

निष्कर्ष:

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

Answer 4

यह array बनाम linkedlist की बहुत ही बुनियादी मतभेद के निर्भर करता है।

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