collections - Java में ArrayList पर LinkedList का उपयोग कब करें?




linked-list (25)

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

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

ArrayList प्रदर्शन के लिए केवल एक बेहतर विकल्प है यदि प्रदर्शन से आपका मतलब है थ्रूपुट है और आप विलंबता को अनदेखा कर सकते हैं। मेरे काम में मेरे अनुभव में मैं सबसे बुरी स्थिति विलंबता को नजरअंदाज नहीं कर सकता।

मैं हमेशा उपयोग करने के लिए हमेशा एक रहा हूं:

List<String> names = new ArrayList<>();

मैं इंटरफ़ेस का उपयोग पोर्टेबिलिटी के प्रकार के नाम के रूप में करता हूं, ताकि जब मैं इन जैसे प्रश्न पूछूं तो मैं अपना कोड दोबारा कर सकता हूं।

LinkedList को ArrayList और इसके विपरीत उपयोग कब किया जाना चाहिए?


इस प्रकार, किसी ने भी इन सूचियों में से प्रत्येक के स्मृति पदचिह्न को संबोधित नहीं किया है, इसके अलावा आम सहमति है कि एक LinkedList एक LinkedList की तुलना में "बहुत अधिक" है, इसलिए मैंने यह दिखाने के लिए कुछ संख्या क्रंचिंग की है कि एन सूक्ष्म संदर्भों के लिए दोनों सूचियां कितनी हैं ।

चूंकि संदर्भ उनके रिश्तेदार सिस्टम पर 32 या 64 बिट्स (यहां तक ​​कि जब भी शून्य) हैं, इसलिए मैंने 32 और 64 बिट LinkedLists और ArrayLists लिए डेटा के 4 सेट शामिल किए हैं।

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

नोट 2: (धन्यवाद BeeOnRope) संपीड़ित ओप्स अब मध्य जेडीके 6 और ऊपर से डिफ़ॉल्ट है, 64-बिट मशीनों के लिए नीचे दिए गए मान मूल रूप से अपने 32-बिट समकक्षों से मेल खाते हैं, बशर्ते कि आप निश्चित रूप से इसे बंद कर दें।

नतीजा स्पष्ट रूप से दिखाता है कि LinkedList मुकाबले बहुत अधिक है, खासकर बहुत ही उच्च तत्व गणना के साथ। अगर स्मृति एक कारक है, तो लिंक्डलिस्ट से स्पष्ट हो जाएं।

मेरे द्वारा उपयोग किए जाने वाले सूत्रों का पालन करें, अगर मुझे कुछ गलत किया गया है तो मुझे बताएं और मैं इसे ठीक कर दूंगा। 'बी' या तो 32 या 64 बिट सिस्टम के लिए 4 या 8 है, और 'एन' तत्वों की संख्या है। ध्यान दें कि मोड का कारण यह है कि जावा में सभी ऑब्जेक्ट्स 8 बाइट्स स्पेस का एक से अधिक हिस्सा लेते हैं चाहे यह सब इस्तेमाल किया गया हो या नहीं।

ArrayList :

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList :

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

1) अंतर्निहित डेटा संरचना

ArrayList और LinkedList के बीच पहला अंतर इस तथ्य के साथ आता है कि ऐरेलिस्ट को ऐरे द्वारा समर्थित किया गया है जबकि लिंक्डलिस्ट को लिंक्डलिस्ट द्वारा समर्थित किया गया है। इससे प्रदर्शन में और अंतर आएगा।

2) लिंक्डलिस्ट लागू डेक

ArrayList और LinkedList के बीच एक और अंतर यह है कि सूची इंटरफ़ेस के अलावा, लिंक्डलिस्ट भी डेक इंटरफ़ेस लागू करता है, जो पहले () और मतदान () और कई अन्य डेक फ़ंक्शंस के लिए पहले आउट ऑपरेशंस में पहला प्रदान करता है। 3) ArrayList में तत्व जोड़ना ArrayList में तत्व जोड़ना ओ (1) ऑपरेशन है यदि यह ऐरे के पुनः आकार को ट्रिगर नहीं करता है, इस स्थिति में यह ओ (लॉग (एन)) बन जाता है, दूसरी ओर, एक तत्व को जोड़ना लिंक्डलिस्ट ओ (1) ऑपरेशन है, क्योंकि इसे किसी भी नेविगेशन की आवश्यकता नहीं है।

4) एक स्थिति से एक तत्व को हटा रहा है

किसी विशेष इंडेक्स से तत्व को निकालने के लिए जैसे कि निकालने (इंडेक्स) को कॉल करके, ऐरेलिस्ट एक कॉपी ऑपरेशन करता है जो इसे ओ (एन) के करीब बनाता है जबकि लिंक्डलिस्ट को उस बिंदु पर जाने की आवश्यकता होती है जो इसे ओ (एन / 2) बनाता है। , क्योंकि यह निकटता के आधार पर किसी भी दिशा से पार हो सकता है।

5) ArrayList या LinkedList पर Iterating

Iteration LinkedList और ArrayList दोनों के लिए O (n) ऑपरेशन है जहां n एक तत्व है।

6) एक स्थिति से तत्व पुनर्प्राप्त

Get (अनुक्रमणिका) ऑपरेशन O (1) है ArrayList में जबकि ओ (एन / 2) लिंक्डलिस्ट में, क्योंकि इसे उस प्रविष्टि तक पार करने की आवश्यकता है। हालांकि, बिग ओ नोटेशन ओ (एन / 2) में सिर्फ ओ (एन) है क्योंकि हम वहां स्थिरांक को अनदेखा करते हैं।

7) मेमोरी

लिंक्डलिस्ट एक रैपर ऑब्जेक्ट का उपयोग करता है, एंट्री, जो डाटा को स्टोर करने के लिए एक स्थिर नेस्टेड क्लास है और अगले और पिछले दो नोड्स जबकि ऐरेलिस्ट केवल ऐरे में डेटा स्टोर करता है।

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

यदि ऐरे काफी बड़ा है तो उस बिंदु पर बहुत सारी मेमोरी ले सकती है और कचरा संग्रहण ट्रिगर कर सकती है, जो प्रतिक्रिया समय को धीमा कर सकती है।

ArrayList बनाम लिंक्डलिस्ट के बीच के सभी उपरोक्त मतभेदों से, ऐसा लगता है कि जब आप निकालें (), या प्राप्त () से अक्सर add () ऑपरेशन करते हैं तो छोड़कर ऐरेलेस्टिस्ट लगभग सभी मामलों में लिंक्डलिस्ट से बेहतर विकल्प है।

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

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

मेरी राय में, जावा में अधिकांश व्यावहारिक उद्देश्यों के लिए LinkedList पर ArrayList का उपयोग करें।


ArrayList वह है जो आप चाहते हैं। LinkedList लगभग हमेशा एक (प्रदर्शन) बग है।

क्यों LinkedList बेकार है:

  • यह बहुत सी छोटी मेमोरी ऑब्जेक्ट्स का उपयोग करता है, और इसलिए प्रक्रिया में प्रदर्शन को प्रभावित करता है।
  • कैश-इलाके के लिए बहुत सी छोटी वस्तुएं खराब हैं।
  • किसी भी अनुक्रमित ऑपरेशन के लिए एक ट्रैवर्सल की आवश्यकता होती है, यानी ओ (एन) प्रदर्शन होता है। यह स्रोत कोड में स्पष्ट नहीं है, जिससे एरेग्लिदम ओ (एन) की वजह से धीमी गति से ArrayList का उपयोग किया जाता है।
  • अच्छा प्रदर्शन प्राप्त करना मुश्किल है।
  • यहां तक ​​कि जब बड़े-ओ प्रदर्शन ArrayList के समान होता है, वैसे भी यह संभवतः धीमा होने वाला है।
  • यह LinkedList को स्रोत में देखने के लिए LinkedList है क्योंकि यह शायद गलत विकल्प है।

लिंक्डलिस्ट के लेखक जोशुआ ब्लोच:

क्या कोई वास्तव में लिंक्डलिस्ट का उपयोग करता है? मैंने इसे लिखा, और मैंने इसका कभी भी उपयोग नहीं किया।

लिंक: https://twitter.com/joshbloch/status/583813919019573248

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


ArrayListयादृच्छिक रूप से सुलभ है, जबकि LinkedListतत्वों का विस्तार और निकालने के लिए वास्तव में सस्ता है। ज्यादातर मामलों के लिए, ArrayListठीक है।

जब तक आप बड़ी सूचियां नहीं बनाते और एक बाधा उत्पन्न नहीं करते हैं, तो आपको शायद इस अंतर के बारे में चिंता करने की आवश्यकता नहीं होगी।


यह एक दक्षता सवाल है। LinkedList तत्वों को जोड़ने और हटाने के लिए तेज़ है, लेकिन एक विशिष्ट तत्व तक पहुंचने में धीमा है। ArrayList एक विशिष्ट तत्व तक पहुंचने के लिए तेज़ है लेकिन किसी भी अंत में जोड़ने के लिए धीमा हो सकता है, और विशेष रूप से मध्य में हटाने के लिए धीमा हो सकता है।

ऐरे बनाम ऐरेलिस्ट लिंक्ड लिस्ट बनाम वेक्टर गहराई से अधिक जाता है, जैसा कि लिंक्ड लिस्ट करता है।


यदि आपके कोड में है add(0)और remove(0), इसका उपयोग करें LinkedListऔर यह सुंदर addFirst()और removeFirst()विधियों का उपयोग करें। अन्यथा, उपयोग करें ArrayList

और निश्चित रूप से, Guava की ImmutableList आपका सबसे अच्छा दोस्त है।


दोनों निकालें () और डालने () में ArrayLists और LinkedLists दोनों के लिए ओ (एन) की रनटाइम दक्षता है। हालांकि, रैखिक प्रसंस्करण समय के पीछे कारण दो बहुत अलग कारणों से आता है:

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

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

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

बोनस: जबकि ऐरेलिस्ट के लिए इन दो विधियों ओ (1) को बनाने का कोई तरीका नहीं है, वहीं वास्तव में लिंक्डलिस्ट में ऐसा करने का एक तरीका है। आइए मान लें कि हम पूरी सूची को हटाने और हमारे रास्ते पर तत्व डालने के माध्यम से जाना चाहते हैं। आमतौर पर, आप LinkedList का उपयोग करके प्रत्येक तत्व के लिए बहुत शुरुआत से शुरू करेंगे, हम वर्तमान तत्व को "सहेजने" भी कर सकते हैं जिसे हम एक इटरेटर के साथ काम कर रहे हैं। Iterator की मदद से, हम एक LinkedList में काम करते समय हटाने () और डालने () के लिए एक ओ (1) दक्षता प्राप्त करते हैं। इसे एकमात्र प्रदर्शन लाभ बनाना मुझे पता है कि एक लिंक्डलिस्ट हमेशा ArrayList से बेहतर है।


सही या गलत: कृपया स्थानीय रूप से परीक्षण निष्पादित करें और अपने लिए निर्णय लें!

ArrayList तुलना में LinkedList में संपादित / निकालें तेज़ है।

Array द्वारा समर्थित Array , जिसे आकार को दोगुनी करने की आवश्यकता है, बड़े वॉल्यूम एप्लिकेशन में खराब है।

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

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

यहां कोड है:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

यहाँ दोनों में बिग-ओ अंकन है ArrayListऔर LinkedListऔर यह भी CopyOnWrite-ArrayList:

सारणी सूची

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

लिंक्ड सूची

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

इनके आधार पर आपको यह तय करना होगा कि क्या चुनना है। :)


मुझे पता है कि यह एक पुरानी पोस्ट है, लेकिन मैं ईमानदारी से विश्वास नहीं कर सकता कि किसी ने उस LinkedListउपकरण का उल्लेख नहीं किया है Deque। बस Deque(और Queue) में विधियों को देखें ; यदि आप एक उचित तुलना चाहते हैं, तो फीचर-फॉर-फीचर तुलना के LinkedListविरुद्ध चलने का प्रयास करें ArrayDeque


एक सरणी सूची अनिवार्य रूप से आइटम जोड़ने के तरीकों के साथ एक सरणी है (और आपको इसके बजाय एक सामान्य सूची का उपयोग करना चाहिए)। यह उन वस्तुओं का संग्रह है जिन्हें एक इंडेक्सर के माध्यम से एक्सेस किया जा सकता है (उदाहरण के लिए [0])। यह एक आइटम से अगले आइटम में प्रगति का तात्पर्य है।

एक लिंक्ड सूची एक आइटम से अगले तक एक प्रगति निर्दिष्ट करती है (आइटम ए -> आइटम बी)। आप एक सरणी सूची के साथ एक ही प्रभाव प्राप्त कर सकते हैं, लेकिन एक लिंक्ड सूची पूरी तरह से कहती है कि पिछले आइटम का पालन करने के लिए कौन सी वस्तु का पालन करना चाहिए।


ऑपरेशन प्राप्त करें (i) ऐरेलेस्टिस्ट में लिंक्डलिस्ट से तेज़ है, क्योंकि:
ऐरेलिस्ट: सूची इंटरफ़ेस का आकार बदलने योग्य सरणी कार्यान्वयन
लिंकडलिस्ट: सूची और डेक इंटरफेस के संदेह से जुड़े सूची कार्यान्वयन

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


ArrayList अनिवार्य रूप से एक सरणी है। LinkedList को डबल लिंक्ड सूची के रूप में कार्यान्वित किया जाता है।

get करना बहुत स्पष्ट है। ओ (1) ArrayList , क्योंकि ArrayList सूचकांक का उपयोग कर यादृच्छिक उपयोग की अनुमति देता है। ओ (एन) LinkedList , क्योंकि इसे पहले इंडेक्स को खोजने की जरूरत है। नोट: add और remove विभिन्न संस्करण हैं।

LinkedList जोड़ने और हटाने में तेज़ है, लेकिन पाने में धीमी है। संक्षेप में, LinkedList को प्राथमिकता दी जानी चाहिए यदि:

  1. तत्व की यादृच्छिक पहुंच की कोई बड़ी संख्या नहीं है
  2. बड़ी संख्या में जोड़ने / निकालने के संचालन हैं

=== ArrayList ===

  • जोड़ें (ई ई)
    • ArrayList के अंत में जोड़ें
    • स्मृति आकार बदलने की लागत की आवश्यकता है।
    • ओ (एन) सबसे खराब, ओ (1) amortized
  • जोड़ें (int सूचकांक, ई तत्व)
    • एक विशिष्ट सूचकांक स्थिति में जोड़ें
    • स्थानांतरण और संभावित स्मृति आकार बदलने की लागत की आवश्यकता है
    • पर)
  • निकालें (इंट इंडेक्स)
    • एक निर्दिष्ट तत्व को हटा दें
    • स्थानांतरण और संभावित स्मृति आकार बदलने की लागत की आवश्यकता है
    • पर)
  • निकालें (ऑब्जेक्ट ओ)
    • इस सूची से निर्दिष्ट तत्व की पहली घटना को हटा दें
    • पहले तत्व को खोजने की आवश्यकता है, और उसके बाद स्थानांतरण और संभावित मेमोरी आकार बदलने की लागत
    • पर)

=== लिंक्डलिस्ट ===

  • जोड़ें (ई ई)

    • सूची के अंत में जोड़ें
    • हे (1)
  • जोड़ें (int सूचकांक, ई तत्व)

    • निर्दिष्ट स्थिति में डालें
    • पहले स्थिति को खोजने की जरूरत है
    • पर)
  • हटाना()
    • सूची के पहले तत्व को हटा दें
    • हे (1)
  • निकालें (इंट इंडेक्स)
    • निर्दिष्ट सूचकांक के साथ तत्व हटा दें
    • पहले तत्व खोजने की जरूरत है
    • पर)
  • निकालें (ऑब्जेक्ट ओ)
    • निर्दिष्ट तत्व की पहली घटना को हटा दें
    • पहले तत्व खोजने की जरूरत है
    • पर)

programcreek.com से एक आंकड़ा यहां दिया गया है ( addऔर removeपहले प्रकार हैं, यानी, सूची के अंत में एक तत्व जोड़ें और सूची में निर्दिष्ट स्थिति पर तत्व को हटा दें।):


ऊपर अन्य अच्छे तर्क के अलावा, आप नोटिस देना चाहिए ArrayListऔजार RandomAccessइंटरफेस है, जबकि LinkedListऔजार Queue

इसलिए, किसी भी तरह वे दक्षता और व्यवहार के अंतर के साथ थोड़ा अलग समस्याओं का समाधान करते हैं (उनकी विधियों की सूची देखें)।


ArrayList सार सूची बढ़ाता है और सूची इंटरफ़ेस लागू करता है। ArrayList गतिशील सरणी है।
यह कहा जा सकता है कि इसे मूल रूप से सरणी

की कमी को दूर करने के लिए बनाया गया था । लिंक्डलिस्ट वर्ग सार सारणी सूची और विस्तार सूची, डेक और कतार इंटरफ़ेस को बढ़ाता है।
प्रदर्शन
arraylist.get()ओ (1) है जबकि linkedlist.get()ओ (एन)
arraylist.add()ओ (1) है और linkedlist.add()0 (1)
arraylist.contains()ओ (एन) है और linkedlist.contains()ओ (एन)
arraylist.next()ओ (1) है और linkedlist.next()ओ (1)
arraylist.remove()ओ (एन) है जबकि linkedlist.remove()है हे (1)
ArrayList में
iterator.remove()हे (एन) है
, जबकि में linkedlist
iterator.remove()हे है (1)


मैंने प्रतिक्रियाएं पढ़ी हैं, लेकिन एक परिदृश्य है जहां मैं हमेशा एक ऐरेलिस्टिस्ट पर लिंक्डलिस्ट का उपयोग करता हूं जिसे मैं राय सुनने के लिए साझा करना चाहता हूं:

हर बार जब मेरे पास एक विधि थी जो डीबी से प्राप्त डेटा की एक सूची देता है तो मैं हमेशा एक लिंक्डलिस्ट का उपयोग करता हूं।

मेरा तर्क यह था कि यह जानना असंभव है कि मुझे कितने परिणाम मिल रहे हैं, स्मृति बर्बाद नहीं होगी (जैसे कि ऐरेलिस्ट में क्षमता और वास्तविक तत्वों के बीच अंतर के साथ), और कोई समय बर्बाद नहीं होगा क्षमता डुप्लिकेट करें।

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


हाँ, मुझे पता है, यह एक प्राचीन सवाल है, लेकिन मैं अपने दो सेंट में फेंक दूंगा:

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

एक आम उपयोग केस है जिसमें लिंक्डलिस्ट ने ऐरेलिस्ट को बेहतर प्रदर्शन किया है: एक कतार का। हालांकि, यदि आपका लक्ष्य प्रदर्शन है, तो लिंक्डलिस्ट के बजाय आपको एक ऐरेब्लॉकिंगक्यूयू का उपयोग करने पर भी विचार करना चाहिए (यदि आप समय से पहले अपने कतार आकार पर ऊपरी बाउंड निर्धारित कर सकते हैं, और सभी मेमोरी को आगे आवंटित कर सकते हैं), या यह परिपत्रअरेलेलिस्ट कार्यान्वयन । (हां, यह 2001 से है, इसलिए आपको इसे जेनरेट करने की आवश्यकता होगी, लेकिन मुझे हाल ही में जेवीएम में आलेख में उद्धृत किए गए तुलनात्मक प्रदर्शन अनुपात मिल गए हैं)


ArrayList और LinkedList के अपने पेशेवर और विपक्ष है।

ArrayList LinkedList की तुलना में संगत स्मृति पता का उपयोग करता है जो अगले नोड की ओर पॉइंटर्स का उपयोग करता है। तो जब आप एक ऐरेलिस्ट में एक तत्व देखना चाहते हैं तो LinkedList के साथ एन पुनरावृत्तियों करने से तेज़ है।

दूसरी तरफ, लिंक्डलिस्ट में सम्मिलन और हटाना बहुत आसान है क्योंकि आपको केवल पॉइंटर्स को बदलना होगा जबकि एक ऐरेलिस्ट किसी भी प्रविष्टि या हटाने के लिए शिफ्ट ऑपरेशन के उपयोग का तात्पर्य है।

यदि आपके ऐप में लगातार पुनर्प्राप्ति अभियान आपके पास एक ऐरेलिस्ट का उपयोग करते हैं। यदि आपके पास लगातार सम्मिलन और हटाना एक लिंक्डलिस्ट का उपयोग करता है।


यह इस बात पर निर्भर करता है कि आप सूची में कौन से परिचालन करेंगे।

ArrayListअनुक्रमित मूल्य तक पहुंचने के लिए तेज़ है। ऑब्जेक्ट्स डालने या हटाने पर यह बहुत खराब होता है।

अधिक जानने के लिए, किसी लेख को पढ़ें जो सरणी और लिंक्ड सूचियों के बीच अंतर के बारे में बात करता है।


1) खोज: LinkedList खोज ऑपरेशन की तुलना में ArrayList खोज ऑपरेशन बहुत तेज़ है। ArrayList में प्राप्त करें (int अनुक्रमणिका) ओ (1) का प्रदर्शन देता है जबकि LinkedList प्रदर्शन ओ (एन) है।

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

2) हटाना: लिंक्ड लिस्ट हटाने का ऑपरेशन ओ (1) प्रदर्शन देता है जबकि ऐरेलिस्ट परिवर्तनीय प्रदर्शन देता है: ओ (एन) सबसे खराब मामले में (पहले तत्व को हटाते समय) और ओ (1) सर्वोत्तम मामले में (अंतिम तत्व को हटाते समय) ।

निष्कर्ष: LinkedList तत्व हटाना ArrayList की तुलना में तेज़ है।

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

3) सम्मिलन प्रदर्शन: लिंक्डलिस्ट जोड़ें विधि ओ (1) प्रदर्शन देता है जबकि ArrayList सबसे खराब मामले में ओ (एन) देता है। कारण निकालने के लिए समझाया गया है।

4) मेमोरी ओवरहेड: ऐरेलिस्ट इंडेक्स और एलिमेंट डेटा रखता है जबकि लिंक्डलिस्ट तत्व डेटा और पड़ोसी नोड्स के लिए दो पॉइंटर्स रखता है इसलिए तुलनात्मक रूप से लिंक्डलिस्ट में मेमोरी खपत अधिक होती है।

हैं कुछ समानताएं इन कक्षाओं में जो इस प्रकार हैं के बीच:

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

LinkedList का उपयोग कब करें और ArrayList का उपयोग कब करें?

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

2) खोज (विधि प्राप्त करें) ऑपरेशन ArrayList (O (1)) में तेजी से हैं, लेकिन लिंक्डलिस्ट (ओ (एन) में नहीं है, इसलिए यदि संचालन में कम जोड़ और निकालें और अधिक खोज परिचालन आवश्यकताएं हैं, तो ऐरेलिस्ट आपकी सबसे अच्छी शर्त होगी।


Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

एल्गोरिदम: बिग-ओ नोटेशन

ArrayLists लिखने के लिए अच्छे हैं-एक बार पढ़ने-कई या परिशिष्ट, लेकिन सामने या मध्य से जोड़ने / हटाने पर बुरा।


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

ArrayList बनाम LinkedList

1) Search: ArrayListखोज ऑपरेशन की तुलना में LinkedListखोज ऑपरेशन बहुत तेज़ है । get(int index)में ArrayListके प्रदर्शन देता है O(1), जबकि LinkedListहै प्रदर्शन O(n)

Reason: ArrayListसूचकांक आधारित प्रणाली को अपने तत्वों के लिए बनाए रखता है क्योंकि यह सरणी डेटा संरचना का उपयोग करता है जो स्पष्ट रूप से सूची में तत्व खोजने के लिए तेज़ी से बनाता है। दूसरी तरफ LinkedListदोगुनी जुड़ी सूची लागू होती है जिसके लिए तत्व खोजने के लिए सभी तत्वों के माध्यम से ट्रैवर्सल की आवश्यकता होती है।

2) निष्पादन निष्पादन प्रदर्शन Deletion: LinkedListदेता है O(1)जबकि ArrayListपरिवर्तनीय प्रदर्शन देता है: O(n)सबसे खराब स्थिति में (पहले तत्व को हटाते समय) और O(1)सर्वोत्तम मामले में (अंतिम तत्व को हटाते समय)।

निष्कर्ष: LinkedList तत्व हटाना ArrayList की तुलना में तेज़ है।

कारण: लिंक्डलिस्ट का प्रत्येक तत्व दो पॉइंटर्स (पते) को बनाए रखता है जो सूची में दोनों पड़ोसी तत्वों को इंगित करता है। इसलिए निष्कासन को केवल नोड के दो पड़ोसी नोड्स (तत्वों) में सूचक स्थान में परिवर्तन की आवश्यकता होती है जिसे हटाया जा रहा है। जबकि ArrayList में सभी तत्वों को हटाए गए तत्व द्वारा बनाई गई जगह को भरने के लिए स्थानांतरित करने की आवश्यकता है।

3) सबसे खराब मामले में देता है जबकि Inserts Performance: LinkedListविधि जोड़ने O(1)प्रदर्शन ArrayListदेता O(n)है। कारण निकालने के लिए समझाया गया है।

4) Memory Overhead: ArrayListइंडेक्स और तत्व डेटा LinkedListबनाए रखता है जबकि तत्व डेटा और पड़ोसी नोड्स के लिए दो पॉइंटर्स बनाए रखता है

इसलिए तुलनात्मक रूप से लिंक्डलिस्ट में मेमोरी खपत अधिक है।

इन वर्गों के बीच कुछ समानताएं हैं जो निम्नानुसार हैं:

  • ArrayList और LinkedList दोनों सूची इंटरफ़ेस के कार्यान्वयन हैं।
  • वे दोनों तत्व प्रविष्टि आदेश को बनाए रखते हैं जिसका मतलब है कि ऐरेलिस्ट और लिंक्डलिस्ट तत्वों को प्रदर्शित करते समय परिणाम सेट में वही क्रम होगा जिसमें तत्व सूची में डाले गए थे।
  • इन दोनों वर्गों को गैर सिंक्रनाइज़ किया गया है और संग्रह। सिंक्रनाइज़लिस्ट सूची का उपयोग कर स्पष्ट रूप से सिंक्रनाइज़ किया जा सकता है।
  • iteratorऔर listIteratorइन कक्षाओं द्वारा लौटाए गए हैं fail-fast(यदि सूची संरचनात्मक रूप से के माध्यम से छोड़कर, किसी भी समय संशोधित किया गया है किसी भी तरह से करने के बाद इटरेटर बनाई गई है iterator'sखुद हटाना होगा या विधियों को जोड़ने, इटरेटर होगा throwएक ConcurrentModificationException)।

LinkedList का उपयोग कब करें और ArrayList का उपयोग कब करें?

  • जैसा कि सम्मिलित करें और निकालें ऑपरेशन के ऊपर समझाया गया है, इसकी तुलना (O(1))में अच्छा प्रदर्शन प्रदान LinkedListकरता है ArrayList(O(n))

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

  • खोज ( get method) संचालन तेजी से हैं Arraylist (O(1))लेकिन अंदर नहीं हैंLinkedList (O(n))

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


समावेशी / अनन्य सीमाओं के किसी संयोजन के साथ सीमा में यादृच्छिक ints उत्पन्न करने के लिए यहां एक सहायक वर्ग है:

import java.util.Random;

public class RandomRange extends Random {
    public int nextIncInc(int min, int max) {
        return nextInt(max - min + 1) + min;
    }

    public int nextExcInc(int min, int max) {
        return nextInt(max - min) + 1 + min;
    }

    public int nextExcExc(int min, int max) {
        return nextInt(max - min - 1) + 1 + min;
    }

    public int nextIncExc(int min, int max) {
        return nextInt(max - min) + min;
    }
}






java arraylist collections linked-list