सूची कार्यान्वयन: क्या लिंक्डलिस्ट वास्तव में इतनी खराब बनाम ऐरेलिस्ट और ट्रीलिस्ट करता है?

Question

Apache TreeList doc से लिया:

   get add insert iterate remove 
TreeList  3 5  1  2  1 
ArrayList  1 1  40  1  40 
LinkedList 5800 1  350  2  325 

यह पर चला जाता है कहने के लिए:

LinkedList शायद ही कभी एक है

निम्नलिखित रिश्तेदार प्रदर्शन आंकड़े इस वर्ग का संकेत कर रहे कार्यान्वयन की अच्छी पसंद है। TreeList लगभग हमेशा इसके लिए एक अच्छा प्रतिस्थापन है, हालांकि यह थोड़ा अधिक स्मृति का उपयोग करता है।

मेरे प्रश्न हैं:

• क्या, insertArrayListadd साथ है, और remove बार LinkedList कुचल? क्या हमें उम्मीद है कि एक के लिए, वास्तविक दुनिया सम्मिलन और हटाने के मामले बहुत ArrayList का पक्ष लेते हैं?

• क्या यह TreeList केवल आदरणीय LinkedList के ताबूत में नाखून डाल दिया है?

मैं समाप्त करने के लिए वे परिशोधित या ArrayList की बढ़ रही दर्द को नजरअंदाज कर दिया है, और ध्यान में एक LinkedList कि पहले से ही स्थित है में एक आइटम के लिए प्रविष्टि और हटाने बार नहीं लिया है परीक्षा रहा हूँ।

Answer 1

यहां महत्वपूर्ण बात यह है कि तीन सूची कार्यान्वयन में सम्मिलित/हटाए गए संचालन की जटिलता है। ArrayList में ओ (एन) मनमाने ढंग से सूचकांक के लिए समय डालें/हटाएं, लेकिन यह ओ (1) है यदि ऑपरेशन सूची के अंत में है। ArrayList में किसी भी स्थान के लिए ओ (1) पहुंच की सुविधा भी है। लिंक्डलिस्ट समान रूप से ओ (एन) है, लेकिन सूची (प्रारंभ और अंत) के अंत में संचालन के लिए ओ (1) है और ओ (एन) मनमानी पदों के लिए उपयोग है। ट्रीलिस्ट में किसी भी स्थिति में सभी परिचालनों के लिए ओ (लॉगन) जटिलता है।

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

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

Answer 2

यह इन संग्रहों के पीछे data structures के कारण है। ट्रीलिस्ट एक tree है, जो अपेक्षाकृत तेज़ पढ़ने, सम्मिलन, निष्कासन (सभी ओ (लॉग एन) के लिए अनुमति देता है)। डेटा संग्रहित करने के लिए ArrayList array का उपयोग करता है, इसलिए जब आप डालें या हटाते हैं, तो सरणी में प्रत्येक आइटम को ऊपर या नीचे स्थानांतरित किया जाना चाहिए (ओ (एन) सबसे खराब मामला)। Arrays के पास एक निश्चित आकार भी होता है, इसलिए यदि यह वर्तमान सरणी की क्षमता को बहता है, तो एक नया, बड़ा (आमतौर पर अंतिम आकार का आकार, न्यूनतम आकार में रखने के लिए) बनाया जाना चाहिए। लिंक्डलिस्ट का उपयोग किया गया ... linked list। एक लिंक्ड सूची में आमतौर पर सूची में पहले (और कभी-कभी अंतिम) तत्वों का संदर्भ होता है। फिर सूची में प्रत्येक तत्व सूची में अगले तत्व (एकल-लिंक्ड सूची के लिए) या अगले और पिछले तत्वों (एक डबल लिंक्ड सूची के लिए) का प्रतिबिंब है। इसके कारण, किसी विशिष्ट तत्व तक पहुंचने के लिए, आपको वहां जाने से पहले प्रत्येक तत्व के माध्यम से फिर से शुरू करना होगा (ओ (एन) सबसे खराब मामला)। विशिष्ट तत्वों को डालने या हटाने के दौरान, आपको उन्हें डालने या निकालने की स्थिति मिलनी चाहिए, जिसमें समय लगता है (ओ (एन) सबसे खराब मामला)। हालांकि शुरुआत या अंत में एक और तत्व जोड़ने के लिए बहुत कम लागत है (ओ (1))।

डेटा संरचनाओं पर और पूरी तरह से उपयोग किए जाने पर पूरी किताबें लिखी गई हैं, मैं अधिक मौलिक लोगों को पढ़ने की सलाह देता हूं।

Answer 3

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

एक बड़ी लिंक्डलिस्ट में जोड़ने/डालने/हटाने के लिए आपको सही जगह पर जाने के लिए नोड से नोड तक बहुत सारे hopping होगा।

यदि वे बढ़ते दर्द के साथ शुरू करने के लिए उचित आकार के ऐरेलिस्ट को कुछ भी नहीं करेंगे। यदि ArrayList छोटा है तो बढ़ती पीड़ा कोई फर्क नहीं पड़ता।

लिंक्डलिस्ट के लिए यदि ऑपरेशन सूची के सामने सभी हैं तो यह अंत में कम होने पर बहुत कम प्रभावित होगा।

आपको क्या करना चाहिए हमेशा इंटरफ़ेस का उपयोग करना है, उदाहरण के लिए: चर और पैरामीटर घोषित करते समय सूची में आप "नया लिंक्डलिस्ट();" "नई ArrayList();" और यह कोड देखने के लिए कोड को प्रोफाइल करें कि यह आपके विशिष्ट कोड में कैसा प्रदर्शन करता है।

नोड से नोड तक कूदने की गति की वजह से मैं हमेशा लिंक्डलिस्ट के बजाय ArrayList को डिफ़ॉल्ट करता हूं।

मुझे विश्वास है कि पेड़ की सूची दोनों की तुलना में काफी तेज होगी (यहां तक ​​कि कोड को देखे बिना)। पेड़ तेजी से डिजाइन किए गए हैं।

Answer 4

ऐरेलिस्ट के लिए, क्योंकि यह बार-बार किया जाता है, तो आप मूल रूप से उस लागत को नगण्य बना सकते हैं। यदि यह वास्तव में एक समस्या है, तो बस सरणी को शुरू करने के लिए बड़ा बनाएं।

यदि मेरे पास एक छोटी सूची है तो एक लिंकडलिस्ट का उपयोग करने के लिए समझदारी होती है क्योंकि उस बिंदु पर न्यूनतम लाभ होता है। यदि सूची लंबी होने जा रही है तो स्पष्ट रूप से एक वृक्षसूची अधिक समझ में आता है।

यदि मैं किसी सूची में यादृच्छिक पहुंच का एक बड़ा सौदा करने जा रहा हूं तो ArrayList अधिक समझ में आता है।

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

Answer 5

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

LinkedList::add(int index, E element) 
      Inserts the specified element at the specified position in this list. 

जो विधि वे आंकड़े प्राप्त करने के लिए इस्तेमाल होने लगते हैं, लेकिन

iterator.insert(E element) 

एक iterator या तो

public abstract ListIterator<E> listIterator(int index) 
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. 

के माध्यम से प्राप्त के साथ

या

public Iterator<E> iterator() 
Returns an iterator over the elements in this list (in proper sequence). 

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

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

पीएसएस। यही कारण है कि कहा, मैं इसलिए भी बने हुए हैं रहा हूँ

एक LinkedList में एक आइटम के लिए समाप्त करने के लिए वे परिशोधित है परीक्षा या ArrayList के बढ़ रही दर्द को नजरअंदाज कर दिया, और को ध्यान में रखा नहीं किया है प्रविष्टि और हटाने बार है कि पहले से ही स्थित है।

Answer 6

ध्यान दें कि ऐरेलिस्ट आमतौर पर लिंक्डलिस्ट से तेज़ है, भले ही आपका कोड केवल उन विधियों को कॉल करता है जो दोनों के लिए निरंतर समय हैं। उदाहरण के लिए, ArrayList.add() प्रतियों को एक वैरिएबल का अनुपालन करता है और जब कोई आकार बदलने की आवश्यकता नहीं होती है, तो काउंटर में वृद्धि होती है, जबकि LinkedList.add() को नोड भी बनाना चाहिए और एकाधिक पॉइंटर्स सेट करना होगा। इसके अलावा, लिंक्डलिस्ट नोड्स को अधिक मेमोरी की आवश्यकता होती है, जो आपके एप्लिकेशन को धीमा कर देती है, और कचरा संग्रह नोड्स से निपटना चाहिए।

आप जोड़ सकते हैं या सूची के दोनों छोर से तत्वों को दूर करने की जरूरत है, लेकिन रैंडम एक्सेस की आवश्यकता नहीं है, तो एक ArrayDeque, एक LinkedList से की तुलना में तेजी है, हालांकि यह 6.

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