Cómo comprobar si una lista tiene elementos duplicados en Java

Introducción

En este laboratorio, aprenderás cómo verificar de manera eficiente si una List de Java contiene elementos duplicados. Exploraremos una técnica común y efectiva que utiliza la estructura de datos HashSet.

Primero, implementarás un método que aprovecha la propiedad de elementos únicos de HashSet para detectar duplicados recorriendo la lista y agregando elementos al conjunto. Si un elemento ya está presente en el conjunto, se ha encontrado un duplicado. Posteriormente, aprenderás un enfoque alternativo comparando el tamaño de la lista original con el tamaño de un HashSet llenado con los elementos de la lista. Finalmente, probarás tu implementación en varios escenarios, incluyendo listas nulas y vacías, para garantizar su robustez.

Utilizar HashSet para la detección de duplicados

En este paso, exploraremos cómo utilizar un HashSet en Java para detectar de manera eficiente elementos duplicados dentro de una colección. HashSet es parte del Marco de Colecciones de Java (Java Collections Framework) y es especialmente útil para almacenar elementos únicos.

Primero, creemos un nuevo archivo Java llamado DuplicateDetector.java en tu directorio ~/project. Puedes hacer esto utilizando el Explorador de Archivos del WebIDE en el lado izquierdo. Haz clic derecho en el área ~/project, selecciona "Nuevo Archivo" y escribe DuplicateDetector.java.

Ahora, abre el archivo DuplicateDetector.java en el Editor de Código y agrega el siguiente 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
    }
}

Comprendamos las partes clave de este código:

• import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set;: Estas líneas importan las clases necesarias del Marco de Colecciones de Java.
• public static boolean containsDuplicates(List<String> list): Este es un método que toma una List de objetos String como entrada y devuelve true si contiene duplicados, y false en caso contrario.
• Set<String> uniqueElements = new HashSet<>();: Esto crea un HashSet vacío llamado uniqueElements. HashSet está diseñado para almacenar solo elementos únicos.
• for (String element : list): Este bucle recorre cada element en la list de entrada.
• if (uniqueElements.contains(element)): Esto verifica si el element actual ya está presente en el HashSet uniqueElements. Si es así, significa que hemos encontrado un duplicado, y el método devuelve true.
• uniqueElements.add(element);: Si el elemento no está ya en el HashSet, se agrega. Debido a que HashSet solo almacena elementos únicos, agregar un elemento que ya está presente no tiene efecto.
• return false;: Si el bucle se completa sin encontrar ningún duplicado, el método devuelve false.
• El método main demuestra cómo utilizar el método containsDuplicates con listas de ejemplo.

Guarda el archivo DuplicateDetector.java (Ctrl+S o Cmd+S).

Ahora, compilemos y ejecutemos este programa en la Terminal. Asegúrate de estar en el directorio ~/project.

Compila el código:

javac DuplicateDetector.java

Si no hay errores de compilación, no verás salida alguna.

Ahora, ejecuta el código compilado:

java DuplicateDetector

Deberías ver una salida similar a esta:

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

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

Esta salida confirma que nuestro método containsDuplicates identificó correctamente la lista con duplicados. Utilizar un HashSet es una forma eficiente de comprobar duplicados porque comprobar la presencia de un elemento en un HashSet (utilizando contains()) es muy rápido, en promedio.

Comparar el tamaño de la lista con el tamaño del conjunto

En el paso anterior, utilizamos un HashSet para comprobar duplicados recorriendo la lista y agregando elementos al conjunto. Una forma más simple y a menudo más eficiente de detectar duplicados es comparar el tamaño de la lista original con el tamaño de un HashSet creado a partir de esa lista.

Recuerda que un HashSet solo almacena elementos únicos. Si una lista contiene duplicados, el tamaño de un HashSet creado a partir de esa lista será menor que el tamaño de la lista original. Si no hay duplicados, los tamaños serán iguales.

Modifiquemos nuestro archivo DuplicateDetector.java para implementar este enfoque. Abre ~/project/DuplicateDetector.java en el Editor de Código.

Reemplaza el método containsDuplicates con el siguiente 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();
    }

Esto es lo que sucede en el nuevo código:

• Set<String> uniqueElements = new HashSet<>(list);: Esta línea crea directamente un HashSet e inicializa con todos los elementos de la list de entrada. El HashSet maneja automáticamente la unicidad, por lo que cualquier elemento duplicado de la lista no se agregará al conjunto.
• return list.size() != uniqueElements.size();: Esta línea compara el número de elementos en la list original (list.size()) con el número de elementos únicos en el HashSet (uniqueElements.size()). Si los tamaños son diferentes (!=), significa que había duplicados en la lista, y el método devuelve true. Si los tamaños son iguales, no había duplicados, y el método devuelve false.

El método main puede permanecer igual ya que ya llama al método containsDuplicates.

Guarda el archivo DuplicateDetector.java (Ctrl+S o Cmd+S).

Ahora, compilemos y ejecutemos el programa modificado. Asegúrate de estar en el directorio ~/project en la Terminal.

Compila el código:

javac DuplicateDetector.java

Ejecuta el código compilado:

java DuplicateDetector

Deberías ver la misma salida que antes:

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

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

Esto confirma que nuestro nuevo método más simple para detectar duplicados utilizando la comparación de tamaños funciona correctamente. Este enfoque es generalmente más conciso y a menudo más eficiente que recorrer y comprobar la contención uno por uno, especialmente para listas más grandes.

Probar con listas nulas y vacías

En la programación del mundo real, es importante considerar casos extremos, como cuando una lista puede estar vacía o incluso ser null. Nuestro método containsDuplicates actual funciona bien para listas con elementos, pero ¿qué pasa si pasamos una lista vacía o una lista null?

Probemos esto agregando más ejemplos a nuestro método main en ~/project/DuplicateDetector.java. Abre el archivo en el Editor de Código y agrega las siguientes líneas al método main, después del 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));

Guarda el archivo (Ctrl+S o Cmd+S).

Ahora, compila y ejecuta el programa nuevamente.

Compila:

javac DuplicateDetector.java

Ejecuta:

java DuplicateDetector

Deberías ver la salida para la lista vacía:

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

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

Empty list: []
Contains duplicates? false

La salida para la lista vacía es correcta; una lista vacía no contiene duplicados.

Sin embargo, si descomentas la línea System.out.println("Contains duplicates? " + containsDuplicates(nullList)); y intentas compilar y ejecutar, obtendrás una NullPointerException. Esto sucede porque estamos intentando crear un HashSet a partir de una lista null, lo cual no está permitido.

Para hacer que nuestro método containsDuplicates sea más robusto, debemos manejar el caso en el que la lista de entrada sea null. Podemos agregar una comprobación al principio del método.

Modifica el método containsDuplicates en ~/project/DuplicateDetector.java para incluir una comprobación de null:

    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();
    }

Ahora, descomenta la línea que prueba la lista null en el método main:

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

Guarda el archivo (Ctrl+S o Cmd+S).

Compila y ejecuta el programa una última vez.

Compila:

javac DuplicateDetector.java

Ejecuta:

java DuplicateDetector

La salida ahora debe incluir el resultado para la lista null sin que se produzca un error:

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

Al agregar la comprobación de null, nuestro método containsDuplicates es ahora más robusto y puede manejar entradas null de manera adecuada. Esta es una práctica importante en la programación para evitar errores inesperados.

Resumen

En este laboratorio (lab), aprendimos cómo comprobar si una List de Java contiene elementos duplicados. Exploramos el uso de un HashSet para una detección eficiente de duplicados. Al recorrer la lista e intentar agregar cada elemento a un HashSet, podemos determinar rápidamente si un elemento ya está presente, lo que indica un duplicado.

También aprendimos un método alternativo comparando el tamaño de la lista original con el tamaño de un HashSet creado a partir de la lista. Si los tamaños son diferentes, significa que hay duplicados. Finalmente, consideramos casos extremos probando los métodos con listas nulas y vacías para garantizar la robustez.