Differenze di prestazioni tra ArrayList e LinkedList

Sì, questo è un vecchio argomento, ma ho ancora delle confusioni.

In Java, la gente dice:

  1. ArrayList è più veloce di LinkedList se accedo casualmente ai suoi elementi. Penso che l’accesso casuale significhi “dammi l’ennesimo elemento”. Perché ArrayList è più veloce?

  2. LinkedList è più veloce di ArrayList per la cancellazione. Capisco questo. ArrayList è più lento poiché l’array di backup interno deve essere riallocato. Una spiegazione del codice:

    List list = new ArrayList(); list.add("a"); list.add("b"); list.add("c"); list.remove("b"); System.out.println(list.get(1)); //output "c" 
  3. LinkedList è più veloce di ArrayList per l’inserimento. Cosa significa l’inserimento qui? Se si intende spostare alcuni elementi indietro e quindi inserire l’elemento nel punto vuoto centrale, ArrayList dovrebbe essere più lento di LinkedList. Se l’inserimento indica solo un’operazione di aggiunta (object), come potrebbe essere lenta?

ArrayList è più veloce di LinkedList se accedo casualmente ai suoi elementi. Penso che l’accesso casuale significhi “dammi l’ennesimo elemento”. Perché ArrayList è più veloce?

ArrayList ha riferimenti diretti a ogni elemento della lista, quindi può ottenere l’elemento n-esimo in tempo costante. LinkedList deve attraversare la lista dall’inizio per arrivare all’elemento n-esimo.

LinkedList è più veloce di ArrayList per la cancellazione. Capisco questo. ArrayList è più lento poiché l’array di backup interno deve essere riallocato.

ArrayList è più lento perché ha bisogno di copiare parte dell’array per rimuovere lo slot che è diventato gratuito. Se la cancellazione viene eseguita utilizzando l’API ListIterator.remove() , LinkedList deve solo manipolare un paio di riferimenti; se l’eliminazione viene eseguita in base al valore o all’indice, LinkedList deve potenzialmente eseguire la scansione dell’intero elenco per trovare gli elementi da eliminare.

Se ciò significa spostare alcuni elementi indietro e quindi inserire l’elemento nel punto vuoto centrale, ArrayList dovrebbe essere più lento.

Sì, questo è ciò che significa. ArrayList è infatti più lento di LinkedList perché deve liberare uno slot nel mezzo dell’array. Ciò comporta lo spostamento di alcuni riferimenti e, nel peggiore dei casi, la riallocazione dell’intero array. LinkedList deve solo manipolare alcuni riferimenti.

Ignora questa risposta per ora. Le altre risposte, in particolare quella di aix , sono per lo più corrette. A lungo termine sono il modo di scommettere. E se si dispone di dati sufficienti (su un benchmark su una macchina, sembra essere circa un milione di voci) ArrayList e LinkedList funzionano attualmente come pubblicizzati. Tuttavia, ci sono alcuni punti validi che si applicano all’inizio del XXI secolo.

La moderna tecnologia informatica sembra, dai miei test, dare un vantaggio enorme agli array. Gli elementi di un array possono essere spostati e copiati a velocità folle. Di conseguenza, gli array e ArrayList, nella maggior parte delle situazioni pratiche, sovraperformsranno LinkedList sugli inserimenti e sulle eliminazioni, spesso in modo drammatico. In altre parole, ArrayList batterà LinkedList nel proprio gioco.

Lo svantaggio di ArrayList è che tende ad aggrapparsi allo spazio di memoria dopo le eliminazioni, dove LinkedList dà spazio mentre dà le voci.

Lo svantaggio più grande degli array e di ArrayList è la memoria frammentata e il sovraccarico del garbage collector. Man mano che ArrayList si espande, crea nuovi array più grandi, copia il vecchio array su quello nuovo e libera quello vecchio. La memoria si riempie di grossi pezzi contigui di memoria libera che non sono abbastanza grandi per la prossima allocazione. Alla fine non c’è spazio adatto per quella allocazione. Anche se il 90% della memoria è gratuito, nessun singolo pezzo è abbastanza grande per fare il lavoro. Il GC lavorerà freneticamente per spostare le cose intorno, ma se impiegherà troppo tempo per riorganizzare lo spazio, genererà OutOfMemoryException. Se non si arrende, può comunque rallentare il tuo programma.

Il peggio è che questo problema può essere difficile da prevedere. Il tuo programma funzionerà correttamente una volta. Quindi, con meno memoria disponibile, senza avviso, rallenta o si ferma.

LinkedList utilizza piccoli e delicati frammenti di memoria e GC lo adora. Funziona ancora bene quando si utilizza il 99% della memoria disponibile.

Quindi, in generale, usa ArrayList per insiemi di dati più piccoli a cui è improbabile che la maggior parte dei contenuti venga cancellata o quando hai stretto controllo sulla creazione e la crescita. (Ad esempio, creare una ArrayList che usa il 90% della memoria e usarla senza riempirla per la durata del programma va bene. La creazione e la liberazione continue di istanze di ArrayList che utilizzano il 10% di memoria ti uccideranno.) Altrimenti, vai con LinkedList (o una mappa di qualche tipo se hai bisogno di accesso casuale). Se disponi di collezioni molto grandi (ad esempio oltre 100.000 elementi), non ti preoccupare del GC e pianifica un sacco di inserimenti ed eliminazioni e nessun accesso casuale, esegui alcuni benchmark per vedere cosa è più veloce.

La class ArrayList è una class wrapper per un array. Contiene un array interno.

 public ArrayList { private Object[] array; private int size; } 

A LinkedList è una class wrapper per un elenco collegato, con un nodo interno per la gestione dei dati.

 public LinkedList { class Node { T data; Node next; Node prev; } private Node first; private Node last; private int size; } 

Nota, il codice presente è usato per mostrare come può essere la class, non l’effettiva implementazione. Sapendo come può essere l’implementazione, possiamo fare l’ulteriore analisi:

ArrayList è più veloce di LinkedList se accedo casualmente ai suoi elementi. Penso che l’accesso casuale significhi “dammi l’ennesimo elemento”. Perché ArrayList è più veloce?

Tempo di accesso per ArrayList: O (1). Tempo di accesso per LinkedList: O (n).

In un array, è ansible accedere a qualsiasi elemento usando array[index] , mentre in un elenco collegato è necessario navigare in tutto l’elenco a partire dal first fino a ottenere l’elemento necessario.

LinkedList è più veloce di ArrayList per la cancellazione. Capisco questo. ArrayList è più lento poiché l’array di backup interno deve essere riallocato.

Tempo di eliminazione per ArrayList: tempo di accesso + O (n). Tempo di eliminazione per LinkedList: tempo di accesso + O (1).

L’ArrayList deve spostare tutti gli elementi array[index] array[index-1] partire dall’elemento per eliminare l’indice. Il LinkedList dovrebbe navigare fino a quell’elemento e quindi cancellare quel nodo disaccoppiandolo dalla lista.

LinkedList è più veloce di ArrayList per la cancellazione. Capisco questo. ArrayList è più lento poiché l’array di backup interno deve essere riallocato.

Tempo di inserimento per ArrayList: O (n). Tempo di inserimento per LinkedList: O (1).

Perché ArrayList può prendere O (n)? Perché quando si inserisce un nuovo elemento e l’array è pieno, è necessario creare un nuovo array con più dimensioni (è ansible calcolare le nuove dimensioni con una formula come 2 * dimensione o 3 * dimensione / 2). La LinkedList aggiunge semplicemente un nuovo nodo vicino all’ultimo.

Questa analisi non è solo in Java, ma in altri linguaggi di programmazione come C, C ++ e C #.

Maggiori informazioni qui:

Sia remove () che insert () hanno un’efficienza di runtime di O (n) per ArrayList e LinkedLists. Tuttavia il motivo dietro il tempo di elaborazione lineare deriva da due ragioni molto diverse:

In una ArrayList si ottiene l’elemento in O (1), ma in realtà rimuovere o inserire qualcosa lo rende O (n) perché tutti i seguenti elementi devono essere modificati.

In una LinkedList è necessario O (n) per ottenere effettivamente l’elemento desiderato, perché dobbiamo iniziare dall’inizio fino a raggiungere l’indice desiderato. La rimozione o l’inserimento è costante una volta arrivati ​​lì, 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, LinkedList sarà più veloce, perché dobbiamo passare relativamente a pochi elementi. Se siamo più vicini alla fine, una ArrayList sarà più veloce, perché ci arriviamo in tempo costante e dobbiamo solo cambiare i pochi elementi rimanenti che la seguono.

Bonus: Mentre non c’è modo di rendere questi due metodi O (1) per un ArrayList, in realtà esiste un modo per farlo in LinkedLists. Diciamo che vogliamo passare attraverso l’intero elenco rimuovendo e inserendo elementi sul nostro cammino. Solitamente si ricomincia dall’inizio per ogni elemento che utilizza LinkedList, potremmo anche “salvare” l’elemento corrente su cui stiamo lavorando con un Iterator. Con l’aiuto di Iterator otteniamo un’efficienza di O (1) per remove () e insert () quando si lavora in una LinkedList. Rendendolo l’unico vantaggio in termini di prestazioni, sono a conoscenza di dove un LinkedList è sempre migliore di un ArrayList.

Risposta a 1: ArrayList utilizza un array sotto il cofano. L’accesso a un membro di un object ArrayList è semplice come accedere all’array nell’indice fornito, supponendo che l’indice si trovi entro i limiti dell’array di supporto. Un LinkedList deve scorrere i suoi membri per raggiungere l’ennesimo elemento. Questo è O (n) per una LinkedList, contro O (1) per ArrayList.

In una lista collegata gli elementi hanno un riferimento all’elemento prima e dopo di esso. In un ArrayList la struttura dei dati è solo una matrice.

  1. Un LinkedList ha bisogno di scorrere su N elementi per ottenere l’ennesimo elemento. Un ArrayList deve solo restituire l’elemento N dell’array di supporto.

  2. L’array di supporto deve essere riallocato per la nuova dimensione e l’array copiato su o ogni elemento dopo che l’elemento eliminato deve essere spostato verso l’alto per riempire lo spazio vuoto. A LinkedList è sufficiente impostare il riferimento precedente sull’elemento dopo la rimozione a quello precedente alla rimozione e il successivo riferimento sull’elemento prima dell’elemento rimosso all’elemento dopo l’elemento rimosso. Più a lungo da spiegare, ma più veloce da fare.

  3. Lo stesso motivo della cancellazione qui.

ArrayList : ArrayList ha una struttura come una matrice, ha un riferimento diretto a ogni elemento. Quindi l’accesso al reso è veloce in ArrayList.

LinkedList : In LinkedList per ottenere nth elemnt devi attraversare l’intera lista, richiede tempo rispetto a ArrayList. Ogni elemento ha un link al suo elemento precedente e nest, quindi la cancellazione è veloce.

ArrayList: la class ArrayList estende AbstractList e implementa l’interfaccia List e RandomAccess (interfaccia marker). ArrayList supporta array dinamici che possono crescere secondo le necessità. Ci dà la prima iterazione sugli elementi.

LinkedList: A LinkedList è ordinata per posizione di indice, come ArrayList, tranne per il fatto che gli elementi sono doppiamente collegati l’uno all’altro. Questo collegamento offre nuovi metodi (oltre a quelli ottenuti dall’interfaccia Elenco) per l’aggiunta e la rimozione dall’inizio o alla fine, il che lo rende una scelta facile per l’implementazione di uno stack o di una coda. Tieni presente che una LinkedList può scorrere più lentamente di una ArrayList, ma è una buona scelta quando hai bisogno di inserimenti e cancellazioni veloci. A partire da Java 5, la class LinkedList è stata migliorata per implementare l’interfaccia java.util.Queue. Come tale, ora supporta i metodi di coda comuni: peek (), poll () e offer ().

Anche se sembrano identici (lo stesso elenco di interfacce implementato – non thread-safe), danno risultati diversi in termini di prestazioni in add / delete e in cerca di tempo e consumano memoria (LinkedList ne consuma di più).

Le liste di collegamento possono essere utilizzate se si utilizza l’inserimento / eliminazione elevata con l’esecuzione O (1). ArrayLists può essere utilizzato se si utilizzano le operazioni di accesso diretto con prestazioni O (1)

Questo codice può chiarire questi commenti e puoi provare a capire i risultati delle prestazioni. (Ci scusiamo per il codice della piastra della caldaia)

 public class Test { private static Random rnd; static { rnd = new Random(); } static List testArrayList; static List testLinkedList; public static final int COUNT_OBJ = 2000000; public static void main(String[] args) { testArrayList = new ArrayList<>(); testLinkedList = new LinkedList<>(); insertSomeDummyData(testLinkedList); insertSomeDummyData(testArrayList); checkInsertionPerformance(testLinkedList); //O(1) checkInsertionPerformance(testArrayList); //O(1) -> O(n) checkPerformanceForFinding(testArrayList); // O(1) checkPerformanceForFinding(testLinkedList); // O(n) } public static void insertSomeDummyData(List list) { for (int i = COUNT_OBJ; i-- > 0; ) { list.add(new String("" + i)); } } public static void checkInsertionPerformance(List list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.add(rndIndex, "test"); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } public static void checkPerformanceForFinding(List list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.get(rndIndex); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } }