Quale implementazione di List utilizzare?

Question

Nel mio programma utilizzo spesso le raccolte per memorizzare elenchi di oggetti. Attualmente utilizzo ArrayList per memorizzare oggetti. La mia domanda è: questa è la scelta migliore? Potrebbe essere meglio usare LinkedList? O qualcos'altro?

criteri da prendere in considerazione sono:

• Utilizzo della memoria
• prestazioni

operazioni di cui ho bisogno sono:

• Aggiungi elemento da collezione
• iterazioni sugli elementi

Qualche idea?

Aggiornamento: la mia scelta è: ArrayList :) Sulla base di questa discussione, così come i seguenti:

• When to use LinkedList over ArrayList?
• List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Answer 1

ho sempre predefinito a ArrayList, e sarebbe nel tuo caso pure, tranne quando

• ho bisogno di filo di sicurezza (nel qual caso mi metto a guardare Elenco implementazioni in java.util.concurrent)
• So che sto facendo un sacco di inserimento e manipolazione per la List o profiling rivela il mio utilizzo di un ArrayList per essere un problema (molto raro)

Per quanto riguarda cosa scegliere in questo secondo caso, questo Il thread SO.com ha alcune informazioni utili: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Answer 2

lista collegata è più veloce per l'aggiunta/rimozione di elementi interni (cioè non testa o coda)

L'arraylist è più veloce per iterare

Answer 3

È un compromesso classico tra l'inserimento e l'ottimizzazione del recupero. Scelta comune per l'attività mentre la descrivi è l'ArrayList.

Answer 4

ArrayList va bene per il vostro (e la maggior parte degli altri) scopi. Ha un overhead di memoria molto piccolo e ha buone prestazioni ammortizzate per la maggior parte delle operazioni. I casi in cui non è l'ideale sono relativamente rari:

• L'elenco ist molto grande
• avete spesso bisogno di fare una di queste operazioni:
  • aggiungere/rimuovere gli elementi durante l'iterazione
  • Rimuovi elementi a partire dall'inizio della lista

Answer 5

se si sta solo aggiungendo alla fine della lista, ArrayList dovrebbe essere ok. Dalla documentazione di ArrayList:

I dettagli della politica di crescita non sono specificati al di là del fatto che l'aggiunta di un elemento ha costante di tempo costo ammortizzato

e ArrayList dovrebbe anche utilizzare meno memoria di una lista collegata in quanto non è necessario utilizzare lo spazio per i collegamenti.

Answer 6

Dipende dal profilo di utilizzo.

Aggiungi alla fine della lista? Entrambi stanno bene per questo. Aggiungete all'inizio della lista? LinkedList è meglio per questo. Richiede l'accesso casuale (chiamerai mai get(n) su di esso)? ArrayList è meglio per questo.

Entrambi sono validi per l'iterazione, entrambe le implementazioni di Iterator sono O (1) per next().

In caso di dubbio, testare la propria app per ogni implementazione e fare la propria scelta.

Answer 7

so che sono in ritardo, ma, forse, this page può aiutare, non solo ora, ma in futuro ...

Answer 8

credo che questo sarebbe un buon punto di partenza: http://www.odi.ch/prog/design/newbies.php#26 Essa mostra le differenze di prestazioni di diverse implementazioni di List.

Answer 9

Dato i criteri, si dovrebbe utilizzare la lista collegata.

LinkedList implementa l'interfaccia Deque che significa che può aggiungere all'inizio o alla fine dell'elenco in tempo costante (1). Inoltre, sia ArrayList che LinkedList eseguiranno l'iterazione entro (N).

NON si deve utilizzare ArrayList semplicemente perché il costo dell'aggiunta di un elemento quando l'elenco è pieno. In questo caso, l'aggiunta dell'elemento sarebbe (N) a causa della creazione del nuovo array e della copia di tutti gli elementi da un array all'altro.

Inoltre, ArrayList occuperà più memoria in quanto la dimensione dell'array di supporto potrebbe non essere completa.