Quando usare LinkedList su ArrayList in Java?

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

Poiché i riferimenti sono a 32 o 64 bit (anche quando null) sui loro sistemi relativi, 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 tagliati - In pratica, la capacità dell'array di supporto in un ArrayList è generalmente maggiore del numero di elementi corrente.

Nota 2: (grazie BeeOnRope) Poiché CompressedOops è predefinito ora da metà JDK6 in su, i valori sottostanti per le macchine a 64 bit corrisponderanno sostanzialmente alle loro controparti a 32 bit, a meno che ovviamente non lo si spenga specificamente.

Il risultato mostra chiaramente che LinkedList è un insieme 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 sistemerò. '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 un multiplo di 8 byte di spazio indipendentemente dal fatto che sia tutto utilizzato o non.

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 e ' quello che vuoi. LinkedList è quasi sempre un bug (prestazioni).

Perché LinkedList fa schifo:

• Utilizza molti piccoli oggetti di memoria e quindi influisce sulle prestazioni in tutto il processo.
• Molti piccoli oggetti sono dannosi per la località della cache.
• Qualsiasi operazione indicizzata richiede un attraversamento, cioè ha prestazioni O(n). Questo non è ovvio nel codice sorgente, portando ad algoritmi O (n) più lento di se ArrayList è stato utilizzato.
• Ottenere buone prestazioni è ingannevole.
• Anche quando le prestazioni di big-O sono le stesse di ArrayList, probabilmente sarà comunque significativamente più lento.
• È stridente vedere LinkedList nella fonte perché probabilmente è la scelta sbagliata.

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

Allo stesso modo, è possibile ottenere un throughput migliore in un'app dal garbage collector di throughput predefinito, ma una volta ottenute le app java con heap da 10 GB, è possibile bloccare l'app per 25 secondi durante un GCS completo che causa timeout e errori nelle app SOA e fa saltare gli SLA se si verifica troppo spesso. Anche se il raccoglitore CMS richiede più risorse e non raggiunge lo stesso throughput grezzo, è molto meglio scelta perché ha latenza più prevedibile e più piccola.

ArrayList è solo una scelta migliore per le prestazioni se tutto ciò che intendi per prestazioni è il throughput e puoi ignorare la latenza. Nella mia esperienza nel mio lavoro non posso ignorare la latenza del 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: Notazione Big-Oh

ArrayLists sono buoni per write-once-read-many o appenders, ma cattivi per aggiungere/rimuovere dalla parte anteriore o centrale.

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

LinkedList è quasi sempre la scelta sbagliata, in termini di prestazioni. Ci sono alcuni algoritmi molto specifici in cui viene richiesto un LinkedList, ma quelli sono molto, molto rari e l'algoritmo di solito dipenderà specificamente dalla capacità di LinkedList di inserire ed eliminare elementi nel mezzo dell'elenco in modo relativamente rapido, una volta che hai navigato lì con un ListIterator.

Ce n'è uno caso d'uso comune in cui LinkedList supera ArrayList: quello di una coda. Tuttavia, se il tuo obiettivo è prestazioni, invece di LinkedList dovresti anche considerare l'utilizzo di ArrayBlockingQueue (se puoi determinare un limite superiore sulla dimensione della coda in anticipo e puoi permetterti di allocare tutta la memoria in anticipo), o questa Implementazione CircularArrayList. (Sì, è del 2001, quindi dovrai generificarlo, ma ho rapporti di prestazioni paragonabili a quelli citati nell'articolo ora in una JVM recente)

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

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

Corretto o errato: Si prega di eseguire il test a livello locale e decidere per te!

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

ArrayList, sostenuta da Array, che deve essere il doppio della dimensione, è peggio in applicazioni di grandi volumi.

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

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

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

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

1. non ci sono un gran numero di accesso casuale di elemento
2. esiste un gran numero di operazioni di aggiunta/rimozione

=== Elenco degli array ===

• aggiungere (E e)
  • aggiungi alla fine di ArrayList
  • richiede il costo di ridimensionamento della memoria.
  • O(n) peggiore, O(1) ammortizzato
• aggiungi (indice int, elemento E)
  • aggiungi a una posizione specifica dell'indice
  • richiede lo spostamento e il possibile costo di ridimensionamento della memoria
  • O (n)
• rimuovere (int indice)
  • rimuove un elemento specificato
  • richiede lo spostamento e il 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 e ridimensionare la memoria possibile
  • O (n)

=== Elenco collegamenti ===

• Aggiungere (E e)

  • aggiungere al fine dell'elenco
  • O (1)

• Aggiungi (indice int, elemento E)

  • inserire nella posizione specificata
  • bisogno di trovare la posizione prima
  • O (n)
• rimuovere()
  • rimuove il primo elemento dell'elenco
  • O (1)
• rimuovi(indice int)
  • rimuove l'elemento con l'indice specificato
  • devi prima trovare l'elemento
  • O (n)
• rimuovi (Oggetto o)
  • rimuove la prima occorrenza dell'elemento specificato
  • devi prima trovare l'elemento
  • O (n)

Ecco una figura da programcreek.com (add e remove sono il primo tipo, cioè aggiungere un elemento alla fine dell'elenco e rimuovere l'elemento nella posizione specificata nell'elenco.):

ArrayList è accessibile in modo casuale, mentre LinkedList è davvero economico per espandere e rimuovere elementi da. Per la maggior parte dei casi, ArrayList 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.

1) Search: 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 su 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, LinkedList implementa una lista doppiamente collegata che richiede l'attraversamento attraverso tutti gli elementi per la ricerca di un elemento.

2) Eliminazione: L'operazione di rimozione LinkedList fornisce prestazioni O(1) mentre ArrayList fornisce 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 ad ArrayList.

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

3) Inserti Prestazioni: LinkedList add metodo dà O(1) prestazioni mentre ArrayList dà O(n) nel peggiore dei casi. Il motivo è lo stesso spiegato per rimuovere.

4) Memoria Overhead: ArrayList mantiene gli indici e i 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 poche somiglianze tra queste classi che sono le seguenti:

Sia ArrayList che LinkedList sono implementazioni dell'interfaccia List. Entrambi mantengono l'ordine di inserimento degli elementi il che significa che durante la visualizzazione degli elementi ArrayList e LinkedList il risultato set 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 le Raccolte.Metodo synchronizedList. L'iteratore e l'listiteratore 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 attraverso i metodi remove o add dell'iteratore, l'iteratore genererà un ConcurrentModificationException).

Quando usare LinkedList e quando usare ArrayList?

1) Come spiegato sopra le operazioni di inserimento e rimozione danno buone prestazioni (O(1)) in LinkedList rispetto a ArrayList(O(n)). Quindi, se c'è un requisito di frequente aggiunta e cancellazione in un'applicazione, LinkedList è la scelta migliore.

2) Le operazioni di ricerca (metodo get) sono veloci in ArrayList (O(1)) ma non in LinkedList(O (n)) quindi se ci sono meno add e rimuovere le operazioni e più operazioni di ricerca requisito, ArrayList sarebbe la soluzione migliore.

Joshua Bloch, l'autore di LinkedList:

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

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

Mi dispiace per la risposta per non essere così informativo come le altre risposte, ma ho pensato che sarebbe stato il più interessante e auto-esplicativo.

So che questo è un vecchio post, ma onestamente non posso credere che nessuno abbia menzionato che LinkedList implementa Deque. Basta guardare i metodi in Deque (e Queue); se si desidera un confronto equo, provare a eseguire LinkedList contro ArrayDeque e fare un confronto feature-for-feature.

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

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

Ecco la notazione Big-O sia 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)

CopyOnWrite-ArrayList

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

Sulla base di questi si deve decidere cosa scegliere. :)

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

1. Attuazione

ArrayList è l'implementazione dell'array ridimensionabile dell'interfaccia list, mentre

LinkedList è l'implementazione della lista doppiamente collegata dell'interfaccia elenco.

2. Prestazioni

• Get (indice int) o operazione di ricerca

  L'operazione ArrayList get(int index) viene eseguita in tempo costante, ovvero O (1) mentre

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

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

  LinkedList non fornisce l'accesso basato su indice per i suoi elementi in quanto itera dall'inizio o dalla fine (a seconda di quale sia più vicino) per recuperare il nodo all'indirizzo specificato indice elemento.

• Operazione Inserisci() o aggiungi(Oggetto)

  Gli inserimenti in LinkedList sono generalmente veloci come confronto con ArrayList. In LinkedList l'aggiunta o l'inserimento è l'operazione O(1).

  Mentre in ArrayList , se l'array è il caso peggiore, c'è un costo aggiuntivo per ridimensionare l'array e copiare gli elementi nel nuovo array, il che rende il runtime dell'operazione add in ArrayList O (n), altrimenti è O (1).

• Operazione di rimozione(int)

  L'operazione di rimozione in LinkedList è generalmente la stessa di ArrayList cioè 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 in tempo costante O (1). L'altro metodo di rimozione sovraccarico 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 ha trovato l'oggetto e scollegarlo dall'elenco originale. Quindi questo metodo runtime è O (n).

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

3. Iteratore inverso

LinkedList può essere iterato in direzione inversa usando descendingIterator () mentre

Non esiste descendingIterator() in ArrayList , quindi abbiamo bisogno di scrivere il nostro codice per iterare su ArrayList in direzione inversa.

4. Capacità iniziale

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

LinkedList costruisce solo la lista vuota senza alcuna capacità iniziale.

5. Sovraccarico di memoria

Il sovraccarico di memoria in LinkedList è più rispetto ad ArrayList come nodo in LinkedList deve mantenere gli indirizzi del nodo successivo e precedente. Mentre

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

Fonte

In aggiunta agli altri buoni argomenti di cui sopra, si dovrebbe notare ArrayList implementa RandomAccess interfaccia, mentre LinkedList implementa Queue.

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

Vedere le implementazioni Java Tutorial - List .

Un elenco di array è essenzialmente un array con metodi per aggiungere elementi, ecc. (e dovresti usare invece 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 all'altro (Elemento a -> elemento b). È possibile ottenere lo stesso effetto con un elenco di array, ma un elenco collegato dice assolutamente quale elemento dovrebbe seguire il precedente.

Dipende da quali operazioni farai di più nella Lista.

ArrayList è più veloce 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 e liste collegate.

Ho letto le risposte, ma c'è uno scenario in cui uso sempre un LinkedList su un 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 uso sempre un LinkedList.

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

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

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

Importante : Per Java il suo LinkedList questo non è vero! Vedi Esiste un metodo concat veloce per la lista collegata in Java?

L'operazione get (i) in ArrayList è più veloce di LinkedList, perché:
ArrayList: Implementazione di array ridimensionabili dell'interfaccia List
LinkedList: Implementazione della lista doppiamente collegata delle interfacce List e Deque

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

ArrayList e LinkedList entrambi implementa List interface e i loro metodi e risultati sono quasi identici. Tuttavia ci sono poche differenze tra loro che rendono uno migliore rispetto ad un altro a seconda del requisito.

ArrayList Vs LinkedList

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

Reason: ArrayList mantiene il sistema basato su indice per il suo 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 LinkedList implementa una lista doppiamente collegata che richiede l'attraversamento di tutti gli elementi per la ricerca di un elemento.

2) Deletion: LinkedList l'operazione di rimozione fornisce prestazioni O(1) mentre ArrayList fornisce 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: ogni elemento di LinkedList 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 vicini (elementi) 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: LinkedList aggiungi metodo dà O(1) prestazioni mentre ArrayList dà O(n) nel peggiore dei casi. La ragione è la stessa spiegata per rimuovere.

4) Memory Overhead: ArrayList mantiene gli indici e i 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 poche somiglianze tra queste classi che sono le seguenti:

• Sia ArrayList che LinkedList sono l'implementazione di List interfaccia.
• 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 le Raccolte.Metodo synchronizedList.
• Le iterator e listIterator restituite da queste classi sono fail-fast (se la lista è strutturalmente modificata in qualsiasi momento dopo la l'iteratore viene creato, in qualsiasi modo tranne attraverso i metodi iterator’s remove o add, l'iteratore throw a ConcurrentModificationException).

Quando usare LinkedList e quando usare ArrayList?

• Come spiegato sopra le operazioni di inserimento e rimozione danno buone prestazioni (O(1)) in LinkedList rispetto a ArrayList(O(n)).

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

• Ricerca (get method) le operazioni 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 operazioni di ricerca, ArrayList sarebbe la soluzione migliore.

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. Quindi, quando vuoi cercare un elemento in un ArrayList è più veloce di fare n iterazioni con LinkedList.

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

Se hai frequenti operazioni di recupero nella tua app usa un ArrayList. Se hai frequenti inserimenti ed eliminazioni usa un LinkedList.

1) Struttura dati sottostante

La prima differenza tra ArrayList e LinkedList deriva dal fatto che ArrayList è supportato da Array mentre LinkedList è supportato da LinkedList. Ciò porterà ad 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 first in first out operazioni per add() e poll () e diverse altre funzioni Deque. 3) Aggiunta di elementi in ArrayList L'aggiunta di elementi in ArrayList è O(1) operazione se non attiva la ridimensionamento dell'array, nel qual caso diventa O(log(n)), D'altra parte, l'aggiunta di un elemento in LinkedList è O(1) operazione, in quanto non richiede alcuna navigazione.

4) Rimozione di un elemento da una posizione

Per rimuovere un elemento da un particolare indice, 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 vicinanza.

5) Iterazione su ArrayList o LinkedList

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

6) Recupero dell'elemento da una posizione

L'operazione get(index) è O (1) in ArrayList mentre il suo O (n / 2) in LinkedList, in quanto deve attraversare fino a quella voce. Tuttavia, nella notazione Big O 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 la memorizzazione dei dati e due nodi next e previous mentre ArrayList memorizza solo i dati in Array.

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

Se l'array è abbastanza grande potrebbe richiedere molta memoria a quel punto e attivare la Garbage collection, che può rallentare il tempo 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 esegue un'operazione add() frequente rispetto a remove () o get().

È più semplice modificare un elenco collegato rispetto ad ArrayList, specialmente se aggiunta o rimozione di elementi dall'inizio o dalla fine perché l'elenco collegato mantiene internamente i riferimenti di tali posizioni e sono accessibili in tempo 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, l'inserimento o l'eliminazione di un elemento nel mezzo di un elenco collegato.

A mio parere, 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 Linkedlist. Tuttavia, la ragione dietro il tempo di elaborazione lineare deriva da due ragioni molto diverse:

In un 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 modificati.

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

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

Bonus: Mentre non c'è modo di rendere questi due metodi O(1) per un ArrayList, c'è in realtà un modo per farlo in LinkedLists. Diciamo che vogliamo passare attraverso l'intera lista rimuovendo e inserendo elementi sulla nostra strada. Di solito, inizieresti dall'inizio per ogni elemento usando il LinkedList, potremmo anche "salvare" l'elemento corrente su cui stiamo lavorando con un Iteratore. Con l'aiuto dell'iteratore, otteniamo un'efficienza O(1) per remove() e insert() quando si lavora in una LinkedList. Rendendolo l'unico vantaggio in termini di prestazioni di cui sono a conoscenza, dove un LinkedList è sempre migliore di un ArrayList.

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

La classe LinkedList estende AbstractSequentialList e implementa l'interfaccia List, Deque e Queue.
Prestazioni
arraylist.get() è O(1) considerando che linkedlist.get() è O(n)
arraylist.add() è O(1) e linkedlist.add() è 0(1)
arraylist.contains() è O(n) linkedlist.contains() è O(n)
arraylist.next() è O(1) e linkedlist.next() è O(1)
arraylist.remove() è O(n) considerando che linkedlist.remove() è O (1)
In arraylist
iterator.remove() è O (n)
mentre in linkedlist
iterator.remove()è 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 particolare avevo bisogno di aggiungere/rimuovere elementi a un ultimo che cresce fino a circa 500 elementi. Nei miei test LinkedList è uscito più velocemente, con linked LinkedList che arriva a circa 50.000 NS e ArrayList che arriva a circa 90.000 NS... piu ' o meno. 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;
}

Quando dovrei usare LinkedList? Quando si lavora principalmente con pile o quando si lavora con buffer. Quando dovrei usare ArrayList? Solo quando si lavora con gli indici, altrimenti è possibile utilizzare HashTable con elenco collegato, quindi si ottiene:

Tabella hash + elenco collegato

• Accesso tramite chiave O (1),
• Inserire per tasto O (1),
• Rimuovere dal tasto O (1)
• e c'è un trucco per implementare RemoveAll / SetAll con O(1) quando si utilizza controllo delle versioni

Sembra una buona soluzione, e nella maggior parte dei casi lo è, come mai dovresti sapere: HashTable richiede molto spazio su disco, quindi quando è necessario gestire l'elenco di 1.000.000 di elementi può diventare una cosa importante. Questo può accadere nelle implementazioni del server, nei client è raramente il caso.

Date anche un'occhiata a Rosso-Nero-Albero

• Accesso casuale Log (n),
• Inserire Log (n),
• Rimuovere Registro(n)