Quando usare LinkedList su ArrayList in Java?
Sono sempre stato uno da usare semplicemente:
List<String> names = new ArrayList<>();
Uso 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 sopra ArrayList
e viceversa?
30 answers
Sommario ArrayList
con ArrayDeque
sono preferibili in molto più casi d'uso di LinkedList
. Se non sei sicuro, inizia con ArrayList
.
LinkedList
e ArrayList
sono due diverse implementazioni dell'interfaccia List. LinkedList
lo implementa con una lista doppiamente collegata. ArrayList
lo implementa con un array di ridimensionamento dinamico.
Come per le operazioni standard di elenco e array collegati, i vari metodi avranno runtime algoritmici diversi.
Anziché LinkedList<E>
-
get(int index)
è O (n) (con n/4 passi in media) -
add(E element)
è O (1) -
add(int index, E element)
è O (n) (con n/4 passi in media), ma O (1) quandoindex = 0
LinkedList<E> -
remove(int index)
è O (n) (con n/4 passi in media) -
Iterator.remove()
è O (1) . LinkedList<E> -
ListIterator.add(E element)
è O (1) Questo è uno dei principali vantaggi diLinkedList<E>
Nota: molte delle operazioni richiedono n/4 passi in media, costante numero di passi nel caso migliore (ad esempio index = 0) e n/2 passi nel caso peggiore (al centro dell'elenco)
Anziché ArrayList<E>
-
get(int index)
è O(1) ArrayList<E> -
add(E element)
è O(1)ammortizzato, ma O(n) nel peggiore dei casi poiché l'array deve essere ridimensionato e copiato -
add(int index, E element)
è O (n) (con n/2 passi in media) -
remove(int index)
è O (n) (con n/2 passi in media) -
Iterator.remove()
è O (n) (con n/2 passi in media) -
ListIterator.add(E element)
è O (n) (con n/2 passi in media)
Nota: molte delle operazioni richiedono n/2 passi in media, costante numero di passi nel migliore dei casi (fine dell'elenco), n passi nel caso peggiore (inizio elenco)
LinkedList<E>
consente inserimenti o rimozioni a tempo costante utilizzando iteratori , ma solo accesso sequenziale di elementi. In altre parole, si può camminare l'elenco in avanti o indietro, ma trovare una posizione nella lista richiede tempo proporzionale alla dimensione della lista. Javadoc dice "le operazioni che indicizzano nell'elenco attraverseranno l'elenco dall'inizio o dalla fine, a seconda di quale sia più vicino" , quindi quei metodi sono O (n) (n / 4 passi) in media, anche se O(1) per index = 0
.
ArrayList<E>
, d'altra parte, consenti un rapido accesso in lettura casuale, in modo da poter afferrare qualsiasi elemento in tempo costante. Ma l'aggiunta o la rimozione da qualsiasi luogo, ma la fine richiede spostando tutti gli ultimi elementi sopra, sia per fare un'apertura o colmare il divario. Inoltre, se si aggiungono più elementi rispetto alla capacità dell'array sottostante, viene allocato un nuovo array (1,5 volte la dimensione) e viene copiato il vecchio array a quello nuovo, quindi l'aggiunta a ArrayList
è O(n) nel peggiore dei casi ma costante in media.
Quindi, a seconda delle operazioni che intendi fare, dovresti scegliere le implementazioni di conseguenza. L'iterazione su entrambi i tipi di elenco è praticamente altrettanto economica. (Iterare su un ArrayList
è 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 un LinkedList
sorgono quando si riutilizzano 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 (cioè copiato). Dall'altro lato, cercare in un LinkedList
significa seguire i collegamenti in O(n) (n / 2 passi) per il caso peggiore, mentre in un ArrayList
la posizione desiderata può essere calcolata matematicamente e accessibile in O (1) .
Un altro vantaggio dell'utilizzo di un LinkedList
si presenta quando si aggiunge o si rimuove dalla testa dell'elenco, poiché tali operazioni sono O(1), mentre sono O(n) per ArrayList
. Si noti che ArrayDeque
può essere una buona alternativa a LinkedList
per aggiungere e rimuovere dalla testa, ma non è un List
.
Inoltre, se hai elenchi di grandi dimensioni, tieni presente che anche l'utilizzo della memoria è diverso. Ogni elemento di un LinkedList
ha più overhead dai puntatori al successivo e al precedente gli elementi sono anche memorizzati. ArrayLists
non avere questo overhead. Tuttavia, ArrayLists
occupa tutta la memoria allocata per la capacità, indipendentemente dal fatto che gli elementi siano stati effettivamente aggiunti.
La capacità iniziale predefinita di un ArrayList
è 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 l'alto costo del ridimensionamento quando sai che aggiungerai molti elementi, costruisci il ArrayList
con una capacità iniziale più elevata.
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)
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:
- non ci sono un gran numero di accesso casuale di elemento
- 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).
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).
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
elistIterator
restituite da queste classi sonofail-fast
(se la lista è strutturalmente modificata in qualsiasi momento dopo la l'iteratore viene creato, in qualsiasi modo tranne attraverso i metodiiterator’s
remove o add, l'iteratorethrow
aConcurrentModificationException
).
Quando usare LinkedList e quando usare ArrayList?
- Come spiegato sopra le operazioni di inserimento e rimozione danno buone prestazioni
(O(1))
inLinkedList
rispetto aArrayList(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 inArraylist (O(1))
ma non inLinkedList (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.
Prestazioniarraylist.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 arraylistiterator.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)