लिंकडलिस्ट

Question

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

मैं शायद ही कभी उनके कोड में ArrayDeque का उपयोग कर किसी को देखता हूं। यदि कोई व्यक्ति ArrayDeque को कार्यान्वित करने में अधिक प्रकाश डालता है, तो यह सहायक होगा।

यदि मैं इसे समझता हूं, तो मैं इसका उपयोग करके अधिक आत्मविश्वास रखूंगा। मैं जेडीके कार्यान्वयन को स्पष्ट रूप से समझ नहीं पाया क्योंकि यह सिर और पूंछ संदर्भों का प्रबंधन करता है।

Answer 1

लिंक्ड संरचनाएं संभवतया प्रत्येक तत्व पर कैश मिस के साथ पुनरावृत्ति करने के लिए सबसे खराब संरचना हैं। इसके ऊपर वे रास्ता और अधिक स्मृति का उपभोग करते हैं।

यदि आपको दोनों सिरों को जोड़ने/निकालने की आवश्यकता है, तो एरेडडेक एक लिंक्ड सूची से काफी बेहतर है। प्रत्येक तत्व को यादृच्छिक पहुंच एक चक्रीय कतार के लिए ओ (1) भी है।

एक लिंक्ड सूची का एकमात्र बेहतर संचालन पुनरावृत्ति के दौरान वर्तमान तत्व को हटा रहा है।

Answer 2

ArrayDeque जावा 6 के साथ नया है, यही कारण है कि बहुत सारे कोड (विशेष रूप से प्रोजेक्ट जो पहले जावा संस्करणों के साथ संगत होने का प्रयास करते हैं) इसका उपयोग नहीं करते हैं।

कुछ मामलों में यह "बेहतर" है क्योंकि आप प्रत्येक आइटम को सम्मिलित करने के लिए नोड आवंटित नहीं कर रहे हैं; इसके बजाय सभी तत्वों को एक विशाल सरणी में संग्रहीत किया जाता है, जो आकार भरने पर इसका आकार बदलता है।

Answer 3

ArrayDeque<E> और LinkedList<E> हालांकि दोनों लागू किया Deque<E> इंटरफ़ेस, लेकिन ArrayDeque सरणी E[] वस्तु अपनी वस्तु के अंदर तत्वों रखने के लिए मूल रूप से उपयोग करता है, तो यह आम तौर पर सिर और पूंछ तत्वों का पता लगाने के लिए सूचकांक का उपयोग करता है ।

एक शब्द में, यह सिर्फ डेक (सभी डेक की विधि के साथ) की तरह काम करता है, हालांकि सरणी की डेटा संरचना का उपयोग करता है। इस संबंध में कि कौन सा बेहतर है, इस पर निर्भर करता है कि आप उन्हें कैसे और कहां उपयोग करते हैं।

Answer 4

मुझे विश्वास है कि LinkedList में मुख्य प्रदर्शन टोंटी तथ्य कार्यान्वयन एक नया लिंक्ड सूची नोड है, जो अनिवार्य शामिल JVM/ओएस आवंटित करता है जब भी आप, Deque के किसी भी समाप्त करने के लिए धक्का दृश्य के पीछे जो है, और है कि महंगा है। साथ ही, जब भी आप किसी भी अंत से पॉप करते हैं, LinkedList के आंतरिक नोड कचरा संग्रह के लिए योग्य बन जाते हैं और यह दृश्य के पीछे और अधिक काम करता है।

यदि यह ब्याज का हो सकता है, तो मेरे पास एक सबूत है कि ArrayList या ArrayDeque पर एक तत्व जोड़ना निरंतर स्थिर समय में चलता है; this देखें।

Answer 5

एरेडडेक में किसी तत्व को एक्सेस करना तत्वों तक पहुंचने के लिए ओ (1) के साथ लिंक्डलिस्ट के मुकाबले हमेशा तेज होता है। लिंक्ड सूची में, यह अंतिम तत्व खोजने के लिए ओ (एन) ले जाएगा।

ऐरेडेक मेमोरी कुशल है क्योंकि आपको लिंक की गई सूची के विपरीत अगले नोड का ट्रैक रखने की आवश्यकता नहीं है।

यहां तक ​​कि जावा प्रलेखन प्रति, यह उद्धृत किया गया है कि

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

Benchmarking इन दोनों में से साबित होता है कि ArrayDeque तेज़ है।

Answer 6

तत्व को एक्सेस करने के लिए ऐरेडेक के लिए समय जटिलता ओ (1) है और लिंकलिस्ट के लिए यह अंतिम तत्व तक पहुंचने के लिए ओ (एन) है। ArrayDeque थ्रेड सुरक्षित नहीं है इसलिए मैन्युअल रूप से सिंक्रनाइज़ेशन आवश्यक है ताकि आप इसे एकाधिक धागे के माध्यम से एक्सेस कर सकें और इसलिए वे तेज़ हैं।

Answer 7

सभी लोगों को एक LinkedList की आलोचना, हर दूसरे पुरुष की है कि जावा में List शायद ArrayList का उपयोग करता है का उपयोग किया गया है और एक LinkedList समय की सबसे बारे में सोचते हैं, क्योंकि वे जावा 6 से पहले किया गया है और क्योंकि उन हैं लोगों को एक के रूप में पढ़ाया जा रहा है ज्यादातर किताबों में शुरू करो।

लेकिन, इसका मतलब यह नहीं है कि, मैं अंधाधुंध LinkedList या ArrayDeque की तरफ ले जाऊंगा। यदि आप जानना चाहते हैं, तो नीचे दिए गए बेंचमार्क done by Brian पर एक नज़र डालें।

परीक्षण सेटअप मानती है:

• प्रत्येक परीक्षा वस्तु 500 वर्ण स्ट्रिंग है। प्रत्येक स्ट्रिंग स्मृति में एक अलग वस्तु है।
• परीक्षण सरणी का आकार परीक्षण के दौरान अलग-अलग होगा।
• प्रत्येक सरणी आकार/कतार-कार्यान्वयन संयोजन के लिए, 100 परीक्षण चलाए जाते हैं और औसत समय-प्रति-परीक्षण की गणना की जाती है।
• प्रत्येक परीक्षण में सभी वस्तुओं के साथ प्रत्येक कतार भरने, फिर उन सभी को हटाने के होते हैं।
• मिलीसेकंड के मामले में समय मापें।

परीक्षण परिणाम:

• 10.000 नीचे तत्वों, दोनों LinkedList और ArrayDeque परीक्षण एक उप 1 एमएस स्तर पर औसत है।
• चूंकि डेटा के सेट बड़े हो जाते हैं, इसलिए ऐरेडेक और लिंक्डलिस्ट औसत परीक्षण समय के बीच अंतर बड़ा हो जाता है।
• 9, 9 00,000 तत्वों के परीक्षण आकार पर, लिंक्डलिस्ट दृष्टिकोण ने ArrayDeque दृष्टिकोण से ~ 165% लंबा लिया।

ग्राफ़:

Takeaway:

• आपकी आवश्यकता 100 या 200 तत्वों भंडारण है, तो यह बहुत अधिक अंतर का उपयोग कर नहीं होगा कतारों में से कोई भी।
• हालांकि, अगर आप मोबाइल पर विकसित कर रहे हैं, तो आप अधिकतम क्षमता उस सूची सख्त स्मृति बाधा की वजह से होने के लिए आवश्यक हो सकता है की एक अच्छी अनुमान के साथ एक ArrayList या ArrayDeque उपयोग कर सकते हैं।
• कोड का एक बहुत मौजूद है, जब एक ArrayDeque उपयोग करने के लिए विशेष रूप से, क्योंकि यह List इंटरफ़ेस को लागू नहीं करता है तय करने का उपयोग कर एक LinkedList इसलिए सावधानी से चलने लिखा (मुझे लगता है कि काफी बड़ा कारण नहीं है)। हो सकता है कि आपका कोडबेस सूची इंटरफ़ेस से बड़े पैमाने पर बात करता है, शायद आप और ArrayDeque के साथ कूदने का निर्णय लेते हैं। आंतरिक कार्यान्वयन के लिए इसका उपयोग करना एक अच्छा विचार हो सकता है ...