Collections #1: ArrayList, LinkedList e Vector | Café com Leite

Tempo de leitura: menos de 1 minuto

Olá pessoal, como vão?

Vou falar hoje sobre collections. Existem várias implementações de Collection, muitos sabem exatamente para que todas elas servem, mas vocês sabem??

Vira e mexe, preciso consultar qual é a implementação correta a ser usada para resolver meu problema. Então decidi escreve-las aqui para não esquecer mais.

Começamos então falando da Interface List.

Interface List

A interface java.util.List extende da interface java.util.Collection. É a interface que mais uso quando preciso trabalhar com collections. Sempre que preciso criar uma coleção, esta é a interface que uso juntamente com a implementação java.util.ArrayList.

Uma lista é uma coleção de valores que permite elementos duplicados e mantém uma ordenação específica entre os elementos.

Uma instância de List, provê os recursos de busca, adição, remoção e tamanho flexível, no entanto a ordenação é pré-defina de acordo com cada implementação, sendo assim, ao inserir um objeto em uma lista a ordenação do mesmo já foi definida.

A partir do Java 5, o conceito de Generics foi adicionado ao Java, assim, é possível criar listas “tipadas”, por exemplo, uma lista de String, Integer, ou um tipo próprio do seu negócio. Antes disso, só lista de Object.

ArrayList

O ArrayList, como disse anteriormente é a implementação que mais uso, deve ser a sua também. Ela trabalha com um array interno para gerar uma lista. Portanto, ela é mais rápida na pesquisa do que sua concorrente, a LinkedList, que é mais rápida na inserção e remoção de itens nas pontas.

Mas que fique claro, mesmo contendo no nome a palavra “array”, Array List não é um array. Ela usa um array como estrutura para armazenar os dados, porém este atributo está encapsulado e o mesmo é inacessível.

É a forma mais simples de lista, a ordenação dos seus itens é dada pela ordem de inserção, ou seja, o primeiro item é adicionado no índice 0, o segundo no índice 1 e assim por diante.

Outro ponto importante, é que o ArrayList aumenta seu tamanho em 50% quando a lista está cheia.

Para criar uma ArrayList de String basta fazer:

[code language=”java”]
ArrayList<String> lista = new ArrayList<String>();
[/code]

No entanto, sempre que possível abstraia a implementação da lista para a interface List:

[code language=”java”]
List<String> lista = new ArrayList<String>();
[/code]

LinkedList

A outra implementação de List é o LinkedList. Como o nome mesmo diz, é a implementação para lista ligada. Fornece métodos adicionais para tratar as extremidades da lista, é possível obter e remover o primeiro ou o último elemento da lista.

Seu funcionamento interno é diferente do ArrayList. LinkedList possui melhor performance nos métodos add e remove, em compensação seus métodos get e set possuem uma performance pior. Para ver na prática a diferença, nada melhor que testar.

[code language=”java” highlight=”42,44,46″]
@Test
public void teste() {
final List<List<Integer>> listas = new ArrayList<List<Integer>>() {
{
add(new LinkedList<Integer>());
add(new ArrayList<Integer>());
}
};

for (List<Integer> lista : listas) {
final String nomeImplemetacao = lista.getClass().getSimpleName();
// add
long inicio = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
lista.add(i);
}
long fim = System.currentTimeMillis();
long duration = fim – inicio;
System.out.println(nomeImplemetacao + " add: " + duration);

// get
inicio = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
lista.get(i);
}
fim = System.currentTimeMillis();
duration = fim – inicio;
System.out.println(nomeImplemetacao + " get: " + duration);

// remove
inicio = System.currentTimeMillis();
for (int i = 99999; i >= 0; i–) {
lista.remove(i);
}
fim = System.currentTimeMillis();
duration = fim – inicio;
System.out.println(nomeImplemetacao + " remove: " + duration);
}
}
// Saídas:
// LinkedList add: 22
// LinkedList get: 9172
// LinkedList remove: 9186
// ArrayList add: 23
// ArrayList get: 4
// ArrayList remove: 14736
[/code]

LinkedList é mais performático ao adicionar (add) e remover (remove), no entanto, bem pior ao obter um item (get), se comparado ao ArrayList. Por tanto, é importante fazer uma análise detalhada, antes de escolher a implementação de List, principalmente quando falamos em milhares ou milhões de itens.

Vale ressaltar a importância do uso da interface List. Ao criar um método, use sempre referenciar a interface mais genérica, desta forma obtemos um baixo acoplamento, podemos trocar a implementação, já que estamos programando para a interface.

Vector

Vector é o mais antiga das implementações, já existia na versão 1.0 do Java, antes mesmo da inclusão da API Collection. Com a chegada da Collection, o Vector foi adaptado e virou uma implementação de List.

Vector e ArrayList são muito parecidos, alguns dizem que são a mesma coisa. Se alterarmos a instância do de ArrayList para Vector, provavelmente você não notará diferenças.

Mas a grande diferença entre as duas implementações é que o Vector é sincronizado, e o ArrayList não. Quer dizer que caso sua aplicação necessite ser thread-safe em determinado ponto, use Vector e você estará garantido.

No ArrayList, quando a lista está cheia, a mesma aumenta-se em 50%, já no Vector o percentual sobe para 100%, ou seja, caso você tenha uma Vector de 10 posições todas ocupadas, você terá na verdade uma alocação de 20 posições, sendo que 10 estarão vazias.

Até mais galera!