Artigos Java Diferença entre ArrayList, Vector e LinkedList em Java

Este assunto que confunde muitos iniciantes na área e até profissionais com experiência que acabam não sabendo onde aplicar de cada um destes tipos de listas.

Na verdade todas são muito parecidas, afinal elas implementam a mesma Interface, consequentemente possuem os mesmos métodos mas não as mesmas implementações dos métodos, é aqui que podemos notar a principal diferença, que se da principalmente na performance. Diferente nas implementações da Interface Set (HashSet, TreeSet e LinkedHashSet) que não aceitam elementos duplicados, as listas aceitam elementos duplicado, aqui já encontramos um ponto de diferença entre ambos os conceitos, ou seja, se você não quiser elementos duplicados use Set caso contrário use List.

Vamos nos próximos tópicos explanar como utilizar cada uma das listas e finalmente apontar as principais diferenças entre elas, que é o principal objetivo deste artigo.

ArrayList

Vamos começar pela mais conhecida e usada, ArrayList. Este tipo de lista é implementado como um Array que é dimensionado dinamicamente, ou seja, sempre que é necessário o seu tamanho aumenta em 50% do tamanho da lista, significa que se você tiver uma lista de tamanho igual a 10 e ela “encher”, seu tamanho aumentará para 15 automaticamente.

Além disso a ArrayList permite que elementos sejam acessados diretamente pelos métodos get() e set(), e adicionados através de add() e remove().

Listagem 1: Usando ArrayList


import java.util.ArrayList;
import java.util.Iterator;

public class Principal {

	public static void main(String args[]) {				 
		
		ArrayList al = new ArrayList();
		al.add(3);
		al.add(2);              
		al.add(1);
		al.add(4);
		al.add(5);
		al.add(6);
		al.add(6);

		Iterator iter1 = al.iterator();
		while(iter1.hasNext()){
		        System.out.println(iter1.next());
		}
		
		System.out.println(al.get(2));
		
	}

}

O que você vai perceber no código acima é que o ArrayList não remove os elementos duplicados, e ainda podemos acessar qualquer elemento diretamente através do seu index, mas tudo tem um custo e veremos mais adiante.

Todo ArrayList começa com um tamanho fixo, que vai aumentando conforme necessário, mas o custo deste aumento é alto, pois é feita uma cópia do array atual para um novo array com um novo tamanho, então imagine um array com 10mil elementos que será copiado para um novo array para criação de mais 5 mil elementos ? De fato é um alto custo. Então é altamente aconselhável que você já inicie seu Array com uma quantidade de elementos que atenda ao seu objetivo atual, sem a necessidade de criação dinâmica de novos espaços, ou seja, se você saber que terá que armazenar de 300 a 400 objetos em um Array, defina 500, pois é melhor sobrar espaço do que utilizar recurso do processador sem necessidade.

Há ainda mais um ponto muito importante sobre ArrayList: Estes não são sincronizados, consequentemente não são thread-safe, ou seja, se sua aplicação precisa trabalhar com thread-safe em determinado ponto onde uma Lista é necessária, então descarte ArrayList, a não ser que você faça isso explicitamente, que obviamente não é o correto, veremos mais a diante uma Lista que é sincronizada.

Vector

Do ponto de vista da API, ou seja, da forma como é utilizado, o Vector e o ArayList são muito similares, podemos arriscar até em dizer: iguais. Se você não conhece a fundo o conceito de Vector e ArrayList usará ambos como se fossem o mesmo, sem sentir nenhuma diferença, veja na listagem 2 um exemplo disso.

Listagem 2: Usando Vector


import java.util.Iterator;
import java.util.Vector;

public class Principal {

	public static void main(String args[]) {				 
		
		Vector al = new Vector();
		al.add(3);
		al.add(2);              
		al.add(1);
		al.add(4);
		al.add(5);
		al.add(6);
		al.add(6);

		Iterator iter1 = al.iterator();
		while(iter1.hasNext()){
		        System.out.println(iter1.next());
		}
		
		System.out.println(al.get(2));
		
	}

}

Perceba uma coisa na listagem 2: usamos a mesma estrutura da listagem 1, mudando apenas a lista de ArrayList para Vector, mas o restante do código permanece o mesmo, e a saída também será idêntica.

Então qual a diferença entre Vector e ArrayList ?

  • Primeiramente vamos falar sobre o fato de Vector ser sincronizado e o ArrayList não. Significa dizer que se você possui uma aplicação que precisa ser thread-safe em determinado ponto, use Vector e você estará garantido.
  • Outro ponto importante é a alocação dinâmica do Vector, que é diferente do ArrayList. Lembra que falamos que o ArrayList aumenta 50% do seu tamanho quando a lista está cheia ? O Vector aumenta o dobro, ou seja, se você tem uma lista de 10 elementos cheia, essa lista aumentará para 20, com 10 posições vazias. Mas isso não é ruim ? Depende do que você precisar, se você está precisando aumentar a quantidade de elementos com muita frequência, então o ideal é usar o Vector que aumenta o dobro e você ficará com muito mais espaço do que no ArrayList que precisará ficar aumentando com mais frequência, diminuindo assim a performance da sua aplicação.

LinkedList

Antes de começar as explicações vamos mostrar um uso de LinkedList e você notará que é idêntico a um arrayList.

Listagem 3: Usando LinkedList


import java.util.Iterator;
import java.util.LinkedList;



public class Principal {

	public static void main(String args[]) {

		LinkedList ll = new LinkedList();
		ll.add(3);
		ll.add(2);		
		ll.add(1);
		ll.add(4);
		ll.add(5);
		ll.add(6);
		ll.add(6);

		Iterator iter2 = ll.iterator();
		while(iter2.hasNext()){
			System.out.println(iter2.next());
		}

	}

}

Este tipo de lista implementa uma “double linked list”, ou seja, uma lista duplamente “linkada”. A sua principal diferença entre o ArrayList é na performance entre os métodos add, remove, get e set.

Este tipo de lista possui melhor performance nos métodos add e remove, do que os métodos add e remove do ArrayList, em compensação seus métodos get e set possuem uma performance pior do que os do ArrayList. Vamos abaixo fazer uma comparação entre a complexidade apresentada de cada método do ArrayList e o da LinkedList.

  • get(int index): LinkedList possui O(n) e ArrayList possui O(1)
  • add(E element): LinkedList possui O(1) e ArrayList possui O(n) no pior caso, visto que o array será redimensionado e copiado para um novo array.
  • add(int index, E element): LinkedList possui O(n) e ArrayList possui O(n) no pior caso
  • remove(int index): LinkedList possui O(n) e ArrayList possui O(n-index), se remover o último elemento então fica O(1)

Perceba então que a principal diferença está na performance, e uma análise minuciosa deve ser feita em casos onde a performance é algo crítica e todos o pontos devem ser considerados.

Como falamos muito da diferença de performance entre LinkedList e ArrayList, nada melhor do que mostrar na prática qual é mais rápida em que ocasiões, então veja a listagem abaixo.

Listagem 4: Comparação de Performance entre LinkedList e ArrayList


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

public class Principal {

	public static void main(String args[]) {

		ArrayList arrayList = new ArrayList();
		LinkedList linkedList = new LinkedList();

		// ArrayList add
		long startTime = System.nanoTime();

		for (int i = 0; i < 100000; i++) {
			arrayList.add(i);
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("ArrayList add:  " + duration);

		// LinkedList add
		startTime = System.nanoTime();

		for (int i = 0; i < 100000; i++) {
			linkedList.add(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList add: " + duration);

		// ArrayList get
		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			arrayList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList get:  " + duration);

		// LinkedList get
		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			linkedList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList get: " + duration);

		// ArrayList remove
		startTime = System.nanoTime();

		for (int i = 9999; i >= 0; i--) {
			arrayList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList remove:  " + duration);

		// LinkedList remove
		startTime = System.nanoTime();

		for (int i = 9999; i >= 0; i--) {
			linkedList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList remove: " + duration);

	}

}

SAÍDA;

ArrayList add:  14040033
LinkedList add: 10367831
ArrayList get:  1530083
LinkedList get: 84278855
ArrayList remove:  231619281
LinkedList remove: 83775736

Conclusão

O uso destes 3 tipos de listas se confundem ao ponto que são exatamente iguais as suas formas de utilização, porém o ponto chave aqui é a forma com que cada uma é implementada que impacta diretamente na performance. Além de termos uma lista especial que é a Vector, que é thread-safe, questão muito comum da prova de certificação da oracle.