Download UD06. Tipos List y Set con tipos genéricos

Unidad Didáctica 6
Tipos List y Set con tipos
genéricos
Fundamentos de Programación
Departamento de Lenguajes y Sistemas Informáticos
Versión 1.0.1
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Estructuras de datos predefinidas en Java
(Colecciones)


Java suministra una serie de Estructuras de Datos que
permiten modelar fácilmente problemas del mundo real
que involucran colecciones de datos.
Una Colección (Collection) es un tipo de datos que agrupa
a objetos de un mismo tipo.


Algunas colecciones admiten elementos duplicados, otras no.
Algunas mantienen los elementos ordenados según
determinados criterios, otras no.
UD 6: Tipos List y Set con tipos genéricos
Estructuras de datos predefinidas en Java
(Colecciones)

El uso de colecciones tiene numerosas ventajas:





Reduce el esfuerzo de programación puesto que proporciona
estructuras de datos y algoritmos útiles.
Incrementa la velocidad y la calidad de los programas, puesto
que Java ofrece implementaciones optimizadas y libres de
errores.
Simplifica la interoperabilidad y la reemplazabilidad entre
aplicaciones, puesto que facilita estructuras que se pueden
intercambiar entre distintos componentes.
Reduce esfuerzos de aprendizaje y diseño.
En Java las colecciones se representan mediante la
interfaz Collection del paquete java.util
UD 6: Tipos List y Set con tipos genéricos
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Interfaz Collection

Concepto:
Como se ha dicho, una Colección (Collection) es un tipo de datos
que agrupa a objetos de un mismo tipo.

Operaciones:


básicas:
¿colección vacía?, ¿contiene un elemento?, añadir, quitar, etc.
con grupos de elementos:
añadir un grupo, quitarlo, ¿los contiene?, borrar la colección, etc.
UD 6: Tipos List y Set con tipos genéricos
Interfaz Collection
La interfaz Collection en Java:




Pertenece al paquete java.util
Tiene un tipo genérico (le llamaremos <T>); es el tipo de
sus elementos.
Hereda de la interfaz Iterable<T>. Esta interfaz se verá
más adelante; permite iterar sobre los elementos de la
colección (recorrerlos sistemáticamente).
Los objetos “iterables” (los que heredan de Iterable)
permiten el uso de la sentencia for extendido, que se verá
en prácticas.
UD 6: Tipos List y Set con tipos genéricos
Interfaz Collection


No hay ninguna clase que implemente directamente la interfaz
Collection.
Cualquier clase que implemente una subinterfaz suya debe
tener al menos dos constructores:



Un constructor vacío, que crea una estructura vacía.
Un constructor con un argumento de tipo Collection, que crea un
objeto con los mismos elementos que la colección que recibe, con la
implementación correspondiente al constructor de la clase utilizada.
Este constructor se denomina “constructor copia”.
Java no permite obligar a que una clase tenga un determinado
constructor, pero todas las clases que implementan Collection
(sus subinterfaces), tienen los dos constructores anteriores.
UD 6: Tipos List y Set con tipos genéricos
Interfaz Collection

En esta lección vamos a ver en profundidad dos tipos de
colecciones, las listas (interfaz List) y los conjuntos
(interfaz Set).
<<interface>>
Iterable <T>
<<interface>>
Collection <T>
<<interface>>
List <T>
<<interface>>
Set <T>
etc.
UD 6: Tipos List y Set con tipos genéricos
etc.
Interfaz Collection. Métodos
package java.util;
public interface Collection<T> extends Iterable<T> {
// Operaciones básicas
int size();
boolean isEmpty();
boolean contains(Object o);
// Operaciones modificadoras
// Devuelven true si se modifica la colección
boolean add(T e);
boolean remove(Object o);
(sigue)
UD 6: Tipos List y Set con tipos genéricos
Interfaz Collection. Métodos
(continuación)
// Operaciones con grupos de elementos
// Las operaciones booleanas devuelven true si se
// modifica la colección
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends T> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
...
}
Nota: información detallada del contrato en http://java.sun.com/javase/6/docs/api/
- java.util – interfaz Collection
UD 6: Tipos List y Set con tipos genéricos
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista






Una lista es una secuencia de elementos en la que el
orden en el que estén los elementos (cuál es el primero,
cuál el segundo, etc.) es relevante.
En una lista cada elemento está referenciado mediante un
índice.
El índice del primer elemento es el 0.
Una lista puede contener elementos duplicados.
En Java, la lista se modela mediante la interfaz List, que
hereda de Collection, por lo que tiene todos sus
métodos.
Añade algunos métodos: los que involucran a los índices.
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Métodos
public interface List<T> extends Collection<T> {
//Acceso posicional
T get(int index);
T set(int index, T element);
void add(int index, T element);
boolean remove(int index);
//Búsqueda
int indexOf(Object o);
int lastIndexOf(Object o);
//Vista de subrango
List<T> subList(int fromIndex, int toIndex);
...
}
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Métodos




List extiende a Collection, por lo que tiene todos sus
métodos.
La operación add(T e) añade el elemento al final de la
lista. Siempre devuelve true.
La operación remove(T e) elimina la primera aparición
del elemento e en la lista, si hay alguno; en ese caso
devuelve true.
Los métodos indexOf y lastIndexOf devuelven -1 si el
elemento no está en la lista.
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Métodos

Todos los métodos que contienen índices elevan la excepción
IndexOutOfBoundsException si los índices se salen de los rangos
adecuados. Esto funciona del mismo modo en el tipo Vector.


Para las operaciones
 T get(int index);
 T set(int index, T element);
 boolean remove(int index);
el rango válido para el índice es
(0 <= index && index < size())
Para la operación
 void add(int index, T element);
el rango válido para el índice es
(0 <= index && index <= size())
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Métodos

Para la operación
List<T> subList(int fromIndex, int toIndex);
los valores válidos para los índices son
(0 <= fromIndex && fromIndex <= toIndex &&
toIndexindex <= size())


Devuelve una sublista con los elementos desde fromIndex
(incluido) hasta toIndex (excluido). Si fromIndex ==
toIndex, devuelve la lista vacía. Si toIndex es size(), la
sublista incluye al último elemento.
La lista devuelta está respaldada por la lista original (es
una vista de ella): los cambios que se realizan en la sublista
devuelta se reflejan en la lista original. Si se realizan
cambios estructurales (inserciones o borrados) en la lista
original, se eleva una excepción.
Nota: información detallada del contrato en
http://java.sun.com/javase/6/docs/api/ - java.util – interfaz List
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Ejemplos
Ejemplos
l=



l.size() == 5
l.contains(
) == true
l.contains(
) == false
Nota: si son objetos, los elementos 0, 1 y 4 serán referencias al mismo objeto.
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Ejemplos
l=

Operaciones que usan índice:




l.get(2) devuelve
l.indexOf(
) devuelve 3.
l.lastIndexOf(
) devuelve 4.
l.indexOf(
) devuelve -1.
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Ejemplos
l=

l.remove(3) modifica la lista, quedando:
y devolviendo
UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Ejemplos
Sobre la lista anterior
l.add(2,
)
modifica la lista, quedando:

0
1
2
3
UD 6: Tipos List y Set con tipos genéricos
4
Concepto de Lista. Ejemplos
Sobre la lista anterior
0
1
2
3
l.sublist(2, 4) devuelve la sublista
0
1
(llamémosla sl)
UD 6: Tipos List y Set con tipos genéricos
4
Concepto de Lista. Ejemplos
Si hacemos sl.add(1,
), es
sl =
0
1
2
y ahora l es
l=
0
1
2
3
UD 6: Tipos List y Set con tipos genéricos
4
5
Concepto de Lista. Implementaciones
Existen dos implementaciones de las listas:

ArrayList. La lista está almacenada en un array.

LinkedList. Cada elemento de la lista tiene una referencia a su anterior y a
su posterior.

Cada una tiene sus ventajas y sus inconvenientes.
Se verán con mucho más detalle en la asignatura EDDA

UD 6: Tipos List y Set con tipos genéricos
Concepto de Lista. Implementaciones

Para crear una lista vacía de un tipo T se usará
List<T> nombreLista = new LinkedList<T>();

o bien
List<T> nombreLista = new ArrayList<T>();

Por ejemplo, si tenemos un tipo Avion, para crear una lista de
aviones se escribirá:
List<Avion> listaAviones = new LinkedList<Avion>();
o

List<Avion> listaAviones = new ArrayList<Avion>();
Más adelante se creará una factoría de colecciones que
simplificará la creación de éstas.
UD 6: Tipos List y Set con tipos genéricos
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Concepto de Conjunto




Un conjunto es una colección en la que no se permiten
elementos repetidos.
Se corresponde con el concepto matemático de
conjunto.
En Java, se modela mediante la interfaz Set, que hereda de
Collection, por lo que tiene todos sus métodos.
No añade ningún método:
public interface Set<T> extends Collection<T> {
}
Nota: información detallada del contrato en
http://java.sun.com/javase/6/docs/api/ - java.util – interfaz Set
UD 6: Tipos List y Set con tipos genéricos
Concepto de Conjunto

Dados dos conjuntos (de Integer) a y b:
a = {1, 2, 3, 4}
b = {4, 5, 6}
recordemos que:





a = {1,2,3,4}
b= {4,5,6}
a  b = {1,2,3,4,5,6}
a – b = {1,2,3}
a  b = {4}
1
3
6
4
5
2
a
UD 6: Tipos List y Set con tipos genéricos
b
Concepto de Conjunto. Métodos

La correspondencia entre las operaciones de los
conjuntos en matemáticas y los métodos de la
interfaz Set es:






la unión: a.addAll(b) (devuelve boolean si cambia el
conjunto)
la diferencia: a.removeAll(b) (idem)
la intersección: a.retainAll(b) (idem)
ver si es vacío un conjunto: a.isEmpty( )
relación de inclusión: a.containsAll(b)
Los métodos addAll, removeAll, retainAll NO devuelven
un nuevo conjunto (devuelven un booleano), sino que
modifican el conjunto sobre el que se invocan.
UD 6: Tipos List y Set con tipos genéricos
Concepto de Conjunto. Implementaciones


Los conjuntos tienen fundamentalmente dos
implementaciones, HashSet y TreeSet, aunque se usará
principalmente la primera. Ambas se verán con detalle en la
asignatura EDDA.
Para crear un conjunto vacío de tipo T se usará:
Set<T> nombreConjunto = new HashSet<T>();
Por ejemplo, el siguiente código crea un conjunto de cadenas
llamado diccionario:
Set<String> diccionario = new HashSet<String>();

Como se ha dicho, más adelante se creará una factoría de
colecciones que simplificará la creación de éstas.
UD 6: Tipos List y Set con tipos genéricos
Índice


Estructuras de datos predefinidas en Java (Colecciones)
Interfaz Collection


Concepto de Lista



Métodos
Implementaciones
Concepto de Conjunto



Métodos
Métodos
Implementaciones
Clase Collections
UD 6: Tipos List y Set con tipos genéricos
Clase Collections

El paquete java.util contiene la clase Collections. Esta
clase está formada exclusivamente por métodos
estáticos que permiten operaciones sofisticadas sobre
las colecciones, como invertir una lista, barajarla,
ordenarla, buscar una sublista dentro de una lista,
encontrar el máximo o el mínimo de los elementos de
una colección, contar las veces en las que aparece un
elemento, etc.

Nota: información detallada en
http://java.sun.com/javase/6/docs/api/ - java.util – clase Collections
UD 6: Tipos List y Set con tipos genéricos
Clase Collections

Ejemplos:

Supongamos que tenemos una lista l de String que contiene
las cadenas "R", "T", "B", "A", "M“ en ese orden.

Si ejecutamos:
mostrar(l);
la salida es:
[R, T, B, A, M]
UD 6: Tipos List y Set con tipos genéricos
Clase Collections

Ejemplos:

Si sobre el valor actual de l ([R, T, B, A, M]) hacemos:
Collections.reverse(l);
mostrar(l);
se muestra por pantalla:
[M, A, B, T, R]
UD 6: Tipos List y Set con tipos genéricos
Clase Collections

Ejemplos:

Sobre el valor actual de l ([M, A, B, T, R]) ejecutamos:
Collections.sort(l);
mostrar(l);
la salida será:
[A, B, M, R, T]

Finalmente, si hacemos:
Collections.fill(l, "X");
mostrar(l);
se mostrará:
[X, X, X, X, X]
UD 6: Tipos List y Set con tipos genéricos