Quando utilizzare LinkedList su ArrayList in Java?

StackOverflow https://stackoverflow.com/questions/322715

Domanda

Sono sempre stato uno che usa semplicemente:

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

Utilizzo l'interfaccia come nome del tipo per portabilità, in modo che quando faccio domande come queste posso rielaborare il mio codice.

Quando dovrebbe LinkedList essere utilizzato ArrayList e viceversa?

È stato utile?

Soluzione

Riepilogo ArrayList con ArrayDeque sono preferibili in molti più casi d'uso rispetto a LinkedList. Se non sei sicuro & Nbsp; & # 8212; inizia con LinkedList<E>.

get(int index) e add(E element) sono due diverse implementazioni dell'interfaccia Elenco. add(int index, E element) lo implementa con un elenco doppiamente collegato. index = 0 lo implementa con una matrice di ridimensionamento dinamico.

Come per le operazioni standard di elenco e array collegati, i vari metodi avranno runtime algoritmici diversi.

Per remove(int index)

  • Iterator.remove() è O (n) (con n / 4 passi in media)
  • ListIterator.add(E element) è O(1)
  • ArrayList<E> è O (n) (con n / 4 passi in media), ma O (1) quando List < --- vantaggio principale di ArrayLists
  • <=> è O (n) (con n / 4 passi in media)
  • <=> è O (1) . < --- vantaggio principale di <=>
  • <=> è O (1) Questo è uno dei principali vantaggi di <=>

Nota: molte delle operazioni richiedono n / 4 passi in media, costante numero di passi nel migliore dei casi (es. indice = 0), e n / 2 passi nel caso peggiore (in mezzo all'elenco)

Per <=>

  • <=> è O (1) < --- vantaggio principale di <=>
  • <=> è O (1) ammortizzato, ma O (n) nel caso peggiore poiché l'array deve essere ridimensionato e copiato
  • <=> è O (n) (con n / 2 passi in media)
  • <=> è O (n) (con n / 2 passi in media)
  • <=> è O (n) (con n / 2 passi in media)
  • <=> è O (n) (con n / 2 passi in media)

Nota: molte operazioni richiedono n / 2 passaggi in media, costante numero di passaggi nel migliore dei casi (fine elenco), n passi nel caso peggiore (inizio elenco)

<=> consente inserimenti o rimozioni a tempo costante utilizzando iteratori , ma solo l'accesso sequenziale agli elementi. In altre parole, puoi spostare l'elenco in avanti o indietro, ma trovare una posizione nell'elenco richiede tempo proporzionale alla dimensione dell'elenco. Javadoc dice & Quot; le operazioni che indicizzano nell'elenco attraverseranno l'elenco dall'inizio o dalla fine, qualunque sia il più vicino & Quot; , quindi quei metodi sono O (n ) ( n / 4 passi) in media, sebbene O (1) per <=>.

<=>, d'altra parte, consente un rapido accesso casuale in lettura, in modo da poter afferrare qualsiasi elemento in tempo costante. Ma aggiungere o rimuovere da qualsiasi luogo tranne la fine richiede di spostare tutti questi ultimi elementi, sia per fare un'apertura che per colmare il divario. Inoltre, se aggiungi più elementi rispetto alla capacità dell'array sottostante, viene allocato un nuovo array (1,5 volte la dimensione) e il vecchio array viene copiato in quello nuovo, quindi l'aggiunta a un <=> è O (n) nel peggiore dei casi, ma costante in media.

Quindi, a seconda delle operazioni che intendi fare, dovresti scegliere le implementazioni di conseguenza. Scorrere su entrambi i tipi di Elenco è praticamente ugualmente economico. (Iterare su un <=> è tecnicamente più veloce, ma a meno che tu non stia facendo qualcosa di veramente sensibile alle prestazioni, non dovresti preoccuparti di questo: sono entrambe costanti.)

I principali vantaggi dell'utilizzo di <=> derivano dal riutilizzo di iteratori esistenti per inserire e rimuovere elementi. Queste operazioni possono quindi essere eseguite in O (1) modificando l'elenco solo localmente. In un elenco di array, il resto dell'array deve essere spostato (ovvero copiato). D'altra parte, cercare in <=> significa seguire i collegamenti in O (n) ( n / 2 ) per il caso peggiore, mentre in <=> la posizione desiderata può essere calcolata matematicamente e accessibile in O (1) .

Un altro vantaggio dell'uso di <=> si presenta quando aggiungi orimuovere dalla testa dell'elenco, poiché tali operazioni sono O (1) , mentre sono O (n) per <=>. Nota che <=> può essere una buona alternativa a <=> per aggiungere e rimuovere dalla testa, ma non è un <=>.

Inoltre, se si dispone di elenchi di grandi dimensioni, tenere presente che anche l'utilizzo della memoria è diverso. Ogni elemento di un <=> ha un overhead maggiore poiché vengono memorizzati anche i puntatori agli elementi successivo e precedente. <=> non hanno questo sovraccarico. Tuttavia, <=> occupa tutta la memoria allocata per la capacità, indipendentemente dal fatto che siano stati effettivamente aggiunti elementi.

La capacità iniziale predefinita di un <=> è piuttosto piccola (10 da Java 1.4 - 1.8). Ma poiché l'implementazione sottostante è un array, l'array deve essere ridimensionato se si aggiungono molti elementi. Per evitare il costo elevato del ridimensionamento quando sai che stai per aggiungere molti elementi, costruisci <=> con una capacità iniziale più elevata.

Altri suggerimenti

Finora, nessuno sembra aver affrontato l'impronta di memoria di ciascuno di questi elenchi oltre al consenso generale secondo cui a LinkedList è "molto di più" di un ArrayList quindi ho eseguito alcuni calcoli sui numeri per dimostrare esattamente quanto occupano entrambi gli elenchi per N riferimenti nulli.

Poiché i riferimenti sono a 32 o 64 bit (anche se nulli) sui relativi sistemi, ho incluso 4 set di dati per 32 e 64 bit LinkedLists E ArrayLists.

Nota: Le dimensioni indicate per il ArrayList le linee sono per elenchi ritagliati - In pratica, la capacità dell'array di supporto in an ArrayList è generalmente maggiore del numero di elementi corrente.

Nota 2: (grazie BeeOnRope) Poiché CompressedOops è ora predefinito dalla metà del JDK6 in su, i valori seguenti per le macchine a 64 bit corrisponderanno sostanzialmente alle loro controparti a 32 bit, a meno che ovviamente non lo disattivi specificatamente.

Graph of LinkedList and ArrayList No. of Elements x Bytes

Il risultato lo dimostra chiaramente LinkedList è molto più di ArrayList, soprattutto con un numero di elementi molto elevato.Se la memoria è un fattore, evitalo LinkedLists.

Seguono le formule che ho usato, fammi sapere se ho fatto qualcosa di sbagliato e sistemerò il problema."b" è 4 o 8 per i sistemi a 32 o 64 bit e "n" è il numero di elementi.Nota che il motivo delle modifiche è perché tutti gli oggetti in Java occuperanno uno spazio multiplo di 8 byte indipendentemente dal fatto che siano tutti utilizzati o meno.

Lista di array:

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)

Lista collegata:

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)

ArrayList è quello che vuoi. LinkedList è quasi sempre un bug (prestazioni).

Perché <=> fa schifo:

  • Utilizza molti piccoli oggetti di memoria e pertanto influisce sulle prestazioni in tutto il processo.
  • Molti piccoli oggetti sono dannosi per la localizzazione della cache.
  • Qualsiasi operazione indicizzata richiede un attraversamento, ovvero ha prestazioni O (n). Questo non è ovvio nel codice sorgente, portando ad algoritmi O (n) più lenti rispetto a quando si utilizzava <=>.
  • Ottenere buone prestazioni è complicato.
  • Anche quando le prestazioni di big-O sono le stesse di <=>, probabilmente sarà comunque significativamente più lenta.
  • È sconcertante vedere <=> nella fonte perché è probabilmente la scelta sbagliata.

Come qualcuno che si occupa di ingegneria delle prestazioni operative su servizi web SOA su larga scala da circa un decennio, preferirei il comportamento di LinkedList rispetto a ArrayList. Mentre il throughput allo stato stazionario di LinkedList è peggiore e quindi potrebbe portare all'acquisto di più hardware, il comportamento di ArrayList sotto pressione potrebbe portare ad applicazioni in un cluster che espandono i loro array in quasi sincronicità e per grandi dimensioni di array potrebbe portare a una mancanza di reattività nell'app e un'interruzione, mentre sotto pressione, che è un comportamento catastrofico.

Allo stesso modo, puoi ottenere un throughput migliore in un'app dal Garbage Collector di throughput predefinito di throughput, ma una volta ottenute app java con heap da 10 GB puoi concludere il blocco dell'app per 25 secondi durante un GC completo che causa timeout e guasti nelle app SOA e fa esplodere i tuoi SLA se si verifica troppo spesso. Anche se il raccoglitore CMS richiede più risorse e non raggiunge lo stesso throughput non elaborato, è una scelta molto migliore perché ha una latenza più prevedibile e minore.

ArrayList è solo una scelta migliore per le prestazioni se tutto ciò che intendi per prestazioni è la velocità effettiva e puoi ignorare la latenza. Nella mia esperienza nel mio lavoro non posso ignorare la latenza nel caso peggiore. 

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)

Algoritmi: Big-Oh Notation

Le liste di array sono utili per scrivere-una-sola-lettura-molte o appendici, ma male per aggiungere / rimuovere dalla parte anteriore o centrale.

Sì, lo so, questa è una domanda antica, ma aggiungerò i miei due centesimi:

LinkedList è quasi sempre la scelta sbagliata, dal punto di vista delle prestazioni. Ci sono alcuni algoritmi molto specifici in cui è richiesto un LinkedList, ma quelli sono molto, molto rari e l'algoritmo di solito dipenderà in modo specifico dalla capacità di LinkedList di inserire ed eliminare elementi in mezzo all'elenco relativamente rapidamente, una volta navigato lì con un ListIterator.

Esiste un caso d'uso comune in cui LinkedList supera ArrayList: quello di una coda. Tuttavia, se il tuo obiettivo è la prestazione, invece di LinkedList dovresti anche considerare di utilizzare un ArrayBlockingQueue (se puoi determinare in anticipo un limite superiore sulla dimensione della coda e puoi permetterti di allocare tutta la memoria in anticipo), oppure questo implementazione di CircularArrayList . (Sì, è del 2001, quindi dovrai generarlo, ma ho ottenuto rapporti di prestazione comparabili a quanto riportato nell'articolo proprio ora in una recente JVM)

È una domanda di efficienza. LinkedList è veloce per aggiungere ed eliminare elementi, ma è lento ad accedere a un elemento specifico. ArrayList è veloce per accedere a un elemento specifico ma può essere lento da aggiungere a una delle estremità e soprattutto lento da eliminare nel mezzo.

Array vs ArrayList vs LinkedList vs Vector va più in profondità, così come lo è Elenco collegato .

Corretto o errato: eseguire il test localmente e decidere autonomamente!

Modifica / Rimuovi è più veloce in LinkedList rispetto a ArrayList.

Array, supportato da <=>, che deve essere il doppio delle dimensioni, è peggio in applicazioni di grandi volumi.

Di seguito è riportato il risultato del test unitario per ciascuna operazione. La durata è espressa in nanosecondi. 

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

Ecco il codice: 

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 è essenzialmente un array. LinkedList è implementato come un doppio elenco collegato.

Il get è abbastanza chiaro. O (1) per add, poiché remove consente l'accesso casuale utilizzando l'indice. O (n) per <=>, perché deve prima trovare l'indice. Nota: esistono diverse versioni di <=> e <=>.

<=> è più veloce in aggiungi e rimuovi, ma più lento in get. In breve, <=> dovrebbe essere preferito se:

  1. non esiste un numero elevato di accessi casuali all'elemento
  2. esiste un gran numero di operazioni di aggiunta / rimozione

=== ArrayList ===

  • aggiungi (E e)
    • aggiungi alla fine di ArrayList
    • richiede costi di ridimensionamento della memoria.
    • O (n) peggiore, O (1) ammortizzato
  • aggiungi (indice int, elemento E)
    • aggiungi a una posizione di indice specifica
    • richiede lo spostamento dell'amplificatore &; possibile costo di ridimensionamento della memoria
    • O (n)
  • rimuovi (int index)
    • rimuove un elemento specificato
    • richiede lo spostamento dell'amplificatore &; possibile costo di ridimensionamento della memoria
    • O (n)
  • rimuovi (oggetto o)
    • rimuove la prima occorrenza dell'elemento specificato da questo elenco
    • è necessario prima cercare l'elemento, quindi spostare & amp; possibile costo di ridimensionamento della memoria
    • O (n)

=== LinkedList ===

  • aggiungi (E e)

    • aggiungi alla fine dell'elenco
    • O (1)

  • aggiungi (int index, elemento E)

    • inserisci nella posizione specificata
    • è necessario prima trovare la posizione
    • O (n)
  • remove ()
    • rimuove il primo elemento dell'elenco
    • O (1)
  • rimuovi (int index)
    • rimuove l'elemento con l'indice specificato
    • è necessario prima trovare l'elemento
    • O (n)
  • rimuovi (oggetto o)
    • rimuove la prima occorrenza dell'elemento specificato
    • è necessario prima trovare l'elemento
    • O (n)

Ecco una figura di programcreek.com (<=> e <=> sono il primo tipo, vale a dire aggiungere un elemento alla fine dell'elenco e rimuovere l'elemento nella posizione specificata nell'elenco).

inserisci qui la descrizione dell'immagine

Joshua Bloch, l'autore di LinkedList:

  

Qualcuno usa davvero LinkedList? L'ho scritto e non lo uso mai.

Link: https://twitter.com/joshbloch/status/583813919019573248

Mi dispiace per la risposta per non essere così istruttiva come le altre risposte, ma ho pensato che sarebbe stata la più interessante e autoesplicativa.

ArrayList è accessibile in modo casuale, mentre LinkedList è davvero economico per espandere e rimuovere elementi da. Nella maggior parte dei casi, <=> va bene.

A meno che tu non abbia creato elenchi di grandi dimensioni e misurato un collo di bottiglia, probabilmente non dovrai mai preoccuparti della differenza.

Se il tuo codice ha add(0) e remove(0), usa i metodi LinkedList ed è più carino addFirst() e removeFirst(). Altrimenti, usa ArrayList.

E, naturalmente, Guava 's ImmutableList è il tuo migliore amico.

So che questo è un vecchio post, ma onestamente non posso credere che nessuno abbia menzionato che LinkedList implementa Deque. Guarda i metodi in Queue (e ArrayDeque); se desideri un confronto equo, prova a eseguire <=> contro <=> ed esegui un confronto funzionalità per funzionalità.

Ecco la notazione Big-O in ArrayList e LinkedList e anche CopyOnWrite-ArrayList:

ArrayList 

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

LinkedList 

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

copy-on-write-ArrayList 

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

In base a questi devi decidere cosa scegliere. :)

TL; DR a causa della moderna architettura informatica, ArrayList sarà significativamente più efficiente per quasi ogni possibile caso d'uso - e quindi LinkedList dovrebbe essere evitato tranne alcuni casi davvero unici ed estremi .

In teoria, LinkedList ha una O (1) per add(E element)

Anche l'aggiunta di un elemento nel mezzo di un elenco dovrebbe essere molto efficiente.

La pratica è molto diversa, poiché LinkedList è una struttura di dati Cache ostile . Dal POV delle prestazioni - ci sono pochissimi casi in cui Int potrebbe essere più performante del compatibile con la cache Vector.

Ecco i risultati di un test di benchmark che inserisce elementi in posizioni casuali. Come puoi vedere, l'elenco di array è molto più efficiente, anche se in teoria ogni inserto in mezzo all'elenco richiederà & Quot; move & Quot; gli n elementi successivi dell'array (i valori più bassi sono migliori):

inserisci qui la descrizione dell'immagine

Lavorando su un hardware di generazione successiva (cache più grandi ed efficienti) - i risultati sono ancora più conclusivi:

inserisci qui la descrizione dell'immagine

LinkedList richiede molto più tempo per eseguire lo stesso lavoro. source Codice sorgente

Ci sono due ragioni principali per questo:

  1. Principalmente - che i nodi di <=> sono sparsi casualmente nella memoria. La RAM (& Quot; Memoria ad accesso casuale & Quot;) non è realmente casuale e i blocchi di memoria devono essere recuperati nella cache. Questa operazione richiede tempo e quando tali recuperi si verificano frequentemente, le pagine di memoria nella cache devono essere sostituite continuamente - & Gt; Manca la cache - & Gt; La cache non è efficiente. <=> gli elementi sono archiviati nella memoria continua, che è esattamente ciò per cui la moderna architettura della CPU sta ottimizzando.

  2. Secondario <=> richiesto per trattenere i puntatori indietro / avanti, il che significa 3 volte il consumo di memoria per valore memorizzato rispetto a <=>.

DynamicIntArray , a proposito, è un'implementazione ArrayList personalizzata che contiene <=> (tipo primitivo) e non Oggetti - quindi tutti i dati sono realmente archiviati in modo adiacente - quindi ancora più efficiente.

Un elemento chiave da ricordare è che il costo del recupero del blocco di memoria è più significativo del costo di accesso a una singola cella di memoria. Ecco perché il lettore 1 MB di memoria sequenziale è fino a x400 volte più veloce della lettura di questa quantità di dati da diversi blocchi di memoria: 

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Fonte: Numeri di latenza che ogni programmatore dovrebbe conoscere

Solo per rendere il punto ancora più chiaro, si prega di controllare il benchmark di aggiungere elementi all'inizio dell'elenco. Questo è un caso d'uso in cui, in teoria, il <=> dovrebbe davvero brillare e <=> dovrebbe presentare risultati mediocri o addirittura peggiori:

inserisci qui la descrizione dell'immagine

Nota: questo è un punto di riferimento della libreria C ++ Std, ma la mia precedente esperienza ha mostrato che i risultati C ++ e Java sono molto simili. Codice sorgente

La copia di una massa sequenziale di memoria è un'operazione ottimizzata dalle moderne CPU: cambiare la teoria e rendere di nuovo <=> / <=> molto più efficiente

Crediti: vengono creati tutti i benchmark pubblicati quid di Kjell Hedstr & # 246; m . Ancora più dati sono disponibili sul il suo blog

Confrontiamo LinkedList e ArrayList w.r.t. sotto i parametri:

1. Attuazione

  

ArrayList è l'implementazione di array ridimensionabile dell'interfaccia elenco, mentre

     

LinkedList è l'implementazione dell'elenco con doppio collegamento dell'interfaccia dell'elenco.

2. Prestazioni

  • get (int index) o operazione di ricerca

      L'operazione

    ArrayList get (int index) viene eseguita a tempo costante, ovvero O (1) mentre

         

    LinkedList il tempo di esecuzione dell'operazione get (int index) è O (n).

    La ragione per cui ArrayList è più veloce di LinkedList è che ArrayList utilizza un sistema basato su indice per i suoi elementi in quanto utilizza internamente una struttura di dati di array, d'altro canto,

    LinkedList non fornisce accesso basato sull'indice per i suoi elementi in quanto scorre dall'inizio o alla fine (qualunque sia il più vicino) per recuperare il nodo nell'indice degli elementi specificato.

  • operazione insert () o add (Object)

      

    Le inserzioni in LinkedList sono generalmente veloci rispetto a ArrayList. In LinkedList l'aggiunta o l'inserimento è un'operazione O (1).

         

    Mentre ci si trova in ArrayList , se l'array è il caso più completo, vale a dire il peggio, c'è un costo aggiuntivo per il ridimensionamento dell'array e la copia degli elementi nel nuovo array, il che rende il runtime dell'operazione di aggiunta in ArrayList O ( n), altrimenti è O (1).

  • rimuovi (int) operazione

    L'operazione di rimozione in LinkedList è generalmente uguale a ArrayList, ovvero O (n).

      

    In LinkedList , ci sono due metodi di rimozione sovraccaricati. uno è remove () senza alcun parametro che rimuove la testa dell'elenco e viene eseguito a tempo costante O (1). L'altro metodo di rimozione di overload in LinkedList è remove (int) o remove (Object) che rimuove l'oggetto o int passato come parametro. Questo metodo attraversa il LinkedList fino a quando non trova l'oggetto e lo scollega dall'elenco originale. Quindi questo runtime del metodo è O (n).

         

    Mentre in ArrayList il metodo remove (int) prevede la copia di elementi dal vecchio array al nuovo array aggiornato, quindi il suo runtime è O (n).

3. Iteratore inverso

  

LinkedList può essere ripetuto nella direzione inversa usando descendingIterator () mentre

     

non esiste descendingIterator () in ArrayList , quindi è necessario scrivere il nostro codice per scorrere su ArrayList in senso inverso.

4. Capacità iniziale

  

Se il costruttore non è sovraccarico, ArrayList crea un elenco vuoto della capacità iniziale 10, mentre

     

LinkedList costruisce solo l'elenco vuoto senza alcuna capacità iniziale.

5. Overhead di memoria

  

L'overhead di memoria in LinkedList è maggiore rispetto ad ArrayList poiché un nodo in LinkedList deve mantenere gli indirizzi del nodo successivo e precedente. Mentre

     

In ArrayList ogni indice contiene solo l'oggetto reale (dati).

Fonte

Oltre agli altri buoni argomenti di cui sopra, dovresti notare ArrayList implementa RandomAccess interfaccia, mentre LinkedList implementa Queue.

Quindi, in qualche modo affrontano problemi leggermente diversi, con differenze di efficienza e comportamento (vedi la loro lista di metodi).

Un elenco di array è essenzialmente un array con metodi per aggiungere elementi ecc. (e invece dovresti usare un elenco generico). È una raccolta di elementi a cui è possibile accedere tramite un indicizzatore (ad esempio [0]). Implica una progressione da un elemento all'altro.

Un elenco collegato specifica una progressione da un elemento al successivo (Articolo a - > elemento b). Puoi ottenere lo stesso effetto con un elenco di array, ma un elenco collegato dice assolutamente quale elemento dovrebbe seguire quello precedente.

Dipende da quali operazioni eseguirai di più nell'elenco.

ArrayList è più veloce per accedere a un valore indicizzato. È molto peggio quando si inseriscono o si eliminano oggetti.

Per saperne di più, leggi qualsiasi articolo che parla della differenza tra array ed elenchi collegati.

Di solito uso l'uno sull'altro in base alla complessità temporale delle operazioni che eseguirò su quel particolare Elenco. 

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Una caratteristica importante di un elenco collegato (che non ho letto in un'altra risposta) è la concatenazione di due elenchi. Con un array questo è O (n) (+ sovraccarico di alcune riallocazioni) con un elenco collegato questo è solo O (1) o O (2) ;-)

Importante : per Java il suo LinkedList non è vero! Vedi Esiste un metodo rapido di concat per l'elenco collegato in Java?

Ho letto le risposte, ma esiste uno scenario in cui utilizzo sempre una LinkedList su una ArrayList che voglio condividere per ascoltare le opinioni:

Ogni volta che ho avuto un metodo che restituisce un elenco di dati ottenuti da un DB, utilizzo sempre un LinkedList.

La mia logica era che, poiché è impossibile sapere esattamente quanti risultati sto ottenendo, non ci sarà spreco di memoria (come in ArrayList con la differenza tra la capacità e il numero effettivo di elementi) e non ci sarebbe tempo sprecato nel tentativo di duplicare la capacità.

Per quanto riguarda un ArrayList, sono d'accordo che almeno dovresti sempre usare il costruttore con la capacità iniziale, per ridurre al minimo la duplicazione degli array.

ArrayList e LinkedList hanno i loro pro e contro.

ArrayList utilizza un indirizzo di memoria contiguo rispetto a LinkedList che utilizza i puntatori verso il nodo successivo. Pertanto, quando si desidera cercare un elemento in un array è più veloce che fare iterazioni con LinkedList.

D'altra parte, l'inserimento e la cancellazione in una LinkedList sono molto più facili perché devi solo cambiare i puntatori mentre una ArrayList implica l'uso dell'operazione shift per qualsiasi inserimento o cancellazione.

Se hai frequenti operazioni di recupero nella tua app usa una ArrayList. Se si hanno frequenti inserimenti ed eliminazioni, utilizzare una LinkedList.

ArrayList e LinkedList entrambi implementano List interface e i loro metodi e risultati sono quasi identici. Tuttavia, ci sono alcune differenze tra loro che migliorano l'una rispetto all'altra a seconda del requisito.

ArrayList Vs LinkedList

1) Search: get(int index) l'operazione di ricerca è piuttosto veloce rispetto all'operazione di ricerca O(1). O(n) in Reason: fornisce le prestazioni di Deletion: mentre Inserts Performance: le prestazioni sono Memory Overhead:.

iterator listIterator mantiene il sistema basato sull'indice per i suoi elementi in quanto utilizza implicitamente la struttura dei dati dell'array che lo rende più veloce per la ricerca di un elemento nell'elenco. Dall'altro lato fail-fast implementa un elenco doppiamente collegato che richiede l'attraversamento di tutti gli elementi per la ricerca di un elemento.

2) iterator’s throw rimuovi operazione fornisce ConcurrentModificationException prestazioni mentre (O(1)) fornisce prestazioni variabili: ArrayList(O(n)) nel peggiore dei casi (durante la rimozione del primo elemento) e get method nel migliore dei casi (durante la rimozione dell'ultimo elemento ).

  

Conclusione: l'eliminazione dell'elemento LinkedList è più rapida rispetto a   ArrayList.

Motivo: LinkedList & # 8217; s ogni elemento mantiene due puntatori (indirizzi) che puntano a entrambi gli elementi vicini nell'elenco. Quindi la rimozione richiede solo la modifica della posizione del puntatore nei due nodi (elementi) vicini del nodo che verrà rimosso. Mentre in ArrayList è necessario spostare tutti gli elementi per riempire lo spazio creato dall'elemento rimosso.

3) Arraylist (O(1)) LinkedList (O(n)) aggiungi metodo fornisce <=> prestazioni mentre <=> fornisce <=> nel peggiore dei casi. Il motivo è lo stesso spiegato per la rimozione.

4) <=> <=> mantiene gli indici e i dati degli elementi mentre <=> conserva i dati degli elementi e due puntatori per i nodi vicini

  

quindi il consumo di memoria è relativamente elevato in LinkedList relativamente.

Esistono alcune somiglianze tra queste classi che sono le seguenti:

  • Sia ArrayList che LinkedList sono implementazioni dell'interfaccia Elenco.
  • Entrambi mantengono l'ordine di inserimento degli elementi, il che significa che durante la visualizzazione degli elementi ArrayList e LinkedList il set di risultati avrà lo stesso ordine in cui gli elementi sono stati inseriti nell'elenco.
  • Entrambe queste classi non sono sincronizzate e possono essere sincronizzate esplicitamente usando il metodo Collections.synchronizedList.
  • I <=> e <=> restituiti da queste classi sono <=> (se l'elenco viene modificato strutturalmente in qualsiasi momento dopo la creazione dell'iteratore, in qualsiasi modo, tranne attraverso i metodi di rimozione o aggiunta propri di <=>, il iteratore <=> a <=>).

Quando utilizzare LinkedList e quando utilizzare ArrayList?

  • Come spiegato sopra, le operazioni di inserimento e rimozione forniscono buone prestazioni <=> in <=> rispetto a <=>.
      

    Quindi, se c'è un requisito di frequente aggiunta e cancellazione nell'applicazione, allora LinkedList è la scelta migliore.

    • Le operazioni di ricerca (<=>) sono veloci in <=> ma non in <=>
      

    quindi Se ci sono meno operazioni di aggiunta e rimozione e più requisiti per le operazioni di ricerca, ArrayList sarebbe la soluzione migliore.

L'operazione get (i) in ArrayList è più veloce di LinkedList perché:
ArrayList: implementazione di array ridimensionabili dell'interfaccia Elenco
LinkedList: Implementazione di elenchi doppiamente collegati delle interfacce List e Deque

Le operazioni che indicizzano nell'elenco attraverseranno l'elenco dall'inizio o dalla fine, a seconda di quale sia il più vicino all'indice specificato.

1) Struttura dei dati sottostanti

La prima differenza tra ArrayList e LinkedList sta nel fatto che ArrayList è supportato da Array mentre LinkedList è supportato da LinkedList. Ciò comporterà ulteriori differenze nelle prestazioni.

2) LinkedList implementa Deque

Un'altra differenza tra ArrayList e LinkedList è che, oltre all'interfaccia List, LinkedList implementa anche l'interfaccia Deque, che fornisce le prime operazioni first-out per add () e poll () e diverse altre funzioni Deque. 3) Aggiunta di elementi in ArrayList L'aggiunta di elementi in ArrayList è un'operazione O (1) se non attiva la ridimensionamento di matrice, nel qual caso diventa O (log (n)), D'altra parte, aggiungendo un elemento in LinkedList è un'operazione O (1), in quanto non richiede alcuna navigazione.

4) Rimozione di un elemento da una posizione

Per rimuovere un elemento da un indice particolare, ad es. chiamando remove (indice), ArrayList esegue un'operazione di copia che lo rende vicino a O (n) mentre LinkedList deve attraversare quel punto che lo rende anche O (n / 2), poiché può attraversare da entrambe le direzioni in base alla prossimità .

5) Iterazione su ArrayList o LinkedList

Iterazione è l'operazione O (n) sia per LinkedList che per ArrayList in cui n è un numero di un elemento.

6) Recupero di un elemento da una posizione

L'operazione get (indice) è O (1) in ArrayList mentre O (n / 2) in LinkedList, poiché deve attraversare fino a quella voce. Tuttavia, nella notazione O grande O (n / 2) è solo O (n) perché ignoriamo le costanti lì.

7) Memoria

LinkedList utilizza un oggetto wrapper, Entry, che è una classe nidificata statica per l'archiviazione dei dati e due nodi successivi e precedenti mentre ArrayList archivia semplicemente i dati in array.

Quindi il requisito di memoria sembra inferiore nel caso di ArrayList rispetto a LinkedList, tranne nel caso in cui Array esegua l'operazione di ridimensionamento quando copia il contenuto da un array all'altro.

Se l'array è abbastanza grande, a quel punto potrebbe essere necessaria molta memoria e attivare la Garbage Collection, che può rallentare i tempi di risposta.

Da tutte le differenze di cui sopra tra ArrayList vs LinkedList, sembra che ArrayList sia la scelta migliore di LinkedList in quasi tutti i casi, tranne quando si esegue un'operazione add () frequente rispetto a remove () o get ().

È più semplice modificare un elenco collegato rispetto a ArrayList, soprattutto se si stanno aggiungendo o rimuovendo elementi dall'inizio o alla fine perché l'elenco collegato mantiene internamente i riferimenti di tali posizioni e sono accessibili in O (1).

In altre parole, non è necessario attraversare l'elenco collegato per raggiungere la posizione in cui si desidera aggiungere elementi, in tal caso l'addizione diventa un'operazione O (n). Ad esempio, inserendo o eliminando un elemento nel mezzo di un elenco collegato.

Secondo me, utilizzare ArrayList su LinkedList per la maggior parte dello scopo pratico in Java.

Sia remove () che insert () hanno un'efficienza di runtime di O (n) sia per ArrayLists che per LinkedLists. Tuttavia, il motivo del tempo di elaborazione lineare deriva da due motivi molto diversi:

In una ArrayList, si arriva all'elemento in O (1), ma in realtà la rimozione o l'inserimento di qualcosa lo rende O (n) perché tutti i seguenti elementi devono essere cambiati.

In un LinkedList, ci vuole O (n) per arrivare effettivamente all'elemento desiderato, perché dobbiamo iniziare dall'inizio fino a raggiungere l'indice desiderato. In realtà la rimozione o l'inserimento è costante, perché dobbiamo cambiare solo 1 riferimento per remove () e 2 riferimenti per insert ().

Quale dei due è più veloce per l'inserimento e la rimozione dipende da dove succede. Se siamo più vicini all'inizio, la LinkedList sarà più veloce, perché dobbiamo esaminare relativamente pochi elementi. Se siamo più vicini alla fine, un ArrayList sarà più veloce, perché ci arriveremo in tempo costante e dovremo solo cambiare i pochi elementi rimanenti che lo seguono. Se fatto esattamente nel mezzo, il LinkedList sarà più veloce perché passare attraverso n elementi è più veloce di spostare n valori.

Bonus: anche se non è possibile creare questi due metodi O (1) per una ArrayList, in realtà esiste un modo per farlo in LinkedLists. Supponiamo di voler esaminare l'intero Elenco rimuovendo e inserendo elementi lungo il nostro cammino. Di solito, inizieresti dall'inizio per ogni elemento usando il LinkedList, potremmo anche & Quot; save & Quot; l'elemento corrente a cui stiamo lavorando con un Iteratore. Con l'aiuto di Iterator, otteniamo un'efficienza O (1) per remove () e insert () quando lavoriamo in un LinkedList. Rendendolo l'unico vantaggio in termini di prestazioni, sono consapevole di dove un LinkedList è sempre meglio di un ArrayList.

ArrayList estende AbstractList e implementa l'interfaccia elenco. ArrayList è un array dinamico.
Si può dire che è stato sostanzialmente creato per ovviare agli svantaggi degli array

La classe LinkedList estende AbstractSequentialList e implementa l'interfaccia List, Deque e Queue.
Prestazioni
arraylist.get() è O (1) mentre linkedlist.get() è O (n)
arraylist.add() è O (1) e linkedlist.add() è 0 (1)
arraylist.contains() è O (n) e linkedlist.contains() è O (n)
arraylist.next() è O (1) e linkedlist.next() è O (1)
arraylist.remove() è O (n) mentre linkedlist.remove() è O (1)
Nell'arraylist
iterator.remove() è O (n)
mentre in elenco collegato
<=> è O (1)

Uno dei test che ho visto qui conduce il test solo una volta. Ma quello che ho notato è che è necessario eseguire questi test molte volte e alla fine i loro tempi convergeranno. Fondamentalmente la JVM deve riscaldarsi. Per il mio caso d'uso specifico, dovevo aggiungere / rimuovere gli articoli fino a un massimo che aumenta a circa 500 articoli. Nei miei test LinkedList è uscito più velocemente, con i ArrayList collegati che arrivano a circa 50.000 NS e <=> che arrivano a circa 90.000 NS ... dai o dai. Vedi il codice qui sotto. 

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;
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top