Implementazioni di elenchi: LinkedList funziona davvero male rispetto a ArrayList e TreeList?

Question

tratto dal Apache TreeList doc:

le seguenti statistiche sulle prestazioni relativi sono indicativi di questo classe:

   get add insert iterate remove 
TreeList  3 5  1  2  1 
ArrayList  1 1  40  1  40 
LinkedList 5800 1  350  2  325 

E continua dicendo:

LinkedList è raramente un buona scelta di implementazione. TreeList è quasi sempre un buon sostituto, anche se utilizza una quantità di memoria leggermente superiore.

Le mie domande sono:

• Qual è la ArrayListadd, insert, e remove volte schiacciante LinkedList? Dovremmo aspettarci, per lo , che i casi di inserimento e rimozione nel mondo reale siano decisamente a favore di ArrayList?

• Questo TreeList semplicemente mettere il chiodo nella bara del venerabile LinkedList?

sono tentato di concludere che hanno ammortizzato o ignorato ArrayList s' dolori della crescita, e non hanno preso in considerazione i tempi di inserimento e rimozione di un elemento in un LinkedList che è già stato localizzato.

Answer 1

La cosa fondamentale qui è la complessità delle operazioni di inserimento/eliminazione nelle tre implementazioni di Elenco. ArrayList ha O (n) inserire/eliminare i tempi per gli indici arbitrari, ma è O (1) se l'operazione è alla fine della lista. ArrayList ha anche la comodità di accesso O (1) per qualsiasi posizione. LinkedList è analogamente O (n), ma è O (1) per le operazioni alle due estremità dell'elenco (inizio e fine) e O (n) per le posizioni arbitrarie. TreeList ha complessità O (logn) per tutte le operazioni in qualsiasi posizione.

Ciò dimostra chiaramente che TreeList è più veloce per elenchi sufficientemente grandi per quanto riguarda l'inserimento/eliminazione in posizioni arbitrarie. Ma AFAIK, TreeList è implementato come un albero di ricerca binario e ha una costante molto più grande associata alle sue operazioni O (logn) rispetto alle operazioni simili con ArrayLists che sono semplicemente wrapper attorno ad un array. Questo rende TreeList in realtà più lento per le Liste piccole. Inoltre, se tutto ciò che stai facendo è aggiungere un elemento in una List, le prestazioni O (1) di ArrayList/LinkedList sono chiaramente più veloci. Inoltre, spesso il numero di inserimenti/cancellazioni è molto inferiore al numero di accessi, il che tende a rendere ArrayList più veloce nel complesso per molti casi. L'inserimento/eliminazione costante del tempo di LinkedList alle due estremità dell'Elenco rende molto più veloce l'implementazione di strutture di dati come Code, Stack e Deques.

Alla fine della giornata, tutto dipende da cosa è esattamente necessario un elenco per. Non esiste una soluzione valida per tutti. Devi selezionare l'implementazione più adatta al tuo lavoro.

Answer 2

È dovuto allo data structures dietro queste raccolte. TreeList è un tree, che consente letture, inserzioni, rimozioni relativamente veloci (tutto O (log n)). ArrayList usa un array per memorizzare i dati, quindi quando si inserisce o rimuove, ogni elemento dell'array deve essere spostato in alto o in basso (O (n) nel caso peggiore). Gli array hanno anche una dimensione fissa, quindi se si supera la capacità dell'array attuale, deve essere creato uno nuovo, più grande (di solito il doppio della dimensione dell'ultimo, per mantenere le riduzioni al minimo). LinkedList utilizzato ... a linked list. Un elenco collegato di solito ha un riferimento al primo (e talvolta ultimo) elementi nella lista. Quindi ogni elemento nella lista ha un riferimento al prossimo elemento nell'elenco (per un elenco collegato singolarmente) o agli elementi successivo e precedente (per un elenco collegato doppio). Per questo motivo, per accedere a un elemento specifico, è necessario scorrere tutti gli elementi prima di arrivare (O (n) nel caso peggiore). Quando si inseriscono o si rimuovono elementi specifici, è necessario trovare la posizione in cui inserirli o rimuoverli, il che richiede tempo (O (n) nel caso peggiore). Tuttavia c'è un costo molto piccolo per aggiungere semplicemente un altro elemento all'inizio o alla fine (O (1)).

Ci sono interi libri scritti sulle strutture dati e quando usarli, consiglio di leggere quelli più fondamentali.

Answer 3

Poiché un elenco collegato deve spostarsi nodo per nodo per ottenere un punto qualsiasi nell'elenco (salvare il front e probabilmente il retro in base all'implementazione), è logico che i numeri siano così alti.

Per aggiungere/inserire/rimuovere in una grande LinkedList, si otterrebbe un sacco di passaggi da un nodo all'altro per raggiungere la posizione corretta.

Se hanno fatto la lista Array delle dimensioni appropriate per iniziare con i dolori in crescita non sarà nulla. Se l'ArrayList è piccolo, i dolori della crescita non contano.

Per LinkedList se le operazioni si trovano tutte in primo piano, l'impatto è molto inferiore se si trovano alla fine.

Quello che dovresti fare è usare sempre l'interfaccia, ad es .: Elenco per dichiarare variabili e parametri, quindi puoi cambiare il "nuovo LinkedList();" a "new ArrayList();" e profilo il codice per vedere come si comporta nel tuo codice specifico.

A causa della velocità di non dover saltare da un nodo all'altro, faccio sempre il default su ArrayList anziché su LinkedList.

Credo che la lista ad albero sarà molto più veloce di entrambe (anche senza guardare il codice). Gli alberi sono progettati per essere veloci.

Answer 4

Per ArrayList, poiché viene eseguito di rado, è possibile che il costo sia trascurabile. Se in realtà è un problema, basta allargare l'array per iniziare.

Se ho una lista piccola, una LinkedList ha senso da usare in quanto vi è un vantaggio minimo a quel punto. Se la lista sarà lunga, ovviamente una TreeList ha più senso.

Se ho intenzione di fare un gran numero di accesso casuale a una lista, l'ArrayList ha più senso.

Quale contenitore da utilizzare dipende realmente da ciò che si farà con esso. Non esiste un contenitore corretto, poiché ognuno ha i suoi punti di forza e di debolezza e con l'esperienza inizi a capire quando usare quale.

Answer 5

Ogni persona che ha risposto qui è corretta. Hanno tutti ragione nel loro concetto, che dipende molto dal tuo schema di utilizzo, cioè non esiste un elenco valido per tutti. Ma al momento della mia scrittura hanno tutti dimenticato di menzionare (o quello, o sono un lettore sciatto) un caso d'uso quando LinkedList è il migliore: inserto posizionato da iteratore.Ciò significa, che se si sta facendo non solo

LinkedList::add(int index, E element) 
      Inserts the specified element at the specified position in this list. 

che sembrano essere il metodo che hanno usato per ottenere le statistiche, ma

iterator.insert(E element) 

con una iterator ottenuta attraverso sia

public abstract ListIterator<E> listIterator(int index) 
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. 

o

public Iterator<E> iterator() 
Returns an iterator over the elements in this list (in proper sequence). 

, quindi sei tenuto a ottenere le migliori prestazioni di inserimento arbitrarie di sempre. Ciò implica, naturalmente, che puoi limitare il numero di chiamate a iterator() e listIterator() e il numero di movimenti di iteratore attraverso l'elenco (ad esempio puoi fare un solo passaggio sequenziale sull'elenco per fare tutti gli inserti di cui hai bisogno). Questo rende i suoi casi d'uso abbastanza limitati nel loro numero, ma tuttavia sono quelli che si verificano molto spesso. E la performance di LinkedList in loro è la ragione per cui è (e sarà in futuro) conservata in tutte le raccolte di contenitori di tutte le lingue, non solo di Java.

PS. Tutto quanto sopra naturalmente si applica a tutte le altre operazioni, come get(), remove(), ecc. I.e l'accesso attentamente progettato tramite iteratore renderà tutti loro O (1) con una costante reale molto piccola. Lo stesso naturalmente può essere detto per tutti gli altri elenchi, l'accesso iteratore li velocizzerà tutti (anche se leggermente). Ma non l'inserto() e remove() di ArrayList - saranno ancora O (n) ... E non TreeList's insert() e remove() - l'overhead di bilanciamento dell'albero non è qualcosa che puoi evitare ... E TreeList probabilmente ha più memoria in testa ... Hai la mia idea. Per riassumere tutto, LinkedList è per piccole operazioni di tipo hi-perf-scan sugli elenchi. Che sia il caso d'uso di cui hai bisogno o meno - solo tu puoi dirlo.

PSS. Detto questo, sto quindi rimango anche

tentati di concludere che hanno ammortizzato o ignorati dolori della crescita di ArrayList, e non hanno preso in considerazione volte l'inserimento e di rimozione per un elemento in un LinkedList che è già stato situato.

Answer 6

Si noti che ArrayList è generalmente più veloce di LinkedList, anche quando il codice chiama solo i metodi che sono costanti per entrambi. Ad esempio, ArrayList.add() consente di copiare una singola variabile e incrementare un contatore quando non è necessario ridimensionare, mentre LinkedList.add() deve anche creare un nodo e impostare più puntatori. Inoltre, i nodi LinkedList richiedono più memoria, il che rallenta l'applicazione e la garbage collection deve gestire i nodi.

Se avete bisogno di aggiungere o rimuovere elementi da entrambe le estremità della lista, ma non richiedono l'accesso casuale, un ArrayDeque è più veloce di quello di una LinkedList, anche se richiede Java 6.

Una LinkedList dare un senso per iterare attraverso l'elenco e quindi aggiungere o rimuovere elementi nel mezzo, ma questa è una situazione insolita.