Domanda Quando utilizzare LinkedList su ArrayList?


Sono sempre stato uno da usare semplicemente:

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

Io uso l'interfaccia come nome del tipo per portabilità, così quando faccio domande come queste posso rielaborare il mio codice.

Quando dovrebbe LinkedList essere usato finita ArrayList e viceversa?


2565
2017-11-27 01:36


origine


risposte:


Sommario  ArrayList con ArrayDeque sono preferibili a tanto più casi d'uso di LinkedList. Non sono 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 una matrice di ridimensionamento dinamico.

Come con le operazioni di elenchi e matrici standard collegate, i vari metodi avranno diversi runtime algoritmici.

Per LinkedList<E>

  • get(int index) è Sopra) (con n / 4 passi in media)
  • add(E element) è O (1)
  • add(int index, E element) è Sopra) (con n / 4 passi in media), ma O (1) quando index = 0  <--- vantaggio principale di LinkedList<E>
  • remove(int index) è Sopra) (con n / 4 passi in media)
  • Iterator.remove() è O (1). <--- vantaggio principale di LinkedList<E>
  • ListIterator.add(E element) è O (1)  Questo è uno dei principali vantaggi di LinkedList<E>

Nota: molte delle operazioni necessarie n / 4 passi in media, costante numero di passaggi nel migliore dei casi (ad esempio indice = 0) e n / 2 passi nel peggiore dei casi (centro della lista)

Per ArrayList<E>

  • get(int index) è O (1)  <--- vantaggio principale di ArrayList<E>
  • add(E element) è O (1) ammortizzato, ma Sopra) il caso peggiore in quanto l'array deve essere ridimensionato e copiato
  • add(int index, E element) è Sopra) (con n / 2 passi in media)
  • remove(int index) è Sopra) (con n / 2 passi in media)
  • Iterator.remove() è Sopra) (con n / 2 passi in media)
  • ListIterator.add(E element) è Sopra) (con n / 2 passi in media)

Nota: molte delle operazioni necessarie n / 2 passi in media, costante numero di passi nel migliore dei casi (fine della lista), n passi nel peggiore dei casi (inizio della lista)

LinkedList<E> consente inserimenti o rimozioni costanti usando gli iteratori, ma solo l'accesso sequenziale di elementi. In altre parole, puoi scorrere l'elenco avanti o indietro, ma trovare una posizione nell'elenco richiede tempo proporzionale alla dimensione dell'elenco. Javadoc dice "le operazioni che indicizzano nella lista attraverseranno la lista dall'inizio o dalla fine, a seconda di quale sia più vicino", quindi quei metodi sono Sopra) (n / 4 passi) in media, però O (1) per index = 0.

ArrayList<E>, d'altra parte, consentire l'accesso veloce alla lettura casuale, in modo da poter afferrare qualsiasi elemento in tempo costante. Ma aggiungere o rimuovere da qualsiasi luogo, ma alla fine richiede di spostare tutti gli ultimi elementi, 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 il vecchio array viene copiato in quello nuovo, quindi aggiungendolo a un ArrayList è Sopra) 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 List è praticamente altrettanto economica. (Iterando su un ArrayList è tecnicamente più veloce, ma a meno che tu non stia facendo qualcosa di davvero sensibile alle prestazioni, non dovresti preoccuparti di questo: sono entrambe costanti.)

I principali vantaggi dell'utilizzo di a LinkedList sorgono quando si riutilizzano gli iteratori esistenti per inserire e rimuovere elementi. Queste operazioni possono quindi essere eseguite in O (1) cambiando la lista solo localmente. In un elenco di array, il resto dell'array deve essere mosso (cioè copiato). Dall'altro lato, cercando in a LinkedList significa seguire i collegamenti in Sopra) (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 a LinkedList sorgono quando si aggiunge o si rimuove dal capo della lista, dal momento che tali operazioni sono O (1), mentre sono Sopra) per ArrayList. Nota che ArrayDeque potrebbe essere una buona alternativa a LinkedList per aggiungere e rimuovere dalla testa, ma non è un List.

Inoltre, se si dispone di elenchi di grandi dimensioni, tenere presente che anche l'utilizzo della memoria è diverso. Ogni elemento di a LinkedList ha un sovraccarico maggiore poiché vengono memorizzati anche i puntatori agli elementi successivo e precedente. ArrayLists non avere questo sovraccarico. Però, ArrayLists occupa la quantità di memoria allocata per la capacità, indipendentemente dal fatto che gli elementi siano stati effettivamente aggiunti.

La capacità iniziale predefinita di un ArrayList è abbastanza piccolo (10 da Java 1.4 - 1.8). Ma poiché l'implementazione sottostante è un array, l'array deve essere ridimensionato se aggiungi molti elementi. Per evitare l'alto costo del ridimensionamento quando sai che stai per aggiungere molti elementi, costruisci il ArrayList con una capacità iniziale più elevata.


2845
2017-10-06 06:46



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

Poiché i riferimenti sono 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 ArrayList le linee sono per liste tagliate - In pratica, la capacità del backing array in un ArrayList è generalmente più grande del suo attuale numero di elementi.

Nota 2:  (grazie 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 lo disattiviate.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Il risultato lo dimostra chiaramente LinkedList è molto più di ArrayList, specialmente con un numero di elementi molto alto. Se la memoria è un fattore, evita 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)

534
2017-11-27 14:20



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

Perché LinkedList succhia:

  • 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, portando ad algoritmi O (n) più lenti di se ArrayListera usato.
  • Ottenere buone prestazioni è complicato.
  • Anche quando le prestazioni di big-O sono le stesse di ArrayList, probabilmente sarà comunque molto più lento.
  • È sconvolgente da vedere LinkedList in origine perché probabilmente è la scelta sbagliata.

190
2018-01-01 20:23



Come qualcuno che sta facendo 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 a stato 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 espandendo i propri array in quasi sincronicità e per dimensioni di array di grandi dimensioni potrebbe portare a mancanza di reattività nell'app e un'interruzione, mentre sotto pressione, che è un comportamento catastrofico.

Allo stesso modo, puoi ottenere un throughput migliore in un'app dal garbage collector predefinito con throughput predefinito, ma una volta che ottieni app java con 10 GB di heap, puoi bloccare l'app per 25 secondi durante un GC completo che causa timeout e guasti nelle app SOA e soffia i tuoi SLA se si verifica troppo spesso. Anche se il raccoglitore CMS prende più risorse e non raggiunge lo stesso throughput raw, è una scelta molto migliore perché ha una latenza più prevedibile e più piccola.

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


125
2018-04-08 20:33



Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritmi: Big-Oh Notation

Le liste di array sono utili per scrivere una volta sola, molte o appendici, ma non valide per aggiungere / rimuovere dalla parte anteriore o centrale.


111
2018-05-19 11:21



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

LinkedList è quasi sempre la scelta sbagliata, in termini di prestazioni. Ci sono alcuni algoritmi molto specifici in cui è richiesto un LinkedList, ma questi sono molto, molto rari e l'algoritmo di solito dipende in modo specifico dalla capacità di LinkedList di inserire ed eliminare elementi nel mezzo della lista relativamente velocemente, una volta che ci si è navigati lì con un ListIterator.

Esiste un caso d'uso comune in cui LinkedList ha prestazioni migliori di ArrayList: quella di una coda. Tuttavia, se il tuo obiettivo è il rendimento, invece di LinkedList dovresti anche considerare l'utilizzo di un ArrayBlockingQueue (se puoi determinare un limite superiore sulla dimensione della tua coda in anticipo, e puoi permetterti di allocare tutta la memoria in primo piano), o questo Implementazione di CircularArrayList. (Sì, è del 2001, quindi dovrai generarlo, ma ho ottenuto percentuali di prestazioni paragonabili a quelle citate nell'articolo in una recente JVM)


92
2017-11-27 01:39



È 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 Vectorva più in profondità, come fa Lista collegata.


50
2017-09-21 22:59