====== Estructuras de datos dinámicas ======
Hasta ahora conocemos los arrays, como la estructura de datos que me permite almacenar una serie de datos del mismo tipo. 

Como hemos visto los arrays tienen un tamaño fíjo, que se indica en el momento de su creación.

Existen otras estructuras de datos, que funcionan de forma similar a los arrays, pero aumentan su capacidad o la disminuyen dependiendo de la necesidad. Todo esto en tiempo de ejecución.

Las siguientes clases implementan la interface ''List'' por lo que tienen método comunes.

===== Clase ArrayList =====
La clase ArrayList representa una de las estructura de datos más usadas en Java.

Consiste en un array dinámico por lo que no hay que definirle un tamaño. Cuando añadimos elementos amplia su tamaño, y cuando los borramos lo reduce.
Implementa los métodos de la interfaz [[https://docs.oracle.com/javase/8/docs/api/java/util/List.html|List]] y permite alacenar valores ''null''.

Solo permite guardar objetos, por lo que al guardar un tipo primitivo, se convertirá automáticamente a su [[bloque3:wrappers|objeto envoltorio]].

==== Instanciar un ArrayList ====
Las colecciones, como en este caso ArrayList, son tipo de datos //raw//. Esto quiere decir que debemos facilitarle al compilador el tipo de datos que almacenará: ''<tipo_datos>''.

<code java>
ArrayList<Integer> listaEnteros = new ArrayList<Integer>();

ArrayList<String> listaCadenas = new ArrayList<String>();

ArrayList<Persona> listaPersonas = new ArrayList<Persona>();
</code>

==== Métodos de ArrayList ====

<code java>
ArrayList<String> lista = new ArrayList<String>();

//Añade el elemento al ArrayList
lista.add("Elemento");

//Añade el elemento al ArrayList en la posición 'n'
lista.add(n, "Elemento 2");

//Devuelve el número de elementos del ArrayList
lista.size();

//Devuelve el elemento en la posición 2 del ArrayList
lista.get(2);

//Comprueba si existe el elemento ('Elemento') 
lista.contains("Elemento");

//Devuelve la posición de la primera ocurrencia ('Elemento')  
lista.indexOf("Elemento");

//Devuelve la posición de la última ocurrencia ('Elemento')   
lista.lastIndexOf("Elemento");

//Borra el elemento de la posición '5'   
lista.remove(5); 

Borra la primera ocurrencia del "Elemento" 
lista.remove("Elemento");

//Borra todos los elementos de ArrayList   
lista.clear();

//Devuelve True si el ArrayList está vacío.
lista.isEmpty();  

//Copiar un ArrayList 
ArrayList arrayListCopia = (ArrayList) lista.clone();  

//Pasa el ArrayList a un Array 
String[] array = lista.toArray();

</code>

===== Recorrer una lista =====
Existen 3 formas principales para recorrer una lista:
  * **bucle for**: se recorre como siempre, llamando al método ''size()'' para comprobar su tamaño. Puedo añadir elementos a la lista mientras la recorro, pero se debe tener cuidado al borrar.
  * **con ''Iterator''**: la forma más recomendable __si debo borrar elementos__ mientras recorro la lista.
  * **bucle for each**: perfecto para recorrer la lista sin modificarla.

==== Bucle for====
Podemos recorrer un ArrayList del mismo modo que lo hacemos con un array estático.

  * Para saber su tamaño usamos el método ''size()''.
  * La primera posición de un ArrayList es la posición **0**.

<code java>
ArrayList<String> listaNombres = new ArrayList<String>();

//Añado 4 elementos seguidos al ArrayList

listaNombres.add("Jose");
listaNombres.add("Marta");
listaNombres.add("Juan");
listaNombres.add("Laura");

//Recorro el array y muestro los elementos
for (int i = 0; i < listaNombres.size(); i++){
   System.out.println(listaNombres.get(i)); 
}

//Cuidado al borrar
for (int i = 0; i < listaNombres.size(); i++){
   if(listaNombres.get(i).equals("Juan"){
      listaNombres.remove(i);
      //La i se incrementa, pero hay un elemento menos en la lista
      //"Laura" pasa a ser el elemento en la posición i actual
      //Y me la saltaré porque la i se incrementa
   } 
}
</code>

Como cada iteración del bucle se comprueba llamando al método ''size()'', puedo añadir o eliminar en tiempo real, ya que size() calculará el tamaño actual en cada iteración. 

Ojo, si borro el elemento en la posición ''i'', ya que ahora la posición ''i'' representará al siguiente elemento.
==== Interface Iterator ====
Todas las listas implementan la interface 
[[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html |Iterable]]. Con ella tenemos un método ''iterator()'' que nos devuelve un objeto [[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html|Iterator]]

Los objetos ''Iterator'' se usan para recorrer (iterar) colecciones de datos de cualquier tipo y tiene siempre 3 métodos:
  * ''hasNext()'' : Comprueba si quedan elementos en el iterador
  * ''next()'' : Devuelve el siguiente elemento del iterador
  * ''remove()'' : Elimina el elemento actual sobre el que se sitúa el iterador.

<code java>
ArrayList<String> lista = new ArrayList<String>();

// Añadimos 10 Elementos al ArrayList
for (int i = 1; i <= 10; i++){
   lista.add("Elemento " + i); 
}

//Obtengo el iterador
Iterator<String> iterador = lista.iterator();

while(iterador.hasNext()){
   String elemento = iterador.next(); //Accedo a cada elemento
   System.out.println(elemento); //Muestro por pantalla
   if(elemento.equals("Elemento 3"){
       iterador.remove(); //Borro el elemento actual
   }
}
</code>


==== Bucle for each====
Conocido como ''foreach'' o for mejorado, es una versión del bucle ''for'' enfocada en recorrer listas. **No se puede usar para borrar elementos.**

Se le indican 3 cosas:
  * Tipo de los datos de la lista
  * Variable con la que accedo a cada dato de la lista
  * Objeto lista (Cualquier tipo de Collection o Array)

<code java>
ArrayList<String> listaNombres = new ArrayList<String>();

listaNombres.add("Jose");
listaNombres.add("Marta");
listaNombres.add("Juan");
listaNombres.add("Laura");

for(String nombre : listaNombres){
   System.out.println(nombre);
}
</code>


===== Clase Stack =====
Una pila (stack) es una estructura que funciona como una lista //LIFO// (Last-In, First Out). El último elemento añadido, será el primero en salir.

//Se puede entender como una pila de platos, se van colocando uno encima de otro, y se van cogiendo desde arriba hacia abajo//.
 
Tiene 5 método principales, además de todos los que tiene la interface ''List''.
  * ''push(Elemento)'' : **apilar**, añade un elemento a la pila
  * ''pop()'' : **desapilar**, devuelve el último elemento de la pila y lo elimina de la pila 
  * ''empty()'' : indica si la pila está vacía 
  * ''peek()'' : devuelve el último elemento pero sin desapilarlo
  * ''search(Object)'' : indica la posición (int) del elemento en la pila

==== Uso de una pila ====
Instanciar una pila:
<code java>
Stack<String> pilaStrings = new Stack<String>();

Stack<Persona> pilaPersonas = new Stack<Persona>();
</code>

Ejemplo de uso:
<code java>
Stack<String> pila = new Stack<String>();

//apilar 3 elementos
pila.push("elemento1");
pila.push("elemento2");
pila.push("elemento3");

//mostrar por consola
for(String cadena : pila){
   System.out.println(cadena);
}

//elimina y devuelve elemento que está en la cima ("elemento3")
String desapilado = pila.pop();
System.out.println(desapilado);

//devuelve el elemento que está en la cima sin borrarlo ("elemento2")
String ultimo = pila.peek();
System.out.println(ultimo);
</code>


===== Clase LinkedList =====
La  usamos  cuando  lo  que  queremos  es  insertar  o  borrar  en  una  posición  determinada,  y  nos 
prima la eficiencia. Es una especie de ArrayList que no tiene definido una posición de inicio ni de fin.

Emplea básicamente lo mismos métodos, y de la misma forma, que la clase ArrayList, ya que son 
clases que implementan la interface ''List''.

<code java>
LinkedList<String> listaEnlazada = new LinkedList<String>();
</code>

===== Otras Colecciones =====
Dentro de las colecciones existen 3 interfaces principales: [[https://docs.oracle.com/javase/8/docs/api/java/util/List.html|List]], [[https://docs.oracle.com/javase/8/docs/api/java/util/Set.html|Set]] y [[https://docs.oracle.com/javase/8/docs/api/java/util/Map.html|Map]]. Cuando se crea una clase que implementa alguna de estas interfaces, está obligada a tener los métodos que indica dicha interfaz.

Por ahora hemos visto las colecciones de tipo ''List'', que son las más parecidas a los ''arrays''.

Pero dependiendo de la finalidad de la colección que necesitemos tenemos otros tipos de estructuras dinámicas: los conjuntos: ''Set'', y los mapas: ''Map''.


==== Conjuntos (Sets) ====
Los conjuntos en Java, al igual que los conjuntos en matemáticas, no permiten contener elementos duplicados. Implementan la interface ''Set'':

  * ''HashSet'' : Almacena los elementos en una tabla //hash// sin mantener ningún orden.
  * ''TreeSet'' : Almacena los elementos ordenandolos en función de sus valores. Necesita que los elementos implementen la interface ''Comparable''
  * ''LinkedHashSet'' : Almacena los elementos en función de su orden de inserción.


==== Mapas ====
Son colecciones que contienen asociaciones ''clave'':''valor''. Implementar la interface ''Map''
Esto quiere decir que al añadir un elemento a la colección debemos añadir una clave para identificarlo. Por ejemplo: ''key'' -> dni, ''value'' -> una persona

Para recuperar los elementos añadidos, debemos indicar la clave del elemento.

^Key^Value^
|714435667R|Persona (nombre = "Juan", apellidos = "López")|
|985543264X|Persona (nombre = "Maria", apellidos = "Martinez")|
|98773255L|Persona (nombre = "Javier", apellidos = "López")|

  * ''HashMap'': almacena las claves en una tabla //hash// sin orden. 
  * ''TreeMap'' : almacena las claves ordenandolas en función de sus valores.
  * ''LinkedHashMap'' : almacena las claves en función de su orden de inserción.

----

(c) {{date> %Y}} Fernando Valdeón