Rimuovere elementi dalla lista o aggiungere compilare una nuova lista?

Question

Spesso vengo a un punto in cui devo iterare un ArrayList e voglio creare un sottoinsieme da esso in base a qualsiasi condizione.

Dal punto di vista delle prestazioni: è meglio usare iteratore e iterator.remove() per gli elementi che voglio rimuovere, o dovrei aggiungere questi elementi a un nuovo elenco?

for (Iterator<Object> it = list.iterator(); it.hasNext();) { 
    Object item = it.next(); 
    if (!conditionMatches(item)) { 
     it.remove(); 
    } 
} 

o

List<Object> newList = new ArrayList<>(); 
for (Object item : list) { 
    it (contitionMatches(item)) { 
     newList.add(item); 
    } 
} 

Answer 1

se si desidera rimuovere i valori da elenco è necessario per renderlo da un capo per iniziare, in questo modo: la complessità

for (int i=list.size()-1; i>=0; i--) { 
    if (contitionMatches(list.get(i))) { 
     list.remove(i); 
    } 
} 

Answer 2

Tempo: Opzione 2 è best

Complessità dello spazio: Optio n 1 è migliore

La rimozione di ArrayList è O (n) mentre l'aggiunta è O (1), tuttavia, sarà necessario allocare nuova memoria per il nuovo elenco.

Answer 3

La seconda opzione è più veloce perché non implica lo spostamento di tutti gli elementi successivi quando viene rimosso l'elemento nella posizione corrente.

Quando si parla di più grandi ArrayList s, ho persino il coraggio di dire che la prima opzione è un anti-pattern.

Answer 4

L'opzione 1 non funziona per gli elenchi di sola lettura come quelli restituiti da Arrays.asList.

Inoltre, remove da ArrayList è un costo significativo quando l'elenco è lungo tanto deve essere copiato gran parte dell'array di supporto.

L'opzione 2 funzionerà per tutte le liste.

E 'anche il modello siamo incoraggiati a utilizzare con i flussi:

List<String> l = Arrays.asList("A","B","C"); 
    List<String> filtered = l.stream() 
      .filter(s -> s.equals("A")) 
      .collect(Collectors.toList()); 

IMHO - Utilizzare questo. I risparmi nell'opzione 1 sono illusori.

Answer 5

Se è necessario rimuovere un solo elemento, è possibile farlo in entrambi i modi. Se si desidera rimuovere tutti gli elementi oltre un certo punto, è possibile farlo in entrambi i casi (iterando all'indietro per la rimozione). In generale, tuttavia, l'approccio per la copia richiederà molto meno tempo. Se si preferisce modificare l'elenco in posizione, è possibile considerare removeIf. Sebbene la documentazione non indichi come funziona, molto probabilmente tiene traccia di un indice "a" e "da", spostando tutti gli elementi in un unico passaggio. Se l'approccio di copia o modifica si adatta meglio dipenderà certamente da come si sta usando l'elenco e (se la mia ipotesi su removeIf è corretta) può dipendere anche da quale frazione degli elementi viene rimossa.