Aggiungi elemento in un ArrayList in modo efficiente a un determinato indice in Java

Question

ho bisogno di inserire un elemento di tipo Person (la mia classe definita) in un ArrayList al indice i

So che posso usare add(int index, E element).

Ma esiste un metodo efficace per farlo, poiché nella mia lista si impiegano mediamente circa 1,5 ms (dati raccolti oltre 1000 inserimenti e poi medi).

Answer 1

Questo inserimento avviene in O (n) perché deve spostare tutti gli elementi verso il basso e nel peggiore dei casi lo spostamento di ogni elemento verso il basso. (Corretto java dice che è O (n) perché usano una formula matematica da inserire)

Se si desidera un inserimento veloce, aggiungerlo alla fine dell'array o utilizzare una hashmap che è un tempo costante.

Inserire nel hashmap: HashMap peopleMap = new HashMap .....

peopleMap.put (person.name, persona); // (o quello che si desidera tracciare)

Imposta la chiave per il nome delle persone e il valore per persona.

Si può anche provare una hashmap con chiave (ehatver che si desidera tracciare) e valutare l'indice in cui la persona si trova in una matrice di supporti. L'inserto è O (i), look O (i) e puoi anche ordinarlo (lo lascerò come esercizio al lettore)

Se l'intero scopo di questo è di ordinare, quindi per semplicità è possibile inserire in una priorityQueue (nLogn) quindi inserire tutto nell'array che fornirà un array ordinato

Answer 2

Se l'attività è più intensiva di inserimento/eliminazione, è sempre possibile utilizzare java.util.LinkedList.

• ArrayList ha una dimensione limitata. Ogni volta che aggiungi un elemento, Java garantisce che possa adattarsi, quindi cresce ArrayList. Se ArrayList cresce più rapidamente, si verificherà un sacco di copie di array.
• LinkedList aggiunge semplicemente l'elemento alla posizione corretta (collegando i nodi intorno), senza aumentare e copiare l'intera ArrayList.
• I svantaggi di LinkedList si verificano quando si cerca un elemento. Dal momento che non ha indici, deve attraversare dall'inizio alla fine della lista per trovare un oggetto.

Per LinkedList:

• ottenere è O (n)
• aggiuntivo è O (1)
• remove è O (n)
• Iterator.rimuovere è O (1)

Per ArrayList:

• get è O (1)
• aggiunge è O (1) ammortizzato, ma O (n) nel caso peggiore poiché la matrice deve essere ridimensionato e copiato
• remove è O (n)

Answer 3

Se si aggiungono utilizzando

arryListInstance.add(positionIndex, Object); 

l'oggetto verrà aggiunto dopo aver setacciato gli oggetti esistenti di 1 posizione. Pertanto il caso medio di questa operazione diventa O (n).

Mentre semplice add

arryListInstance.add(positionIndex, Object); 

aggiunge l'oggetto alla fine del arrayListInstance. Nel migliore dei casi questa operazione è O (1), ma nel peggiore dei casi diventa O (n) quando viene raggiunta la capacità massima: una nuova istanza ArrayList viene creata internamente e tutti i contenuti vengono copiati.

Si trovano ad affrontare questo problema perché uno dei due motivi di cui prima può essere evitato:

1. Non hai definito capacità iniziale sufficiente per l'oggetto ArrayList. Pertanto, prima di ogni arrayListInstance.add (positionIndex, oggetto) un nuovo arrayListInstance si sta creando con maggiore capacità e quindi gli elementi esistenti dall'elenco originale vengono copiati e infine aggiungere è in corso. Questo può essere evitato, se si conosce esattamente la quantità di dati che si desidera gestire da questo elenco e definire di conseguenza la capacità iniziale (uguale al numero di possibili elementi). Se non si prevede la capacità iniziale, è meglio elaborare i dati nei lotti .
2. Dopo ogni inserimento in qualsiasi posizione tranne l'ultima causa, setacciamento di elementi esistenti. Questo è inevitabile. Pertanto, arrayListInstance.add (positionIndex, oggetto) verrà eseguito in O (n) tempo se positionIndex non è l'ultimo indice di arrayList. Anche se si utilizza LinkedList non è possibile ottenere un'operazione di aggiunta di tempo costante che aggiunge un elemento all'elenco a un indice diverso dall'ultimo elemento.