Dicas para usar coleções

1. Lista de coleções

Como você deve se lembrar, Java tem coleções — uma ferramenta útil para armazenar objetos do mesmo tipo.

Vamos tentar relembrar as principais interfaces relacionadas à coleção:

Lista , Conjunto , Mapa e Fila .

Como sempre, as ferramentas não são necessariamente boas ou ruins - o que importa é se você as está usando para o propósito pretendido. E para isso, devemos entender a fundo suas especificidades para saber qual coleção usar e quando.

1. Lista

Vamos começar com a coleção mais usada.

Liste o mais próximo possível de um array antigo simples.

Essa coleção nos permite armazenar convenientemente uma lista de objetos do mesmo tipo sem nos preocuparmos com o tamanho da coleção em si, como faríamos se estivéssemos usando um array. Os elementos da coleção são acessados ​​por index. Se sabemos exatamente onde está um objeto e precisamos acessá-lo com frequência sem precisar adicionar ou remover elementos com frequência, uma Lista é ideal.

2. Definir

Set tem uma estrutura completamente diferente.

Set é mais adequado quando precisamos armazenar objetos únicos. Por exemplo, um conjunto de autores em uma biblioteca onde cada autor é único. Mas não podemos simplesmente pegar qualquer autor específico dele. Set nos permite verificar rapidamente se um determinado autor está presente em nossa biblioteca, ou seja, podemos verificar se um único objeto está presente em um Set . Também podemos iterar em toda a coleção, acessando cada elemento, mas fazer isso não é o ideal.

Em outras palavras, para nossa biblioteca, um Set pode representar a coleção de todos os autores exclusivos para verificar rapidamente se algum autor específico está presente.

3. Mapa

O mapa é mais como um arquivo, onde cada arquivo é assinado e pode armazenar objetos individuais ou estruturas inteiras. Map deve ser usado nos casos em que precisamos manter um mapeamento de um valor para outro.

Para Map , esses relacionamentos são chamados de pares chave-valor.

Poderíamos usar essa estrutura em nossa biblioteca usando objetos de autor como chaves e listas ( objetos de lista ) de livros como valores. Assim, após verificar um Set para ver se existe um objeto author na biblioteca, podemos usar o mesmo objeto author para obter uma List de seus livros de um Map .

4. Fila

Queue é uma coleção que — surpresa! — implementa o comportamento de uma fila. E a fila pode ser LIFO (Last In, First Out) ou FIFO (First In, First Out). Além do mais, a fila pode ser bidirecional ou "dupla extremidade".

Essa estrutura é útil quando os objetos adicionados à classe precisam ser usados ​​na ordem em que são recebidos. Por exemplo, pegue nossa biblioteca.

Podemos adicionar visitantes recém-chegados a uma Fila e atendê-los por sua vez, emitindo os livros que procuram.

Como podemos ver, cada uma dessas estruturas é boa se usada para o propósito a que se destina. E encontramos bons usos para todos os quatro tipos de coleções em um único exemplo de biblioteca.

2. Complexidade

Como já observado, as coleções que consideramos acima são interfaces, o que significa que elas devem ter implementações para que possamos utilizá-las.

Assim como martelar pregos com um microscópio não é a melhor ideia, nem toda implementação de uma coleção é adequada para todas as situações.

Ao escolher a ferramenta certa para um trabalho, normalmente observamos 2 características:

• Quão bem a ferramenta se encaixa no trabalho?
• Com que rapidez ele fará o trabalho?

Passamos algum tempo tentando descobrir como escolher uma ferramenta adequada para um trabalho, mas sua velocidade é algo novo.

Na computação, a velocidade de uma ferramenta geralmente é expressa em termos de complexidade de tempo e denotada por uma letra maiúscula O.

O que no mundo é a complexidade do tempo?

Em termos simples, a complexidade de tempo indica o tempo necessário para um algoritmo na coleção executar uma determinada ação (adicionar/remover um elemento, procurar um elemento).

ArrayList vs LinkedList

Vejamos isso usando duas implementações da interface List — ArrayList e LinkedList .

Para aparências externas, trabalhar com essas coleções é semelhante:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Como você pode ver, para ambos os tipos de coleção, adicionar, obter e remover elementos tem a mesma aparência. Isso ocorre porque essas são implementações na mesma interface. Mas é aí que as semelhanças terminam.

Devido às suas diferentes implementações da interface List , essas duas estruturas executam ações diferentes com mais eficiência do que outras.

Considere remover e adicionar um elemento.

Se precisarmos remover um elemento do meio de uma ArrayList , teremos que sobrescrever qualquer parte da lista após o elemento que removemos.

Suponha que temos uma lista de 5 elementos e queremos remover o terceiro.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Nesse caso, a remoção libera uma célula, então precisamos escrever o 4º elemento onde estava o 3º e o 5º onde estava o 4º.

Isso é altamente ineficiente.

O mesmo acontece ao adicionar um elemento no meio da lista.

LinkedList é estruturado de forma diferente. Adicionar ou remover elementos é rápido, pois só precisamos alterar as referências nos elementos anterior e seguinte, excluindo assim o objeto que estamos removendo da cadeia de elementos.

Voltando ao exemplo da mesma lista de 5 elementos, após retirar o 3º elemento, basta apenas alterar a referência do 2º elemento para o próximo elemento e a referência do 4º elemento para o anterior.

Quando um elemento é adicionado à lista, o mesmo processo acontece, mas ao contrário.

Observe quanto menos trabalho precisamos fazer em um LinkedList em comparação com um ArrayList . E isso é apenas 5 elementos. Se nossa lista tivesse 100 ou mais elementos, a superioridade do LinkedList se tornaria ainda mais perceptível.

Mas como a situação muda se acessarmos um elemento por índice?

Tudo é exatamente o oposto aqui.

Como ArrayList é estruturado como um array comum, obter qualquer elemento por seu índice será muito fácil para nós. Simplesmente movemos o ponteiro para um determinado local e obtemos o elemento da célula correspondente.

Mas um LinkedList simplesmente não funciona dessa maneira. Temos que percorrer todos os elementos da lista para encontrar o elemento com um determinado índice.

Vamos tentar expressar tudo isso em termos de grande O?

Vamos começar acessando um elemento por índice.

Em um ArrayList , isso acontece em uma etapa, independentemente de onde o elemento esteja localizado na lista. Seja no final ou no começo.

Neste caso, a complexidade de tempo será O(1) .

Em uma LinkedList , temos que iterar sobre um número de elementos igual ao valor do índice que precisamos.

A complexidade de tempo para tal ação é O(n) , onde n é o índice do elemento que precisamos.

Aqui você vê que o número que colocamos entre parênteses grandes corresponde ao número de ações executadas.

Shell voltamos a remover e adicionar?

Vamos começar com LinkedList.

Como não precisamos fazer um grande número de ações para adicionar ou remover um elemento, e a velocidade dessa operação não depende de forma alguma de onde o elemento está localizado, sua complexidade é expressa como O(1) e é dita ser constante.

A complexidade de tempo desta operação para ArrayList também é O(n) , que chamamos de complexidade linear.

Em algoritmos com complexidade linear, o tempo de execução depende diretamente do número de elementos a serem processados. Também pode depender da posição do elemento, se está no início da lista ou no final.

A complexidade de tempo também pode ser logarítmica. Isso é expresso como O(log n) .

Como exemplo, considere um TreeSet ordenado que consiste em 10 números. Queremos encontrar o número 2.

Como a lista está ordenada e não contém duplicatas, podemos dividi-la ao meio e verificar qual metade conteria o número desejado, descartar a parte irrelevante e então repetir este processo até chegar ao elemento desejado. Por fim, encontraremos (ou não) o número após o processamento do número log(n) de elementos.

Aqui está uma tabela que resume a complexidade de tempo do restante das coleções.

Agora que temos uma tabela mostrando a complexidade de tempo de coleções populares, podemos responder à pergunta por que, entre tantas coleções, usamos com mais frequência ArrayList , HashSet e HashMap .

É simplesmente que eles são os mais eficientes para a maioria das tarefas :)