Herramientas de usuario

Herramientas del sitio


bloque3:estructurasdatos

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 List y permite alacenar valores null.

Solo permite guardar objetos, por lo que al guardar un tipo primitivo, se convertirá automáticamente a su 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>.

ArrayList<Integer> listaEnteros = new ArrayList<Integer>();
 
ArrayList<String> listaCadenas = new ArrayList<String>();
 
ArrayList<Persona> listaPersonas = new ArrayList<Persona>();

Métodos de ArrayList

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

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.
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
   } 
}

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 Iterable. Con ella tenemos un método iterator() que nos devuelve un objeto 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.
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
   }
}

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

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:

Stack<String> pilaStrings = new Stack<String>();
 
Stack<Persona> pilaPersonas = new Stack<Persona>();

Ejemplo de uso:

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

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.

LinkedList<String> listaEnlazada = new LinkedList<String>();

Otras Colecciones

Dentro de las colecciones existen 3 interfaces principales: List, Set y 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.

KeyValue
714435667RPersona (nombre = “Juan”, apellidos = “López”)
985543264XPersona (nombre = “Maria”, apellidos = “Martinez”)
98773255LPersona (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.

© 2020 Fernando Valdeón

bloque3/estructurasdatos.txt · Última modificación: 15/02/2019 13:25 por Fernando Valdeón