util - using linked list in java




Quando utilizzare LinkedList su ArrayList in Java? (20)

Sono sempre stato uno da usare semplicemente:

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

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

Quando deve essere utilizzato LinkedList su ArrayList e viceversa?


È una questione 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 entrambe le estremità, e particolarmente lento da eliminare nel mezzo.

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


1) Ricerca: l' operazione di ricerca ArrayList è piuttosto veloce rispetto all'operazione di ricerca LinkedList. get (int index) in ArrayList fornisce le prestazioni di O (1) mentre le prestazioni di LinkedList sono O (n).

Motivo: ArrayList mantiene un sistema basato sugli indici per i suoi elementi poiché utilizza la struttura dei dati dell'array implicitamente, il che rende più veloce la ricerca di un elemento nell'elenco. Dall'altro lato, LinkedList implementa una lista doppiamente collegata che richiede l'attraversamento di tutti gli elementi per la ricerca di un elemento.

2) Cancellazione: l' operazione di rimozione di LinkedList fornisce prestazioni O (1) mentre ArrayList offre prestazioni variabili: O (n) nel peggiore dei casi (rimuovendo il primo elemento) e O (1) nel migliore dei casi (Durante la rimozione dell'ultimo elemento) .

Conclusione: la cancellazione dell'elemento LinkedList è più veloce rispetto a ArrayList.

Motivo: ciascuno degli elementi di LinkedList mantiene due puntatori (indirizzi), che puntano a entrambi gli elementi vicini nell'elenco. Quindi la rimozione richiede solo una modifica della posizione del puntatore nei due nodi (elementi) vicini del nodo che verrà rimosso. Mentre In ArrayList tutti gli elementi devono essere spostati per riempire lo spazio creato dall'elemento rimosso.

3) Inserti Performance: il metodo di aggiunta LinkedList fornisce prestazioni O (1) mentre ArrayList fornisce O (n) nel peggiore dei casi. Il motivo è lo stesso spiegato per rimuovere.

4) Memory Overhead: ArrayList mantiene indici e dati degli elementi mentre LinkedList mantiene i dati degli elementi e due puntatori per i nodi vicini, quindi il consumo di memoria è elevato in LinkedList relativamente.

Ci sono 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 avrebbe lo stesso ordine in cui gli elementi sono stati inseriti nell'Elenco. Entrambe queste classi non sono sincronizzate e possono essere sincronizzate esplicitamente utilizzando il metodo Collections.synchronizedList. L'iteratore e l'elencoIterator restituiti da queste classi sono fail-fast (se l'elenco viene modificato strutturalmente in qualsiasi momento dopo la creazione dell'iteratore, in qualsiasi modo tranne che attraverso i metodi di rimozione o aggiunta dell'iteratore, l'iteratore genererà una ConcurrentModificationException).

Quando utilizzare LinkedList e quando utilizzare ArrayList?

1) Come spiegato sopra, le operazioni di inserimento e rimozione forniscono buone prestazioni (O (1)) in LinkedList rispetto a ArrayList (O (n)). Quindi, se c'è un'obbligo di frequenti aggiunte e cancellazioni in un'applicazione, LinkedList è la scelta migliore.

2) Le operazioni di ricerca (ottenere metodo) sono veloci in ArrayList (O (1)) ma non in LinkedList (O (n)), quindi se ci sono meno operazioni di aggiunta e rimozione e più requisiti di ricerca, ArrayList sarebbe la soluzione migliore.


Corretto o errato: esegui il test in locale e decidi tu stesso!

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

ArrayList , supportato da Array , che deve essere il doppio della dimensione, è peggio nell'applicazione di grandi volumi.

Di seguito è riportato il risultato del test unitario per ciascuna operazione. Il calcolo è dato 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);
    }
}

Finora, nessuno sembra aver affrontato l'impronta di memoria di ognuna di queste liste oltre al consenso generale sul fatto che una LinkedList è "molto più" di una ArrayList quindi ho fatto un po 'di numeri crunch per dimostrare esattamente quanto entrambe le liste occupano per N riferimenti nulli .

Dato che i riferimenti sono 32 o 64 bit (anche quando null) sui loro sistemi relativi, ho incluso 4 set di dati per LinkedLists 32 e 64 bit e ArrayLists .

Nota: le dimensioni mostrate per le righe ArrayList sono per gli elenchi tagliati . In pratica, la capacità dell'array di supporto in un oggetto ArrayList è generalmente maggiore del suo numero di elementi corrente.

Nota 2: (grazie a BeeOnRope) Poiché CompressedOops ora è predefinito da metà JDK6 e versioni successive, i valori seguenti per le macchine a 64 bit corrisponderanno sostanzialmente alle loro controparti a 32 bit, a meno che, ovviamente, non venga disattivato.

Il risultato mostra chiaramente che LinkedList è molto più di ArrayList , specialmente con un numero di elementi molto alto. Se la memoria è un fattore, evitare di LinkedLists .

Le formule che ho usato seguono, fammi sapere se ho fatto qualcosa di sbagliato e lo aggiusterò. 'b' è 4 o 8 per sistemi a 32 o 64 bit, e 'n' è il numero di elementi. Nota il motivo per le mod è perché tutti gli oggetti in java occuperanno più di 8 byte spazio indipendentemente dal fatto che sia tutto usato o meno.

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)

ArrayList è ciò che desideri. LinkedList è quasi sempre un bug (di prestazioni).

Perché LinkedList schifo:

  • Utilizza molti piccoli oggetti di memoria e quindi influisce sulle prestazioni lungo il processo.
  • Un sacco di piccoli oggetti fanno male alla cache-locality.
  • Qualsiasi operazione indicizzata richiede un attraversamento, cioè ha prestazioni O (n). Questo non è ovvio nel codice sorgente, il che porta ad algoritmi O (n) più lenti di quando è stato usato ArrayList .
  • Ottenere buone prestazioni è complicato.
  • Anche quando le prestazioni di big-O sono le stesse di ArrayList , probabilmente sarà comunque molto più lento.
  • È sconcertante vedere LinkedList in source perché probabilmente è la scelta sbagliata.

ArrayList è essenzialmente un array. LinkedList è implementato come un doppio elenco collegato.

Il risultato è abbastanza chiaro. O (1) per ArrayList , perché ArrayList consente l'accesso casuale usando l'indice. O (n) per LinkedList , perché ha bisogno di trovare prima l'indice. Nota: ci sono diverse versioni di add e remove .

LinkedList è più veloce in add e remove, ma più lento in get. In breve, LinkedList dovrebbe essere preferito se:

  1. non ci sono molti accessi casuali di elementi
  2. ci sono un gran numero di operazioni di aggiunta / rimozione

=== ArrayList ===

  • aggiungi (E e)
    • aggiungi alla fine di ArrayList
    • richiede un costo di ridimensionamento della memoria.
    • O (n) peggio, O (1) ammortizzato
  • aggiungi (indice int, elemento E)
    • aggiungi a una posizione specifica dell'indice
    • richiedono il cambio e il possibile ridimensionamento della memoria
    • Sopra)
  • rimuovere (int index)
    • rimuovere un elemento specificato
    • richiedono il cambio e il possibile ridimensionamento della memoria
    • Sopra)
  • rimuovi (oggetto o)
    • rimuovere la prima occorrenza dell'elemento specificato da questo elenco
    • è necessario cercare prima l'elemento, quindi spostare e il possibile ridimensionamento della memoria
    • Sopra)

=== LinkedList ===

  • aggiungi (E e)

    • aggiungere alla fine della lista
    • O (1)
  • aggiungi (indice int, elemento E)

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

Ecco una figura di programcreek.com ( add e remove sono il primo tipo, ovvero aggiungi un elemento alla fine dell'elenco e rimuovi l'elemento nella posizione specificata nell'elenco.):


ArrayListe LinkedListentrambi gli strumenti, i List interfaceloro metodi e risultati sono quasi identici. Tuttavia ci sono poche differenze tra loro che rendono l'uno migliore rispetto ad un altro a seconda del requisito.

ArrayList Vs LinkedList

1) l' Search: ArrayListoperazione di ricerca è piuttosto veloce rispetto all'operazione di LinkedListricerca. get(int index)in ArrayListdà le prestazioni di O(1)mentre la LinkedListprestazione è O(n).

Reason: ArrayListmantiene il sistema basato sugli indici per i suoi elementi poiché utilizza la struttura dei dati dell'array implicitamente, il che rende più veloce la ricerca di un elemento nell'elenco. Dall'altra parte LinkedListimplementa una lista doppiamente collegata che richiede l'attraversamento di tutti gli elementi per la ricerca di un elemento.

2) l' Deletion: LinkedListoperazione di rimozione fornisce O(1)prestazioni mentre ArrayListfornisce prestazioni variabili: O(n)nel peggiore dei casi (durante la rimozione del primo elemento) e O(1)nel migliore dei casi (durante la rimozione dell'ultimo elemento).

Conclusione: la cancellazione dell'elemento LinkedList è più veloce rispetto a ArrayList.

Motivo: ciascun elemento di LinkedList mantiene due puntatori (indirizzi) che puntano a entrambi gli elementi vicini nell'elenco. Quindi la rimozione richiede solo una modifica nella posizione del puntatore nei due nodi (elementi) vicini del nodo che verrà rimosso. Mentre In ArrayList tutti gli elementi devono essere spostati per riempire lo spazio creato dall'elemento rimosso.

3) Inserts Performance: LinkedListaggiungi metodo dà O(1)prestazioni mentre ArrayListO(n)nel peggiore dei casi. La ragione è la stessa spiegata per la rimozione.

4) Memory Overhead: ArrayListmantiene indici e dati degli elementi mentre LinkedListmantiene i dati degli elementi e due puntatori per i nodi vicini

quindi il consumo di memoria è elevato in LinkedList relativamente.

Ci sono alcune somiglianze tra queste classi che sono le seguenti:

  • Sia ArrayList che LinkedList sono l'implementazione 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 avrebbe lo stesso ordine in cui gli elementi sono stati inseriti nell'Elenco.
  • Entrambe queste classi non sono sincronizzate e possono essere sincronizzate esplicitamente utilizzando il metodo Collections.synchronizedList.
  • Le iteratore listIteratorrestituite da queste classi sono fail-fast(se l'elenco viene modificato strutturalmente in qualsiasi momento dopo la creazione dell'iteratore, in ogni caso tranne che attraverso i iterator'spropri metodi di rimozione o aggiunta, l'iteratore sarà throwa ConcurrentModificationException).

Quando utilizzare LinkedList e quando utilizzare ArrayList?

  • Come spiegato sopra l'inserto e rimuovere operazioni forniscono buone prestazioni (O(1))in LinkedListconfronto a ArrayList(O(n)).

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

  • Le operazioni di ricerca ( get method) sono veloci Arraylist (O(1))ma non attiveLinkedList (O(n))

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


1) Struttura dei dati sottostanti

La prima differenza tra ArrayList e LinkedList deriva dal fatto che ArrayList è supportato da Array mentre LinkedList è supportato da LinkedList. Ciò porterà a 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 prima le prime operazioni per add () e poll () e diverse altre funzioni Deque. 3) Aggiunta di elementi in ArrayList L'aggiunta di elementi in ArrayList è l'operazione O (1) se non attiva la ridimensionamento della 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 esempio chiamando remove (index), 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) , in quanto può attraversare da entrambe le direzioni in base alla prossimità.

5) Iterating su ArrayList o LinkedList

Iterazione è l'operazione O (n) per LinkedList e ArrayList dove n è un numero di un elemento.

6) Recupero 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. Però, in Big O notation 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 successivo e precedente mentre ArrayList memorizza solo i dati nell'array.

Pertanto, 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 una matrice a un'altra.

Se la matrice è sufficientemente grande, potrebbe richiedere molto spazio di memoria e attivare la raccolta dei dati inutili, che può rallentare i tempi di risposta.

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

È più semplice modificare un elenco collegato rispetto a ArrayList, soprattutto se si aggiungono o rimuovono elementi dall'inizio o fine perché l'elenco collegato conserva 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'aggiunta diventa operazione O (n). Ad esempio, inserire o eliminare un elemento nel mezzo di un elenco collegato.

A mio parere, usa ArrayList su LinkedList per la maggior parte degli scopi pratici in Java.


TL, DR a causa della moderna architettura dei computer, ArrayListsarà significativamente più efficiente per quasi tutti i casi d'uso possibili - e quindi LinkedListdovrebbe essere evitato tranne alcuni casi davvero unici ed estremi.

In teoria, LinkedList ha una O (1) per il 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 Cache Hostile Data. Dalla performance POV - ci sono pochissimi casi in cui LinkedListpotrebbe essere più performante rispetto alla cache ArrayList .

Ecco i risultati di un test di riferimento che inserisce elementi in posizioni casuali. Come si può vedere - la lista di array se molto più efficiente, anche se in teoria ogni inserto nel mezzo della lista richiederà "spostare" il n successivi elementi della matrice (valori più bassi sono migliori):

Lavorando su hardware di ultima generazione (cache più grandi e più efficienti), i risultati sono ancora più convincenti:

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

Ci sono due ragioni principali per questo:

  1. Principalmente - che i nodi del LinkedListsono sparsi casualmente attraverso la memoria. RAM ("Random Access Memory") non è realmente casuale e i blocchi di memoria devono essere recuperati nella cache. Questa operazione richiede tempo e quando tali intervalli si verificano frequentemente - le pagine di memoria nella cache devono essere continuamente sostituite -> Cache mancate -> La cache non è efficiente. ArrayListgli elementi sono memorizzati nella memoria continua, il che è esattamente l'ottimizzazione della moderna architettura della CPU.

  2. Secondario LinkedList richiesto per trattenere / inoltrare i puntatori, che significa 3 volte il consumo di memoria per valore memorizzato rispetto a ArrayList.

DynamicIntArray , btw, è una implementazione di ArrayList personalizzata Int(tipo primitivo) e non Objects - quindi tutti i dati sono archiviati in modo DynamicIntArray adiacenti - quindi ancora più efficienti.

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 400 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

Per rendere ancora più chiaro il punto, controlla il benchmark dell'aggiunta di elementi all'inizio della lista. Questo è un caso d'uso in cui, in teoria, LinkedListdovrebbe davvero brillare, e ArrayListdovrebbe presentare risultati pessimi o addirittura peggio:

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

La copia di una massa sequenziale di memoria è un'operazione ottimizzata dalle moderne CPU, che modifica la teoria e rende effettivamente, ancora una volta, ArrayList/ Vectormolto più efficiente

Crediti: tutti i benchmark pubblicati qui sono creati da Kjell Hedström . Ancora più dati possono essere trovati sul suo blog


ArrayList e LinkedList hanno i loro pro e contro.

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

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

Se hai frequenti operazioni di recupero nella tua app usa un ArrayList. Se hai frequenti inserimenti e cancellazioni usa una LinkedList.


Dipende da quali operazioni farai di più sulla lista.

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 parli della differenza tra array e liste collegate.


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

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

Il mio fondamento logico è che, poiché è impossibile sapere esattamente quanti risultati ottengo, non ci sarà memoria sprecata (come in ArrayList con la differenza tra la capacità e il numero effettivo di elementi), e non ci sarebbe tempo perso a cercare di duplicare la capacità.

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


ArrayList estende AbstractList e implementa l'interfaccia List. ArrayList è una matrice dinamica.
Si può dire che è stato fondamentalmente creato per superare gli svantaggi degli array.

La classe LinkedList estende AbstractSequentialList e implementa l'interfaccia List, Deque e Queue.
Prestazione
arraylist.get()è O (1) mentre linkedlist.get()è O (n)
arraylist.add()è O (1) ed linkedlist.add()è 0 (1)
arraylist.contains()è O (n) ed linkedlist.contains()è O (n)
arraylist.next()è O (1) ed linkedlist.next()è O (1)
arraylist.remove()è O (n) mentre linkedlist.remove()è O (1)
In arraylist
iterator.remove()è O (n)
mentre in linkedlist
iterator.remove()è O (1)


Ecco la notazione O-grande sia ArrayListed LinkedListe anche CopyOnWrite-ArrayList:

Lista di array

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

Lista collegata

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)

Sulla base di questi devi decidere cosa scegliere. :)


Oltre agli altri argomenti validi sopra, dovresti notare l' interfaccia degli ArrayListattrezzi RandomAccess, mentre gli LinkedListattrezzi Queue.

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


Se il tuo codice ha add(0)e remove(0), usa un LinkedListed è più carino addFirst()e removeFirst()metodi. 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 questo LinkedListstrumento Deque. Basta guardare i metodi in Deque(e Queue); se si desidera un confronto equo, provare a eseguire LinkedListcontro ArrayDequee fare un confronto funzione per funzionalità.


Un elenco di array è essenzialmente una matrice con metodi per aggiungere elementi, ecc. (E dovresti invece utilizzare una lista generica). È una raccolta di elementi a cui è possibile accedere tramite un indicizzatore (ad esempio [0]). Implica una progressione da un oggetto all'altro.

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


Uno dei test che ho visto qui conduce solo una volta il test. Ma quello che ho notato è che devi eseguire questi test molte volte e alla fine i loro tempi convergeranno. Fondamentalmente la JVM ha bisogno di riscaldarsi. Per il mio caso d'uso particolare, avevo bisogno di aggiungere / rimuovere elementi a un ultimo che aumentasse a circa 500 articoli. Nei miei test LinkedListè uscito più veloce, con link che LinkedListarrivavano a circa 50.000 NS e ArrayListarrivavano a circa 90.000 NS ... dare o prendere. Guarda 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;
}





linked-list