ArrayList Vs LinkedList
Eu estava seguindo umpostagem anterio nisto que diz:
Para LinkedList
get é O (n)add é O (1)remove é O (n) Iterator.remove é O (1)For ArrayList
get é O (1)add é O (1) amortizado, mas O (n) na pior das hipóteses, pois a matriz deve ser redimensionada e copiadaremove é O (n)Então, olhando para isso, concluí que, se eu tiver que fazer apenas inserção sequencial na minha coleção, digamos 5000000 elementos,LinkedList
superaráArrayList
.
E se eu precisar buscar os elementos da coleção iterando, ou seja, não pegar o elemento no meio, aindaLinkedList
ultrapassará `ArrayList.
Agora, para verificar minhas duas declarações acima, escrevi abaixo o programa de exemplo… Mas estou surpreso que minhas declarações acima tenham sido comprovadas errada
ArrayList
superclassedLinkedlist
nos dois casos. Demorou menos tempo queLinkedList
para adicionar e buscar na coleção. Há algo que estou fazendo de errado ou as declarações iniciais sobreLinkedList
eArrayList
não é verdadeiro para coleções de tamanho 5000000?
Mencionei o tamanho, porque se eu reduzir o número de elementos para 50000,LinkedList
executa melhor e as instruções iniciais são verdadeira
long nano1 = System.nanoTime();
List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );
for(int j : arr) {
;
}
System.out.println( (System.nanoTime() - nano1) );
long nano2 = System.nanoTime();
List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );
for(int j : arrL) {
;
}
System.out.println( (System.nanoTime() - nano2) );