Vraag Wanneer gebruik ik LinkedList via ArrayList?


Ik ben altijd iemand geweest om gewoon te gebruiken:

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

Ik gebruik de interface als de typenaam voor draagbaarheid, zodat ik, wanneer ik dergelijke vragen stel, mijn code kan herwerken.

Wanneer moet LinkedList worden gebruikt ArrayList en vice versa?


2565
2017-11-27 01:36


oorsprong


antwoorden:


Overzicht  ArrayList met ArrayDeque hebben de voorkeur in veel meer use-cases dan LinkedList. Niet zeker - begin maar met ArrayList.


LinkedList en ArrayList zijn twee verschillende implementaties van de lijst-interface. LinkedList implementeert het met een dubbel gelinkte lijst. ArrayList implementeert het met een dynamisch re-sizing array.

Net als bij standaard gekoppelde lijst- en arraybewerkingen, hebben de verschillende methoden verschillende algoritmische runtimes.

Voor LinkedList<E>

  • get(int index) is Op) (met n / 4 stappen gemiddeld)
  • add(E element) is O (1)
  • add(int index, E element) is Op) (met n / 4 stappen gemiddeld), maar O (1) wanneer index = 0  <--- belangrijkste voordeel van LinkedList<E>
  • remove(int index) is Op) (met n / 4 stappen gemiddeld)
  • Iterator.remove() is O (1). <--- belangrijkste voordeel van LinkedList<E>
  • ListIterator.add(E element) is O (1)  Dit is een van de belangrijkste voordelen van LinkedList<E>

Opmerking: veel van de bewerkingen hebben dit nodig n / 4 stappen gemiddeld constante aantal stappen in het beste geval (bijvoorbeeld index = 0) en n / 2 stappen in het slechtste geval (midden van de lijst)

Voor ArrayList<E>

  • get(int index) is O (1)  <--- belangrijkste voordeel van ArrayList<E>
  • add(E element) is O (1) afgeschreven, maar Op) In het slechtste geval, aangezien de array moet worden aangepast en gekopieerd
  • add(int index, E element) is Op) (met n / 2 stappen gemiddeld)
  • remove(int index) is Op) (met n / 2 stappen gemiddeld)
  • Iterator.remove() is Op) (met n / 2 stappen gemiddeld)
  • ListIterator.add(E element) is Op) (met n / 2 stappen gemiddeld)

Opmerking: veel van de bewerkingen hebben dit nodig n / 2 stappen gemiddeld constante aantal stappen in het beste geval (einde lijst), n stappen in het slechtste geval (begin lijst)

LinkedList<E> zorgt voor invoeging of verwijdering van constante tijden met behulp van iterators, maar alleen sequentiële toegang van elementen. Met andere woorden, u kunt de lijst vooruit of achteruit lopen, maar het vinden van een positie in de lijst kost tijd in verhouding tot de grootte van de lijst. Javadoc zegt "bewerkingen die in de lijst indexeren, doorlopen de lijst vanaf het begin of het einde, afhankelijk van wat zich het dichtst bevindt", dus die methoden zijn Op) (n / 4 stappen) gemiddeld O (1) voor index = 0.

ArrayList<E>, aan de andere kant, staat snelle willekeurige leestoegang toe, zodat je elk element in constante tijd kunt grijpen. Maar het toevoegen of verwijderen van ergens anders dan het einde vereist het verschuiven van alle laatste elementen, ofwel om een ​​opening te maken of om de opening te vullen. Als u meer elementen toevoegt dan de capaciteit van de onderliggende array, wordt een nieuwe array (1,5 keer de grootte) toegewezen en wordt de oude array naar de nieuwe gekopieerd, dus toevoegen aan een nieuwe array. ArrayList is Op) in het slechtste geval, maar constant gemiddeld.

Dus afhankelijk van de bewerkingen die u van plan bent te doen, moet u de implementaties overeenkomstig kiezen. Het is vrijwel even goedkoop om elke soort lijst te herhalen. (Iteratie over een ArrayList is technisch sneller, maar tenzij je echt prestatiegevoelig bezig bent, moet je je hier geen zorgen over maken - het zijn beide constanten.)

De belangrijkste voordelen van het gebruik van een LinkedList ontstaan ​​wanneer u bestaande iterators hergebruikt om elementen in te voegen en te verwijderen. Deze bewerkingen kunnen dan worden gedaan in O (1) door de lijst alleen lokaal te wijzigen. In een arraylijst moet de rest van de array aanwezig zijn verhuisd (dat wil zeggen gekopieerd). Aan de andere kant, op zoek naar een LinkedList betekent het volgen van de links in Op) (n / 2 stappen) voor het slechtste geval, terwijl in een ArrayList de gewenste positie kan wiskundig worden berekend en benaderd worden O (1).

Een ander voordeel van het gebruik van een LinkedList ontstaan ​​wanneer u toevoegt of verwijdert uit de kop van de lijst, aangezien deze bewerkingen zijn O (1), terwijl ze zijn Op) voor ArrayList. Let daar op ArrayDeque kan een goed alternatief zijn voor LinkedList voor het toevoegen en verwijderen van het hoofd, maar het is geen List.

Ook als u grote lijsten heeft, houd er dan rekening mee dat het geheugengebruik ook anders is. Elk element van een LinkedList heeft meer overhead omdat wijzers naar de volgende en vorige elementen ook worden opgeslagen. ArrayLists heb deze overhead niet. Echter, ArrayLists neem evenveel geheugen op als is toegewezen voor de capaciteit, ongeacht of elementen daadwerkelijk zijn toegevoegd.

De standaard initiële capaciteit van een ArrayList is vrij klein (10 van Java 1.4 - 1.8). Maar aangezien de onderliggende implementatie een array is, moet de grootte van de array worden gewijzigd als u veel elementen toevoegt. Om de hoge kosten van het wijzigen van het formaat te vermijden, wanneer u weet dat u veel elementen gaat toevoegen, bouwt u het ArrayList met een hogere initiële capaciteit.


2845
2017-10-06 06:46



Tot dusver lijkt niemand de geheugenvoetafdruk van elk van deze lijsten te hebben aangepakt, naast de algemene consensus dat een LinkedList is "veel meer" dan een ArrayList dus heb ik wat rekenwerk gedaan om precies aan te tonen hoeveel beide lijsten in beslag nemen voor N lege referenties.

Omdat verwijzingen 32 of 64 bits (zelfs nul) op hun relatieve systemen zijn, heb ik 4 datasets voor 32 en 64 bit opgenomen LinkedLists en ArrayLists.

Notitie: De maten weergegeven voor de ArrayList lijnen zijn voor bijgesneden lijsten - In de praktijk is de capaciteit van de achtergrondarray in een ArrayList is over het algemeen groter dan het huidige aantal elementen.

Opmerking 2:  (bedankt BeeOnRope) Omdat CompressedOops nu standaard is vanaf midden JDK6 en hoger, zullen de onderstaande waarden voor 64-bits machines in principe overeenkomen met hun 32-bits tegenhangers, tenzij u dit specifiek uitschakelt.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Het resultaat laat dat duidelijk zien LinkedList is veel meer dan ArrayList, vooral met een zeer hoog aantal elementen. Als geheugen een factor is, blijf dan weg LinkedLists.

De formules die ik heb gebruikt volgen, laten me weten of ik iets verkeerd heb gedaan en ik zal het oplossen. 'b' is ofwel 4 of 8 voor 32- of 64-bits systemen en 'n' is het aantal elementen. Let op de reden voor de mods is omdat alle objecten in java een veelvoud van 8 bytes ruimte innemen, ongeacht of het allemaal wordt gebruikt of niet.

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)

534
2017-11-27 14:20



ArrayList is wat je wilt. LinkedList is bijna altijd een (performance) bug.

Waarom LinkedList zuigt:

  • Het gebruikt veel kleine geheugenobjecten en heeft daarom invloed op de prestaties van het hele proces.
  • Veel kleine objecten zijn slecht voor cache-localiteit.
  • Elke geïndexeerde bewerking vereist een traversal, d.w.z. heeft O (n) -prestatie. Dit is niet duidelijk in de broncode, wat leidt tot algoritmen O (n) langzamer dan wanneer ArrayListwas gebruikt.
  • Goede prestaties halen is lastig.
  • Zelfs wanneer de big-O-prestaties hetzelfde zijn als ArrayList, het zal hoe dan ook waarschijnlijk aanzienlijk langzamer gaan.
  • Het is schokkend om te zien LinkedList in bron omdat het waarschijnlijk de verkeerde keuze is.

190
2018-01-01 20:23



Als iemand die al ongeveer een decennium operationele prestatie-engineering uitvoert op zeer grote SOA-webservices, zou ik het gedrag van LinkedList boven ArrayList verkiezen. Hoewel de steady-state doorvoer van LinkedList slechter is en daarom kan leiden tot het kopen van meer hardware - het gedrag van ArrayList onder druk kan ertoe leiden dat apps in een cluster hun arrays in bijna synchroniciteit uitbreiden en voor grote reeksen groottes kunnen leiden tot gebrek aan responsiviteit in de app en een storing, terwijl ze onder druk staan, wat catastrofaal gedrag is.

Op dezelfde manier kun je een betere doorvoer krijgen in een app van de standaard doorvoerde tenured garbage collector, maar als je eenmaal Java-apps hebt met 10GB heaps, kun je de app 25 seconden blokkeren tijdens een Full GCs waardoor time-outs en storingen in SOA-apps worden veroorzaakt en blaast uw SLA's als het te vaak gebeurt. Hoewel de CMS-verzamelaar meer bronnen nodig heeft en niet dezelfde onbewerkte verwerkingscapaciteit bereikt, is het een veel betere keuze omdat het meer voorspelbare en kleinere latentie heeft.

ArrayList is alleen een betere keuze voor prestaties als alles wat u bedoelt met prestaties doorvoer is en u de latentie kunt negeren. In mijn ervaring op mijn werk kan ik de latentie van worst-cases niet negeren.


125
2018-04-08 20:33



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)

Algoritmen: Big-Oh-notatie

ArrayLists zijn goed voor éénmalig schrijven of veelvoorkomende appenders, maar slecht bij toevoegen / verwijderen vanaf de voorkant of in het midden.


111
2018-05-19 11:21



Ja, ik weet het, dit is een oude vraag, maar ik gooi in mijn twee cent:

LinkedList is bijna altijd de verkeerde keuze, qua prestaties. Er zijn enkele zeer specifieke algoritmen waar een LinkedList voor nodig is, maar die zijn zeer, zeer zeldzaam en het algoritme zal meestal specifiek afhangen van de mogelijkheid van LinkedList om relatief snel elementen in te voegen en te verwijderen, zodra je daar bent genavigeerd met een ListIterator.

Er is één algemene use-case waarin LinkedList beter presteert dan ArrayList: die van een wachtrij. Als uw doel echter prestatie is, in plaats van met LinkedList, moet u ook een ArrayBlockingQueue overwegen (als u van tevoren een bovengrens voor uw wachtrijgrootte kunt bepalen en het u veroorloven om al het geheugen vooraf toe te wijzen), of dit CircularArrayList-implementatie. (Ja, het komt uit 2001, dus je moet het genereren, maar ik heb vergelijkbare prestatieverhoudingen vergeleken met wat in het artikel zojuist in een recente JVM wordt geciteerd)


92
2017-11-27 01:39



Het is een efficiëntievraag. LinkedList is snel voor het toevoegen en verwijderen van elementen, maar traag om toegang te krijgen tot een specifiek element. ArrayList is snel voor toegang tot een specifiek element, maar kan traag zijn om toe te voegen aan beide uiteinden, en vooral langzaam te verwijderen in het midden.

Array vs ArrayList versus LinkedList vs Vectorgaat meer in de diepte, zoals doet Gekoppelde lijst.


50
2017-09-21 22:59



Juist of onjuist: Voer de test lokaal uit en beslis zelf!

Bewerken / verwijderen gaat sneller LinkedList dan ArrayList.

ArrayList, ondersteund door Array, dat dubbel zo groot moet zijn, is erger bij het gebruik van groot volume.

Hieronder vindt u het testresultaat per eenheid voor elke bewerking. Tellen wordt gegeven in Nanoseconden.


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

Hier is de code:

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

49
2018-04-21 00:03



ArrayList is in wezen een array. LinkedList is geïmplementeerd als een dubbele gekoppelde lijst.

De get is vrij duidelijk. O (1) voor ArrayList, omdat ArrayList sta willekeurige toegang toe door index te gebruiken. O (n) voor LinkedList, omdat het de index eerst moet vinden. Let op: er zijn verschillende versies van add en remove.

LinkedList is sneller bij toevoegen en verwijderen, maar langzamer bij krijgen. In het kort, LinkedList verdient de voorkeur als:

  1. er is geen groot aantal willekeurige toegang van element
  2. er zijn een groot aantal bewerkingen voor toevoegen / verwijderen

=== ArrayList ===

  • voeg toe (E e)
    • voeg aan het einde van ArrayList toe
    • geheugen nodig wijzigen van de kosten.
    • O (n) slechtste, O (1) geamortiseerd
  • add (int index, E element)
    • toevoegen aan een specifieke indexpositie
    • vereisen verschuiven en mogelijke kosten voor het wijzigen van het geheugen
    • Op)
  • verwijderen (int index)
    • verwijder een gespecificeerd element
    • vereisen verschuiven en mogelijke kosten voor het wijzigen van het geheugen
    • Op)
  • verwijderen (Object o)
    • verwijder de eerste instantie van het opgegeven element uit deze lijst
    • moet eerst het element worden doorzocht en vervolgens worden verschoven en mogelijke kosten voor het wijzigen van het geheugen worden gewijzigd
    • Op)

=== LinkedList ===

  • voeg toe (E e)

    • voeg toe aan het einde van de lijst
    • O (1)
  • add (int index, E element)

    • invoegen op opgegeven positie
    • moet eerst de positie vinden
    • Op)
  • verwijderen()
    • verwijder het eerste element van de lijst
    • O (1)
  • verwijderen (int index)
    • verwijder element met gespecificeerde index
    • moet eerst het element vinden
    • Op)
  • verwijderen (Object o)
    • verwijder de eerste instantie van het opgegeven element
    • moet eerst het element vinden
    • Op)

Hier is een figuur van programcreek.com (add en remove zijn het eerste type, dat wil zeggen voeg een element toe aan het einde van de lijst en verwijder het element op de opgegeven positie in de lijst.):

enter image description here


38
2017-11-27 01:41



ArrayList is willekeurig toegankelijk LinkedList is echt goedkoop om uit te breiden en elementen uit te verwijderen. In de meeste gevallen ArrayList is goed.

Tenzij u grote lijsten hebt gemaakt en een knelpunt hebt gemeten, hoeft u zich waarschijnlijk nooit zorgen te maken over het verschil.


30
2017-07-07 09:22