Pra adicionar/remover elementos o LinkedList é mais rapido que o ArrayList?

Cara,

achei estranho vc encontrar esses resultados. Principalmente porque sempre levei o conceito de que ArrayList ser mais lento para adicionar/remover elementos, inclusive já fiz a prova OCJP e a uns 2 meses atrás tinha feito um teste parecido.

Com isso resolvi rodar na minha máquina.

Encontrei o seguinte (fiz os testes 3 vezes).

Utilizando um ArrayList o tempo que levou foi: 14
Utilizando um LinkedList o tempo que levou foi: 10

Utilizando um ArrayList o tempo que levou foi: 14
Utilizando um LinkedList o tempo que levou foi: 10

Utilizando um ArrayList o tempo que levou foi: 15
Utilizando um LinkedList o tempo que levou foi: 10

Talvez tenha algum fator determinante na sua máquina. Aliás, qual versão de java ta rodando? Realmente é estranho.

O terceiro teste alterei o código para adicionar Integer como abaixo, mesmo assim deu praticamente o mesmo resultado:

package teste;

import java.util.ArrayList;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) throws Exception {

		int i = 0;
		long longo = System.currentTimeMillis();

		ArrayList<Integer> main = new ArrayList<Integer>();
 
		while(i < 10000000){
			main.add(new Integer(1));
			i++;
		}

		long longof = System.currentTimeMillis();
		long longfinal = longof - longo;

		System.out.println("Utilizando um ArrayList o tempo que levou foi: " + longfinal/1000);

	}

}

tenta assim

javac -source 1.5

No meu caso, rodei versão 7.

Vou rodar versão 5 e posto o resultado aqui.

valeu

Mesmo com versão 5, resultado idêntico…

Utilizando um ArrayList o tempo que levou foi: 14
Utilizando um LinkedList o tempo que levou foi: 10

Adicionar e remover ao final do ArrayList é muito rápido. Se quer testar isso, tem que remover e adicionar de posições aleatórias das duas listas.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Main {
    public static void testarLista(List<String> lista) {
        Random r = new Random();
        System.out.printf("[%s] - Adicionando elementos", lista.getClass().getSimpleName());

        long antes = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++)
            lista.add(0, "Teste");

        System.out.printf(" - %.2fs%n", (System.currentTimeMillis() - antes) / 1000.0);

        System.out.printf("[%s] - Removendo elementos", lista.getClass().getSimpleName());

        antes = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++)
            lista.remove(0);

        System.out.printf(" - %.2fs%n", (System.currentTimeMillis() - antes) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        testarLista(new LinkedList<String>());
        testarLista(new ArrayList<String>());
    }

}

[LinkedList] - Adicionando elementos - 0,01s
[LinkedList] - Removendo elementos - 0,01s
[ArrayList] - Adicionando elementos - 1,16s
[ArrayList] - Removendo elementos - 1,28s

Agora, a performance de encontrar um elemento numa LinkedList é péssima.

Primeiro, porque ele não consegue fazer acesso aleatório a uma dada posição da lista. Sempre que você pede um índice, ele é obrigado a percorre-la.
Segundo, porque ele não é uma estrutura sequencial. Então, percorrer em si será um pouco mais lento do que o “arrayzão” que é o ArrayList.

Por isso, se você repetir esse teste usando Random para sortear uma posição, a LinkedList vai desempenhar MUITO pior.

Eu, de maneira geral, dou preferência sempre para o ArrayList. É mais econômico em memória e em 90% dos casos, vai ser mais rápido também.

e qual o conceito que eu devo levar pra prova?

Tentei retratar o que o ViniGodoy colocou e faz todo sentido.

Realmente estávamos tentando realizar o teste inserindo sempre no final.

Com isso realizei mais um teste e dá pra demonstrar a diferença grande que existe.

Resultado:

Primeira execução
Utilizando um class java.util.LinkedList o tempo que levou foi: 0,31s
Utilizando um class java.util.ArrayList o tempo que levou foi: 58,21s

Segunda execução
Utilizando um class java.util.LinkedList o tempo que levou foi: 0,32s
Utilizando um class java.util.ArrayList o tempo que levou foi: 60,81s

Código:

public static void main(String[] args) throws Exception {

		Integer[] ii = new Integer[100];
		List<Integer> listLinkedList = new LinkedList<Integer>(Arrays.asList(ii));

		long tempoAntes = System.currentTimeMillis();

		for (int i=0; i < 500000; i++){
			Random r = new Random();
			int index = r.nextInt(100);
			int valor = r.nextInt(100);
			listLinkedList.add(index, valor);
		}

		System.out.printf("Utilizando um " + listLinkedList.getClass() + " o tempo que levou foi: %.2fs%n", (System.currentTimeMillis() - tempoAntes) / 1000.0);

		
		List<Integer> listArrayList = new ArrayList<Integer>(Arrays.asList(ii));

		tempoAntes = System.currentTimeMillis();

		for (int i=0; i < 500000; i++){
			Random r = new Random();
			int index = r.nextInt(100);
			int valor = r.nextInt(100);
			listArrayList.add(index, valor);
		}

		System.out.printf("Utilizando um " + listArrayList.getClass() + " o tempo que levou foi: %.2fs%n", (System.currentTimeMillis() - tempoAntes) / 1000.0);

	}

Só que raramente temos esta situação no mundo real. Por isso utilizamos mais o Arraylist como citado também.

Abs.

Livro da Kathy:
ArrayList: “… quando precisar de iteração rápida e não pretender executar muitas inserções exclusões”.

LinkedList: “…uma boa opção quando precisar de inserções e exclusões rápidas.”

É isso aí mesmo.

Não é tão raro assim não. Se você tiver uma situação onde existam muitas exclusões ou inserções, no meio da lista, vai acabar com o mesmo problema.

É o caso quando, por exemplo, você estiver inserindo em alguma ordem, ou tiver itens que são excluídos de alguma posição da lista.

Em games, posso pensar em vários exemplos disso:

• Inclusão e remoção de inimigos
• Geradores de partículas;
• Scene Management;

Em softwares comerciais é um pouco mais raro, mas já tive que usar algumas vezes.

É só pensar no conceito. LinkedList é uma lista duplamente encadeada. Então, para inserir um nó ali, basta mudar os apontadores dos nós posterior e anterior.
ArrayList é uma lista baseada num vetor. Portanto, para inserir um elemento lá, é necessário deslocar todos os elementos para frente. Com exceção do último elemento.

Entretanto, um vetor pode ser facilmente acessado, em qualquer posição. Enquanto uma lista ligada, exige que você percorra a lista toda.

Realmente não é tão raro.

E apenas como complemento, fica um link de uma boa leitura.

http://docs.oracle.com/javase/tutorial/collections/implementations/list.html

Abraços

se você olhar a implementação do LinkedList vai ver que ele é mais rápido. Sem executar só olhando como foi implementado e comparado com o ArrayList percebe a diferença. Por exemplo, percorrer meia duzia de dados, não percebemos a diferença, mas quando temos no minimo 1 milhão e queremos encontrar ou remover um cara que tá no meio com LinkedList isso é fácil e rápido.