È più efficiente rimuovere elementi da una ArrayList o da una LinkedList?

Question

In teoria, è più efficiente rimuovere elementi da un ArrayList o da un LinkedList ?

Answer 1

È "più facile" (ovvero, più efficiente) per rimuoverli da un LinkedList , poiché la rimozione da un ArrayList richiede lo spostamento di tutti gli elementi successivi in ??una nuova posizione nell'elenco, tutti gli elementi successivi di all'array deve essere assegnato un nuovo valore. Con un elenco collegato, solo un puntatore (o due, con un elenco doppiamente collegato) deve essere riassegnato.

Answer 2

Bene, la rimozione di un elemento da un elenco (doppiamente collegato) è O (1). Ma la rimozione da un array richiederà che gli elementi rimanenti vengano spostati in basso di uno spazio nell'array, che è O (n).

Detto questo, ottenere un elemento specifico in un elenco per indice è O (n), mentre ottenere un elemento specifico in un array per indice è O (1).

Quindi, per la rimozione effettiva, LinkedList sarà migliore. Sono disponibili ulteriori informazioni sull'array rispetto a LinkedList qui .