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

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

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

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);
    }
}

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

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

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

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 वह है जो आप चाहते हैं। LinkedList लगभग हमेशा एक (प्रदर्शन) बग है।

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

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

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

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

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 के अपने पेशेवर और विपक्ष है।

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

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

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

आइए पैरामीटर के नीचे लिंक्डलिस्ट और ऐरेलिस्ट wrt की तुलना करें:

1. कार्यान्वयन

ArrayList सूची इंटरफ़ेस का आकार बदलने योग्य सरणी कार्यान्वयन है, जबकि

लिंक्डलिस्ट सूची इंटरफ़ेस का डबली-लिंक्ड सूची कार्यान्वयन है।

2. प्रदर्शन

• प्राप्त करें (int अनुक्रमणिका) या खोज ऑपरेशन

  ArrayList get (int अनुक्रमणिका) ऑपरेशन निरंतर समय यानी ओ (1) के दौरान चलता है

  लिंक्डलिस्ट प्राप्त करें (इंट इंडेक्स) ऑपरेशन रन टाइम ओ (एन) है।

  LinkedList की तुलना में ArrayList तेज होने का कारण यह है कि ArrayList इसके तत्वों के लिए एक सूचकांक आधारित सिस्टम का उपयोग करता है क्योंकि यह आंतरिक रूप से एक सरणी डेटा संरचना का उपयोग करता है,

  लिंक्डलिस्ट अपने तत्वों के लिए इंडेक्स-आधारित पहुंच प्रदान नहीं करता है क्योंकि यह निर्दिष्ट तत्व अनुक्रमणिका में नोड को पुनर्प्राप्त करने के लिए शुरुआत या अंत (जो भी करीब है) से पुनरावृत्त करता है।

• डालें () या जोड़ें (ऑब्जेक्ट) ऑपरेशन

  LinkedList में सम्मिलन आमतौर पर ArrayList की तुलना में तेज़ होते हैं। LinkedList जोड़ने या सम्मिलन में ओ (1) ऑपरेशन है।

  में रहते हुए ArrayList , अगर सरणी पूर्ण यानी सबसे खराब स्थिति है, वहाँ नई सरणी, जो ArrayList हे (एन) में जोड़ने के आपरेशन के क्रम में आता है करने के लिए सरणी और नकल तत्वों का आकार बदलने की एक अतिरिक्त लागत है, अन्यथा यह हे है (1) ।

• निकालें (int) ऑपरेशन

  LinkedList में ऑपरेशन निकालें आमतौर पर ArrayList यानी ओ (एन) के समान होता है।

  में LinkedList , वहाँ दो अतिभारित निकालें तरीके हैं। एक हटाया जाता है () किसी भी पैरामीटर के बिना जो सूची के सिर को हटा देता है और निरंतर समय ओ (1) में चलता है। LinkedList में अन्य अधिभारित निकालने का तरीका निकालें (int) या निकालें (ऑब्जेक्ट) जो पैरामीटर के रूप में ऑब्जेक्ट या int को हटा देता है। यह विधि लिंक्डलिस्ट को तब तक पार करती है जब तक ऑब्जेक्ट नहीं मिला और इसे मूल सूची से अनलिंक कर दिया जाए। इसलिए इस विधि रनटाइम ओ (एन) है।

  जबकि ArrayList हटाने (int) विधि में पुरानी सरणी से तत्वों को नए अद्यतन सरणी में कॉपी करना शामिल है, इसलिए इसका रनटाइम ओ (एन) है।

3. रिवर्स इटरेटर

LinkedList अवरोही इटरेटर () के दौरान रिवर्स दिशा में पुनरावृत्त किया जा सकता है

ArrayList में कोई अवरोही इटरेटर () नहीं है , इसलिए हमें रिवर्स दिशा में ArrayList पर फिर से चलाने के लिए अपना कोड लिखना होगा।

4. प्रारंभिक क्षमता

यदि कन्स्ट्रक्टर ओवरलोड नहीं किया गया है, तो ArrayList प्रारंभिक क्षमता 10 की खाली सूची बनाता है, जबकि

लिंक्डलिस्ट केवल प्रारंभिक क्षमता के बिना खाली सूची बनाता है।

5. मेमोरी ओवरहेड

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

में ArrayList प्रत्येक सूचकांक केवल वास्तविक वस्तु (डेटा) आयोजित करता है।

Source

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

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

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

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

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

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

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

जावा ट्यूटोरियल देखें - सूची कार्यान्वयन ।

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)

एक लिंक्ड सूची की एक महत्वपूर्ण विशेषता (जिसे मैंने किसी अन्य उत्तर में नहीं पढ़ा) दो सूचियों का समापन है। एक सरणी के साथ यह एक जुड़ी सूची के साथ ओ (एन) (कुछ पुनर्विक्रयों का ओवरहेड) है, यह केवल ओ (1) या ओ (2) ;-) है

महत्वपूर्ण : जावा के लिए LinkedListयह सच नहीं है! जावा में लिंक्ड सूची के लिए एक तेज संगत विधि देखें क्या देखें ?

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

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

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

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

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

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

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

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

यहाँ दोनों में बिग-ओ अंकन है 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)

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

यहां पर किए गए परीक्षणों में से एक केवल परीक्षण एक बार आयोजित करता है। लेकिन मैंने जो देखा है वह है कि आपको इन परीक्षणों को कई बार चलाने की ज़रूरत है और अंत में उनका समय अभिसरण हो जाएगा। असल में जेवीएम को गर्म करने की जरूरत है। मेरे विशेष उपयोग के मामले में मुझे वस्तुओं को जोड़ने / हटाने की आवश्यकता है जो लगभग 500 वस्तुओं तक बढ़ती हैं। मेरे परीक्षणों में LinkedListतेजी से बाहर आया, LinkedListलगभग 50,000 एनएस में जुड़े हुए और ArrayList90,000 एनएस में आने के साथ ... दे या ले लो। नीचे दिया गया कोड देखें।

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}