Como Verificar se uma Lista Possui Elementos Duplicados em Java

Introdução

Neste laboratório, você aprenderá como verificar eficientemente se uma List Java contém elementos duplicados. Exploraremos uma técnica comum e eficaz que utiliza a estrutura de dados HashSet.

Primeiramente, você implementará um método que aproveita a propriedade de elementos únicos do HashSet para detectar duplicatas, iterando pela lista e adicionando elementos ao conjunto. Se um elemento já estiver presente no conjunto, uma duplicata é encontrada. Posteriormente, você aprenderá uma abordagem alternativa, comparando o tamanho da lista original com o tamanho de um HashSet preenchido com os elementos da lista. Finalmente, você testará sua implementação com vários cenários, incluindo listas nulas e vazias, para garantir a robustez.

Usar HashSet para Detecção de Duplicatas

Nesta etapa, exploraremos como usar um HashSet em Java para detectar eficientemente elementos duplicados dentro de uma coleção. HashSet faz parte do Java Collections Framework e é particularmente útil para armazenar elementos únicos.

Primeiro, vamos criar um novo arquivo Java chamado DuplicateDetector.java em seu diretório ~/project. Você pode fazer isso usando o File Explorer do WebIDE à esquerda. Clique com o botão direito na área ~/project, selecione "New File" e digite DuplicateDetector.java.

Agora, abra o arquivo DuplicateDetector.java no Code Editor e adicione o seguinte código:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateDetector {

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet to store unique elements
        Set<String> uniqueElements = new HashSet<>();

        // Iterate through the list
        for (String element : list) {
            // If the element is already in the HashSet, it's a duplicate
            if (uniqueElements.contains(element)) {
                return true; // Found a duplicate
            }
            // Otherwise, add the element to the HashSet
            uniqueElements.add(element);
        }

        // If the loop finishes without finding duplicates, return false
        return false;
    }

    public static void main(String[] args) {
        // Example usage
        List<String> myListWithDuplicates = new ArrayList<>();
        myListWithDuplicates.add("apple");
        myListWithDuplicates.add("banana");
        myListWithDuplicates.add("apple"); // Duplicate
        myListWithDuplicates.add("orange");

        List<String> myListWithoutDuplicates = new ArrayList<>();
        myListWithoutDuplicates.add("grape");
        myListWithoutDuplicates.add("mango");
        myListWithoutDuplicates.add("kiwi");

        System.out.println("List with duplicates: " + myListWithDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithDuplicates)); // Expected: true

        System.out.println("\nList without duplicates: " + myListWithoutDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithoutDuplicates)); // Expected: false
    }
}

Vamos entender as partes-chave deste código:

• import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set;: Estas linhas importam as classes necessárias do Java Collections Framework.
• public static boolean containsDuplicates(List<String> list): Este é um método que recebe uma List de objetos String como entrada e retorna true se ela contém duplicatas, e false caso contrário.
• Set<String> uniqueElements = new HashSet<>();: Isso cria um HashSet vazio chamado uniqueElements. HashSet é projetado para armazenar apenas elementos únicos.
• for (String element : list): Este loop itera por cada element na list de entrada.
• if (uniqueElements.contains(element)): Isso verifica se o element atual já está presente no HashSet uniqueElements. Se estiver, significa que encontramos uma duplicata, e o método retorna true.
• uniqueElements.add(element);: Se o elemento não estiver no HashSet, ele é adicionado. Como HashSet armazena apenas elementos únicos, adicionar um elemento que já está presente não tem efeito.
• return false;: Se o loop for concluído sem encontrar nenhuma duplicata, o método retorna false.
• O método main demonstra como usar o método containsDuplicates com listas de exemplo.

Salve o arquivo DuplicateDetector.java (Ctrl+S ou Cmd+S).

Agora, vamos compilar e executar este programa no Terminal. Certifique-se de estar no diretório ~/project.

Compile o código:

javac DuplicateDetector.java

Se não houver erros de compilação, você não verá nenhuma saída.

Agora, execute o código compilado:

java DuplicateDetector

Você deve ver uma saída semelhante a esta:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Esta saída confirma que nosso método containsDuplicates identificou corretamente a lista com duplicatas. Usar um HashSet é uma maneira eficiente de verificar duplicatas porque verificar a presença de um elemento em um HashSet (usando contains()) é muito rápido, em média.

Comparar o Tamanho da Lista com o Tamanho do Conjunto

Na etapa anterior, usamos um HashSet para verificar duplicatas iterando pela lista e adicionando elementos ao conjunto. Uma maneira mais simples e, muitas vezes, mais eficiente de detectar duplicatas é comparando o tamanho da lista original com o tamanho de um HashSet criado a partir dessa lista.

Lembre-se que um HashSet armazena apenas elementos únicos. Se uma lista contiver duplicatas, o tamanho de um HashSet criado a partir dessa lista será menor que o tamanho da lista original. Se não houver duplicatas, os tamanhos serão os mesmos.

Vamos modificar nosso arquivo DuplicateDetector.java para implementar essa abordagem. Abra ~/project/DuplicateDetector.java no Code Editor.

Substitua o método containsDuplicates pelo seguinte código:

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet from the list
        Set<String> uniqueElements = new HashSet<>(list);

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Aqui está o que está acontecendo no novo código:

• Set<String> uniqueElements = new HashSet<>(list);: Esta linha cria diretamente um HashSet e o inicializa com todos os elementos da list de entrada. O HashSet lida automaticamente com a unicidade, então quaisquer elementos duplicados da lista não serão adicionados ao conjunto.
• return list.size() != uniqueElements.size();: Esta linha compara o número de elementos na list original (list.size()) com o número de elementos únicos no HashSet (uniqueElements.size()). Se os tamanhos forem diferentes (!=), significa que havia duplicatas na lista, e o método retorna true. Se os tamanhos forem os mesmos, não havia duplicatas, e o método retorna false.

O método main pode permanecer o mesmo, pois ele já chama o método containsDuplicates.

Salve o arquivo DuplicateDetector.java (Ctrl+S ou Cmd+S).

Agora, vamos compilar e executar o programa modificado. Certifique-se de estar no diretório ~/project no Terminal.

Compile o código:

javac DuplicateDetector.java

Execute o código compilado:

java DuplicateDetector

Você deve ver a mesma saída de antes:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Isso confirma que nosso novo método, mais simples, para detectar duplicatas usando a comparação de tamanho funciona corretamente. Essa abordagem é geralmente mais concisa e, muitas vezes, mais eficiente do que iterar e verificar a contenção um por um, especialmente para listas maiores.

Testar com Listas Nulas e Vazias

Na programação do mundo real, é importante considerar casos extremos (edge cases), como quando uma lista pode estar vazia ou até mesmo ser null. Nosso método containsDuplicates atual funciona bem para listas com elementos, mas o que acontece se passarmos uma lista vazia ou uma lista null?

Vamos testar isso adicionando mais exemplos ao nosso método main em ~/project/DuplicateDetector.java. Abra o arquivo no Code Editor e adicione as seguintes linhas ao método main, após o código existente:

        System.out.println("\nEmpty list: " + new ArrayList<>());
        System.out.println("Contains duplicates? " + containsDuplicates(new ArrayList<>())); // Expected: false

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        // The following line will cause a NullPointerException if not handled
        // System.out.println("Contains duplicates? " + containsDuplicates(nullList));

Salve o arquivo (Ctrl+S ou Cmd+S).

Agora, compile e execute o programa novamente.

Compilar:

javac DuplicateDetector.java

Executar:

java DuplicateDetector

Você deve ver a saída para a lista vazia:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

A saída para a lista vazia está correta; uma lista vazia não contém duplicatas.

No entanto, se você descomentar a linha System.out.println("Contains duplicates? " + containsDuplicates(nullList)); e tentar compilar e executar, você obterá um NullPointerException. Isso acontece porque estamos tentando criar um HashSet a partir de uma lista null, o que não é permitido.

Para tornar nosso método containsDuplicates mais robusto, devemos tratar o caso em que a lista de entrada é null. Podemos adicionar uma verificação no início do método.

Modifique o método containsDuplicates em ~/project/DuplicateDetector.java para incluir uma verificação de nulo:

    public static boolean containsDuplicates(List<String> list) {
        // Handle null input
        if (list == null) {
            return false; // A null list does not contain duplicates
        }

        // Create a HashSet from the list
        Set<String> uniqueElements = new HashSet<>(list);

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Agora, descomente a linha que testa a lista nula no método main:

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        System.out.println("Contains duplicates? " + containsDuplicates(nullList)); // Expected: false

Salve o arquivo (Ctrl+S ou Cmd+S).

Compile e execute o programa pela última vez.

Compilar:

javac DuplicateDetector.java

Executar:

java DuplicateDetector

A saída agora deve incluir o resultado para a lista nula sem travar:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

Null list: null
Contains duplicates? false

Ao adicionar a verificação de nulo, nosso método containsDuplicates agora é mais robusto e pode lidar com a entrada null de forma adequada. Esta é uma prática importante na programação para evitar erros inesperados.

Resumo

Neste laboratório, aprendemos como verificar se uma List Java contém elementos duplicados. Exploramos o uso de um HashSet para detecção eficiente de duplicatas. Ao iterar pela lista e tentar adicionar cada elemento a um HashSet, podemos determinar rapidamente se um elemento já está presente, indicando uma duplicata.

Também aprendemos um método alternativo, comparando o tamanho da lista original com o tamanho de um HashSet criado a partir da lista. Se os tamanhos forem diferentes, isso significa a presença de duplicatas. Finalmente, consideramos casos extremos (edge cases) testando os métodos com listas nulas e vazias para garantir a robustez.