====== 04 - Estructura de datos dinámica: Colecciones y Maps ======

===== 1. Colecciones =====

Las **colecciones** son estructuras de datos avanzadas que **pueden cambiar de tamaño dinámicamente**. Todas las colecciones principales derivan de la interfaz base ''java.util.Collection''.

Principales métodos comunes de la interfaz ''Collection'':

  * ''int size()'': Devuelve el número de elementos.

  * ''boolean isEmpty()'': Indica si está vacía.
 
  * ''boolean contains (Object element)'': retorna verdadero si la colección tiene el elemento pasado como parámetro.

  * ''boolena add(Object element)'': Añade un elemento.

  * ''boolean remove(Object elementt)'': Elimina un elemento.

  * ''void clear()'': Vacía la colección.

==== 1.1 Genéricos y restricción de tipos primitivos ====

Las colecciones en Java hacen uso intensivo de los genéricos (definidos entre ''<>''), los cuales permiten especificar el tipo de datos que almacenará la colección en tiempo de compilación.

Las colecciones solo pueden almacenar objetos (tipos por referencia). **Está estrictamente prohibido utilizar tipos primitivos (''int'', ''double'', ''char'', ''boolean'', etc.) como parámetros de tipo genérico**.

Para trabajar con valores primitivos dentro de una colección, **es obligatorio utilizar sus correspondientes clases de envoltorio (''Integer'', ''Double'', ''Character'', ''Boolean'', etc.)**.

Gracias al Autoboxing y Unboxing automático de Java, la conversión entre el tipo primitivo y el objeto envoltorio se realiza de forma transparente:

<sxh java>
List<Integer> numeros = new ArrayList<>();

numeros.add(10); // Autoboxing: el int '10' se convierte automáticamente en Integer
numeros.add(20);

int primerNumero = numeros.get(0); // Unboxing: el Integer se convierte a int primitivo
</sxh>

==== 1.2 Polimorfismo y programación orientada a interfaces ====

Una de las mejores prácticas de diseño en Java es el principio de **programar hacia una interfaz, no hacia una implementación**.

Al crear una colección, se debe declarar la variable utilizando el tipo de la interfaz (''List'', ''Set''), e instanciar la clase concreta deseada (''ArrayList'', ''HashSet'').

<sxh java>
// No recomendado: Acopla el código a una implementación específica
ArrayList nombres = new ArrayList<>();
</sxh>

Declarar las variables utilizando la interfaz permite cambiar la implementación subyacente en una sola línea de código sin modificar el resto de la aplicación que consume la colección:

<sxh java>
List nombres = new ArrayList<>();

nombres.add("Ana");
nombres.add("Carlos");
IO.println(nombres.get(0));
</sxh>
==== 1.3 Conjuntos (Set) ====

Un ''Set'' es una colección que **NO permite elementos duplicados**.

Implementaciones más comunes:

  * ''HashSet'': Muy rápido. No garantiza ningún orden de los elementos.

  * ''LinkedHashSet'': Rápido. Mantiene el orden en el que se insertaron los elementos.
 
  * ''TreeSet'': Ordena los elementos automáticamente según su valor.

<sxh java>
Set<Integer> numbers = new HashSet<Integer>(); //Una práctica habitual es definir el tipo de datos conjunto como la interfaz genérica (Set)

numbers.add(10);
numbers.add(5);
numbers.add(10); // Devuelve false y NO se añade porque está duplicado
</sxh>

A partir de Java 9, se pueden crear conjuntos de forma estática mediante el método factory ''Set.of()'':

<sxh java>
Set<Integer> numbers = Set.of(2, 10, 3, 23, 99);
</sxh>

<note important>Si inicializamos un conjunto con el método ''of()'', el conjunto que se crea es **inmutable**, es decir, no podemos cambiarlo, con lo que no podremos añadir, eliminar ni modificar elementos.</note>

Para recorrer un conjunto se utiliza habitualmente un bucle ''for-each'':

<sxh java>
for (Integer number : numbers) {
    IO.println(number);
}
</sxh>

==== 1.4 Listas (List) ====

Un ''List'' es una colección ordenada que **SÍ permite elementos duplicados** y cuenta con **acceso posicional mediante índice** (comenzando siempre desde $0$).

Implementaciones principales:

  * ''ArrayList'': Basada en un ''array'' interno redimensionable. Muy eficiente para consultar elementos por índice (''get'').\\ \\
  * ''LinkedList'': Lista doblemente enlazada. Muy eficiente al realizar inserciones o eliminaciones frecuentes en posiciones intermedias.

Métodos clave de la interfaz ''List'':

  * ''E get(int index)'': Obtiene un elemento partiendo de su posición (''index'').\\ \\
  * ''E set(int index, E element)'': Cambia el elemento almacenado en una posición de la lista (''index''), por otro (''element'').\\ \\
  * ''void add(int index, E element)'': Inserta un elemento (''element'') en la lista en una posición concreta (''index''), desplazando los existentes. Si le pasamos solo el elemento (''element'') la inserción la hará al final de la lista.\\ \\
  * ''E remove(int index)'': Elimina un elemento indicando su posición (''index'') en la lista.\\ \\
  * ''boolean addAll(int index, Collection<? extends E> c)'': Inserta una colección pasada por parámetro en una posición de la lista, desplazando el resto de elementos.\\ \\
  * ''int indexOf(Object o)'': Devuelve la posición de un elemento en la lista o $-1$ si el elemento no está en la lista.\\ \\
  * ''int lastIndexOf(Object o)'': Devuelve la última ocurrencia del objeto en la lista (dado que la lista si puede almacenar duplicados) o $-1$ si el elemento no está en la lista.\\ \\
  * ''List<E> subList(int from, int to)'': Genera una sublista (una vista parcial de la lista) con los elementos comprendidos entre la posición inicial (''from'', incluida) y la posición final (''to'', no incluida).

Las listas se utilizan de forma muy parecida a los conjuntos:

<sxh java>
        List<Integer> numbers = new ArrayList<>();

        numbers.add(1); // Añade un elemento al final de la lista.
        numbers.add(3); // Añade otro elemento al final de la lista.
        numbers.add(1,2); // Añade en la posición 1 el elemento 2.
        numbers.add(numbers.get(1)+numbers.get(2)); // Suma los valores contenidos en la posición 1 y 2, y lo agrega al final.
        numbers.remove(0); // Elimina el primer elementos de la lista.
        
        for (Integer number: numbers)
            IO.println("Elemento:" + number); // Muestra la lista.
        }    
        
</sxh>


Al igual que con los conjuntos, se pueden inicializar **listas inmutables** mediante ''List.of()'':
<sxh java>
        List<Integer> numbers = List.of(1, 3, 5, 67);
</sxh>

==== 1.5 Iteración segura con Iterator ====

Cuando se recorre una colección utilizando un bucle ''for-each'' tradicional, no está permitido modificar ni eliminar elementos de la colección. Si se intenta realizar un ''remove()'' o un ''add()'' directamente sobre la colección durante la iteración, Java lanzará una excepción ''ConcurrentModificationException''.

Para eliminar elementos de forma segura mientras se recorre una colección, se debe emplear un objeto ''Iterator'':

  * ''hasNext()'': Devuelve ''true'' si quedan elementos por recorrer.\\ \\
  * ''next()'': Avanza al siguiente elemento y lo devuelve.\\ \\
  * ''remove()'': Elimina de la colección el último elemento devuelto por ''next()''.\\ \\

<sxh java>
// Obtención del iterador
Iterator it = estudiantes.iterator();

while (it.hasNext()) {
    String nombre = it.next();
    if (nombre.startsWith("J")) {
        it.remove(); // Eliminación segura sin lanzar ConcurrentModificationException
    }
}
</sxh>
===== 2. Maps =====

Un ''Map'' es una estructura que almacena asociaciones de clave-valor (''Key'' $\rightarrow$ ''Value''). Las claves son únicas (no se pueden repetir) y sirven para acceder directamente al valor asociado.

==== 2.1 Conceptos clave e implementaciones ====

Implementaciones principales:

  * ''HashMap'': Sin orden específico en las claves.\\ \\
  * ''TreeMap'': Ordena las claves por valor.\\ \\
  * ''LinkedHashMap'': Mantiene el orden de inserción de las claves.\\ \\

Métodos clave de ''Map'':

  * ''V put(K key, V value)'': Asocia el valor (''value'') con la clave (''key'') en el ''map''. Si la clave no existe en el ''map'' crea un nuevo par clave-valor. Si ya existe, reemplazará el valor.\\ \\
  * ''V get(Object key)'': Obtiene el valor asociado a una clave (''key'') ya almacenada en el mapa. Si no existe la clave, retornará ''null''.\\ \\
  * ''V remove(Object key)'': Elimina la clave (''key'') y el valor (''value'') asociado. Retorna el valor asociado a la clave, por si lo queremos utilizar para algo, o ''null'', si la clave no existe.\\ \\
  * ''boolean containsKey(Object key)'': Devuelve ''true'' si el ''map'' tiene almacenada la clave (''key''). En caso contrario devolverá ''false''.\\ \\
  * ''boolean containsValue(Object value)'': Devuelve ''true'' si el ''map'' tiene almacenada el valor (''value''). En caso contrario devolverá ''false''.\\ \\
  * ''int size()'': Devuelve el número de pares clave-valor almacenado en el ''map''.\\ \\
  * ''boolean isEmpty()'': Devuelve ''true'' si el ''map'' está vacío, ''false'' en cualquier otro caso.\\ \\
  * ''void clear()'': Vacía el ''map''.\\ \\
  * ''Set<K> keySet()'': Devuelve el conjunto de claves contenidas en el ''map''.\\ \\

<sxh java>
Map<String, Integer> ages = new HashMap<String, Integer>();

ages.put("Ana", 20);
ages.put("Pedro", 25);
ages.put("María", 21); 
ages.put("Ana", 21); // Actualiza la edad de Ana a 21

for (String name : ages.keySet()) {
    IO.println(name + ": " + ages.get(name));
}
</sxh>

También es posible instanciar mapas inmutables con ''Map.of()'':

<sxh java>
        Map<String, Integer> ages = Map.of("Ana", 20, "Pedro", 25, "María", 21);
</sxh>

==== 2.2 Recorrido eficiente: keySet() vs. entrySet() ====

Existen dos formas principales de iterar sobre un mapa mediante un bucle ''for-each'':

=== Recorrido mediante keySet() ===

El método ''keySet()'' devuelve un conjunto con las claves del mapa. Para obtener el valor asociado a cada clave, es necesario llamar a ''map.get(clave)'' en cada iteración (lo que realiza una búsqueda adicional):

<sxh java>
// Menos eficiente: realiza una búsqueda extra en el mapa con .get() en cada iteración
for (String producto : precios.keySet()) {
    Double precio = precios.get(producto);
    IO.println(producto + " cuesta " + precio + "€");
}
</sxh>

=== Recorrido eficiente mediante entrySet() === 

El método ''entrySet()'' devuelve un conjunto de parejas clave-valor representadas por la interfaz interna ''Map.Entry<K, V>''. Permite acceder tanto a la clave (''getKey()'') como al valor (''getValue()'') de forma directa sin realizar búsquedas adicionales:

<sxh java>
// Recomendado y más eficiente para leer clave y valor simultáneamente
for (Map.Entry<String, Double> entrada : precios.entrySet()) {
   IO.println(entrada.getKey() + " cuesta " + entrada.getValue() + "€");
}
</sxh>

===== 3. Requisitos de los Objetos: Hash vs. Árboles =====

El comportamiento interno de las colecciones impone ciertos requisitos sobre las clases de los objetos que se almacenan en ellas.

==== 3.1 Estructuras basadas en Hash (HashSet, HashMap) ====

Las colecciones con el prefijo //Hash// utilizan una tabla de dispersión (//Hash Table//) para localizar elementos en tiempo constante $O(1)$.

Para que funcionen correctamente, la clase de los objetos almacenados **debe sobrescribir obligatoriamente los métodos ''equals()'' y ''hashCode()''** de ''Object'':

  * ''hashCode()'': Determina la casilla donde se guarda o busca el objeto.\\ \\
  * ''equals()'': Resuelve posibles colisiones para confirmar si dos objetos son exactamente iguales.
  * 
==== 3.2 Estructuras basadas en Árboles (TreeSet, TreeMap) ====

Las colecciones con el prefijo //Tree// mantienen sus elementos ordenados automáticamente. No utilizan ''hashCode()'', sino que requieren que los elementos se puedan comparar entre sí:

  * Los objetos deben implementar la interfaz ''Comparable'' (sobrescribiendo el método ''compareTo()'').\\ \\
  * Alternativamente, se debe pasar un objeto ''Comparator'' al constructor de la colección.

===== 4. La Clase de Utilidad java.util.Collections =====

La clase ''java.util.Collections'' (en plural) contiene exclusivamente métodos estáticos de utilidad diseñados para operar sobre listas y colecciones.

Principales métodos estáticos:

  * ''Collections.sort(lista)'': Ordena la lista en orden ascendente (según su orden natural).\\ \\
  * ''Collections.reverse(lista)'': Invierte el orden de los elementos en la lista.\\ \\
  * ''Collections.shuffle(lista)'': Desordena aleatoriamente los elementos de la lista.\\ \\
  * ''Collections.max(coleccion)'' / ''Collections.min(coleccion)'': Obtiene el elemento máximo o mínimo según su orden natural.\\ \\
  * ''Collections.frequency(coleccion, objeto)'': Cuenta cuántas veces aparece un elemento específico en la colección.\\ \\
  * ''Collections.unmodifiableList(lista)'': Devuelve una vista envuelta de solo lectura de la lista dada.\\ \\

<sxh java>
List<Integer> notas = new ArrayList<>();
notas.add(8);
notas.add(4);
notas.add(10);

Collections.sort(notas); // La lista ahora es [4, 8, 10]
Collections.reverse(notas); // La lista ahora es [10, 8, 4]
int notaMaxima = Collections.max(notas); // Devuelve 10
</sxh>

===== Ejercicios =====

=== Ejercicio 1 ===

Crea un programa que realice las siguientes acciones:

  * Declare una lista polimórfica de enteros de tipo ''List''.\\ \\
  * Solicite o añada manualmente $6$ calificaciones numéricas (valores entre $0$ y $10$).\\ \\
  * Utilice la clase ''Collections'' para:\\ \\
    * Obtener la nota máxima y la nota mínima.\\ \\
    * Ordenar la lista de notas de mayor a menor (orden descendente).\\ \\
  * Contar cuántas veces se repite la nota máxima en la lista mediante ''Collections.frequency()''.\\ \\
  * Calcule la media aritmética de las notas.

=== Ejercicio 2 ===

Crea un método estático que reciba una lista de cadenas de texto ''List'' y realice las siguientes transformaciones:

  * Elimine la primera y la última posición de la lista.\\ \\
  * Añada la palabra ''"INICIO"'' en el índice $0$ y la palabra ''"FIN"'' al final.\\ \\
  * Devuelva una nueva lista con los elementos invertidos en su orden, sin modificar la lista original pasada por parámetro.

=== Ejercicio 3 ===

Dada una lista inicial de direcciones de correo electrónico:

  * Intenta en un primer paso eliminar los correos que comiencen por ''"spam_"'' usando un bucle ''for-each'' tradicional y comprueba/explica en un comentario el error generado.\\ \\
  * Corrige el programa empleando un objeto ''Iterator'' y su método ''remove()'' para eliminar de forma segura todos los correos basura.

=== Ejercicio 4 ===

Crea un programa con una lista con elementos repetidos:

  * Convierte la lista a un conjunto utilizando la implementación ''HashSet'' e imprime el resultado. ¿Qué ocurre con el orden de las palabras?\\ \\
  * Convierte la lista a un conjunto utilizando la implementación ''LinkedHashSet'' e imprime el resultado. Compara la diferencia de orden respecto a ''HashSet''.

=== Ejercicio 5 ===

Desarrolla un programa de gestión de inventario para una tienda:

  * Crea un mapa ''Map<String, Integer>'' donde la clave sea el código/nombre del producto y el valor sea el stock disponible.\\ \\
  * Añada $4$ productos iniciales.\ \Simula una venta: actualiza el stock de uno de los productos reduciendo su cantidad.\\ \\
  * Simula una reposición: si el producto existe, incrementa su stock; si no existe, añádelo con stock inicial.\\ \\
  * Imprime por pantalla el inventario completo utilizando obligatoriamente el método ''entrySet()''.

=== Ejercicio 6 ===

Dado un texto/frase introducido por teclado o almacenado en una cadena (ej. ''"java es un lenguaje java orientado a objetos y java es popular"''):

  * Divide el texto en palabras individuales utilizando el método ''.split(" ")''.\\ \\
  * Utiliza un ''Map<String, Integer>'' para contar cuántas veces aparece cada palabra en el texto.\\ \\
  * Muestra al final cada palabra junto con su número total de apariciones.

=== Ejercicio 7 ===

Dada la clase ''Estudiante'' con las propiedades ''dni'' (''String'') y ''nombre'' (''String''):

  * Sobrescribe los métodos ''equals()'' y ''hashCode()'' tomando el ''dni'' como atributo identificativo único.\\ \\
  * Implementa la interfaz ''Comparable'' para ordenar estudiantes alfabéticamente por su ''nombre''.\\ \\
  * Crea un programa principal donde:\\ \\
    * Se intenten añadir dos estudiantes con el mismo DNI a un ''HashSet''. Comprueba que no se duplican.\\ \\
    * Se añadan los estudiantes a un ''TreeSet'' y se verifique que quedan ordenados alfabéticamente de forma automática.

=== Ejercicio 8 ===

Crea un sistema para clasificar alumnos por asignatura:

  * Declara un mapa ''Map<String, List>'' donde la clave sea el nombre de la asignatura (ej. "Programación", "Bases de Datos") y el valor sea una lista de nombres de alumnos matriculados.\\ \\
  * Implementa un método ''matricularAlumno(Map<String, List> mapa, String asignatura, String alumno)'' que:\\ \\
    * Verifique si la asignatura existe en el mapa. Si no existe, cree la lista vacía y la añada al mapa.\\ \\
    * Añada al alumno a la lista de esa asignatura.\\ \\
  * Recorre el mapa e imprime cada asignatura con su lista completa de alumnos matriculados.