Introdução às Coleções em Java

Prévia do material em texto

Coleções
Prof. Marcelo Roberto Zorzan
Profa. Rachel Reis
Aula de Hoje
• Coleções
Introdução
• Coleções podem representar estruturas de dados
complexas de forma transparente para o
programador.
• Exemplos:
• Músicas favoritas armazenadas no computador
• Jogadores de um time
• Com as coleções os programadores utilizam
estruturas de dados existentes sem se preocupar
como elas são implementadas.
Visão Geral
Queue
• Collection: interface-raiz na hierarquia de coleções a partir da qual as 
interfaces Set e List são derivadas.
• Set : uma coleção que não contém duplicatas
• List : uma coleção ordenada que pode conter elementos duplicados
• Map: associa chaves a valores e não pode conter chaves duplicadas
• Queue: modela uma fila de espera.
Queue
Situação - Problema
� (Set ou List?)
1) Faça um programa em Java que contenha:
a) uma classe Pessoa com os atributos nome e idade.
b) uma classe Principal que imprima as informações das b) uma classe Principal que imprima as informações das 
pessoas cadastradas. 
Coleções
� Implementa uma estrutura de dados que armazena 
qualquer tipo de objeto.
� Não aceita tipos primitivos como elementos, apenas � Não aceita tipos primitivos como elementos, apenas 
instâncias de objetos. 
� Para guardar tipos primitivos devemos usar as 
classes wrapper. (Integer, Double, Float, etc)
� Declarado no pacote java.util
Classes Wrapper
� Permite a utilização de tipos primitivos como objetos.
Bytebyte
Booleanboolean
Doubledouble
Floatfloat
Longlong
Integerint
Shortshort
Characterchar
Bytebyte
Interface Collection 
Visão Geral
<<interface>> 
<<interface>> 
Collection
<<interface>> 
<<interface>> 
List
ArrayList VectorLinkedList
<<interface>> 
SortedSet
HashSet
<<interface>> 
Set
TreeSet
Interface List
� Uma List é uma Collection ordenada que pode conter 
elementos duplicados.
� Como os arrays, o índice do primeiro elemento de uma 
List é zero.
� A interface List é implementada por várias classes, 
incluindo as classes Vector, ArrayList e LinkedList.
<<interface>> 
Collection
Interface List
<<interface>> 
List
ArrayList VectorLinkedList
Interface List
Interface Classes Operações Nome do Método 
(Interface List)
Adição add(int index, Object elem)
List ArrayList
LinkedList
Adição add(int index, Object elem)
Remoção remove(int index)
Acesso get(int index)
listIterator()
Pesquisa indexOf(Object elem)
Tipos genéricos
• Tipos genéricos trazem a facilidade de parametrizar
o tipo de classes, variáveis ou métodos.
• Na API do JDK 5.0 todas as collection foram• Na API do JDK 5.0 todas as collection foram
parametrizadas.
// Java 1.4:
List lista = new ArrayList();
Tipos genéricos
lista.add(“Luis”);
String nome = (String) lista.get(0);
// Java 1.5 – usando generics:
List<String> lista = new ArrayList<String>();
lista.add(“Luis”);
String nome = lista.get(0);
Tipos genéricos
Outro exemplo
// Java 1.4:
List lista2 = new ArrayList();
lista2.add(new Pessoa(“José", 11));
JOptionPane.showMessageDialog(null, lista2.get(0)); JOptionPane.showMessageDialog(null, lista2.get(0)); 
[método getNome() não disponível!]
// Java 1.5 – usando generics:
List<Pessoa> lista2 = new ArrayList<Pessoa>();
lista2.add(new Pessoa(“José", 11));
JOptionPane.showMessageDialog(null, lista2.get(0).getNome());
ArrayList
� É um estrutura de dados que tem com base 
um array
� Principais características:
ArrayList
� Principais características:
� Acesso sequencial/aleatório extremamente rápido.
� Em função do índice o acesso a um elemento no meio da lista é 
uma operação extremamente rápida.
� Inserção é também extremamente rápida.
� Pode ser redimensionada dinamicamente.
� A classe ArrayList não é uma lista de arrays, apesar do 
nome é uma lista de objetos.
ArrayList - operações
� Criar um objeto ArrayList
�Instancie um objeto da classe ArrayList, usando o 
construtor com ou sem parâmetro
ArrayList<T> a = new ArrayList<T>();
ArrayList<T> b = new ArrayList<T>(20);
�O tamanho retornado por ambos objetos com o método 
size() vai ser zero, pois não adicionamos nenhum objeto 
nas listas
�Contudo, o valor 20 que foi informado significa a 
capacidade inicial da lista
• Adicionar elementos a um ArrayList
�O método add() pode ou não receber como parâmetro a 
posição na lista que desejamos que ele ocupe.
ArrayList - operações
posição na lista que desejamos que ele ocupe.
�Caso a posição que informarmos já possua um objeto, o 
mesmo será deslocado uma posição para frente e o nosso 
objeto será colocado na posição solicitada.
�A vantagem de não informar a posição é que a própria lista 
vai cuidar de gerenciar a posição do objeto
Pessoa p = new Pessoa(“joao”, 19);
ArrayList<Pessoa> a = new ArrayList<Pessoa>();
a.add(p);
ArrayList - operações
ou 
a.add(0, p); // Adicionou o objeto p na posição zero do ArrayList
• Remover elementos de um ArrayList
� Para remover um item da lista basta informar a posição da lista 
que desejamos remover
ArrayList - operações
a.remove(int i);
• Ler os dados do ArrayList
� Para ler dados da lista podemos usar o método get()
Pessoa p1 = a.get(int i);
Cuidado !!!
Ao usar o método add(...), get() ou remove() o elemento da 
lista deve existir, caso contrário irá gerar um exceção : 
ArrayList - operações
lista deve existir, caso contrário irá gerar um exceção : 
java.lang.IndexOutOfBoundsException
• Usando o Iterator para percorrer uma lista
� Um iterator serve para recuperar os elementos de uma coleção
ArrayList - operações
� Um iterator serve para recuperar os elementos de uma coleção
Iterator i = a.iterator();
while (i.hasNext()) 
{
Pessoa pessoa = (Pessoa) i.next();
JOptionPane.showMessageDialog(null,pessoa.getNome());
}
� Desta forma percorremos a lista, sem saber o tamanho da mesma. 
Atenção!!!
� Se uma coleção for modificada por um dos seus
métodos depois de um iterador ser criado para essa
ArrayList - operações
métodos depois de um iterador ser criado para essa
coleção, o iterador se torna imediatamente inválido.
�Qualquer operação realizada com o iterador depois
desse ponto pode lançar uma exceção
java.util.ConcurrentModificationException
LinkedList
� A classe LinkedList trabalha com o conceito
de lista encadeada.
LinkedList
� Além de implementar a interface List, a classe LinkedList provê
métodos uniformemente nomeados para get, remove e insert um
elemento no início e no final de uma lista. Essas operações
permitem que as listas encadeadas sejam utilizadas como pilha ou
fila
� Essa classe permite que sejam adicionados elementos no início ou
no final da lista.
LinkedList - operações
• Criar um objeto LinkedList:
LinkedList<String> lista = new 
LinkedList<String>();
• Adicionar um elemento (objeto) no final da lista:
lista.add(objeto);
lista.addLast(objeto);
•Adicionar um elemento (objeto) no início da lista:
lista.addFirst(objeto);
• Retornar o tamanho (número de elementos) da lista:
lista.size();
• Recuperar o elemento (objeto) na posição i:
objeto = lista.get(int i);
• Recuperar o primeiro elemento (objeto):
objeto = lista.getFirst();
• Recuperar o último elemento (objeto):
LinkedList - operações
• Recuperar o último elemento (objeto):
objeto = lista.getLast();
• Remover o elemento (objeto) da posição i:
lista.remove(int i);
• Remover o primeiro elemento (objeto):
lista.removeFirst();
• Remover o último elemento (objeto):
lista.removeLast();
Vector
• Como ArrayList, a classe Vector fornece as 
capacidades das estruturas de dados no estilo array 
que podem se redimensionar dinamicamente.
Vector
que podem se redimensionar dinamicamente.
• A diferença entre eles (ArrayList e Vector) é que a 
classe Vector garante sincronização de dados.
LinkedList x ArrayList
• As diferenças são basicamente relativas a inserção,
remoção e iteração.
• A LinkedList é a mais rápida para inserção e iteração. Se• A LinkedList é a mais rápida para inserção e iteração. Se
a lista for apenas para inserir e exibir os elementos (sem
remover ou alterar) LinkedListé melhor.
• ArrayList é melhor se você precisa de acesso com índice
(chamado acesso aleatório) ou seja , quando você usa o
lista.get(i)
Interface Set
• Um set é uma Collection que não contém elementos 
duplicados.
<<interface>> TreeSet:
<<interface>> 
SortedSet
HashSet
Set
TreeSet
� Modela conjuntos ordenados.
� Armazena seus elementos em uma
árvore.
HashSet:
�Modela conjuntos não ordenados.
�Armazena seus elementos em uma
tabela Hash.
• A interface Set é uma extensão de Collection que não
acrescenta nenhum método à especificação básica.
Interface Set
Collection
containsAll(Object)
addAll(Object)
retainAll(Object)
remove(Object)
• Operações
- Subconjunto (containsAll)
- União (addAll)
- Interseção (retainAll)
- Diferença (removeAll)
Interface SortedSet
• A interface SortedSet é uma extensão de Set que agrega
o conceito de ordenação ao conjunto.
• Operações adicionais são fornecidas para tirar proveito
dessa ordenação:
- comparator()
- first()
- headSet (Object toElement) 
- last() 
- subSet (Object fromElement, Object toElement)
- tailSet(Object fromElement)
HashSet x TreeSet
• Essa estrutura de coleções contém diversas implementações 
de Set, incluindo as classes HashSet ou TreeSet.
• Ao contrário de arrays não é necessário especificar a posição 
para adicionar um elemento, basta fazer:para adicionar um elemento, basta fazer:
c.add(objeto)
• Outros métodos são:
- add - adiciona um elemento ou um conjunto de elementos. 
- remove - remove um elemento ou um conjunto de elementos.
- contains - Retorna true se o conjunto possuir algum elemento. 
- isEmpty - Retorna true se o conjunto estiver vazio. 
• Os elementos de um Set não tem uma ordem como em um 
array, em que o primeiro elemento está na posição 0
HashSet x TreeSet
• A classe HashSet não possui ordem específica
• Já a classe TreeSet cria uma ordem, no caso de• Já a classe TreeSet cria uma ordem, no caso de
números do menor para o maior e no caso de String a
ordem é lexicográfica.
Exemplo 1 HashSet
import java.util.*;
public class ExemploHashSet {
public static void main(String[] args) {
Collection <String> c = new HashSet <String>();Collection <String> c = new HashSet <String>();
c.add("Maria");
c.add("Joao");
c.add("Ana");
c.add("Joao");
c.add("Jose");
System.out.println(c);
}
}
Qual o resultado?
• Resultado: [Joao, Jose, Maria, Ana]
• No exemplo anterior temos um nome que é
Exemplo 1 HashSet
• No exemplo anterior temos um nome que é
adicionado duas vezes, mas como a interface Set não
permite repetição quando manipulamos Strings, ele na
verdade só é inserido uma vez.
• Observe que não há uma ordem na impressão dos
resultados.
import java.util.*;
public class ExemploHashSet2 {
public static void main(String[] args) {
Collection <String> c = new HashSet <String>();
c.add("Maria");
Exemplo 2 HashSet
c.add("Maria");
c.add("Joao");
c.add("Ana");
c.add("Joao");
c.add("Jose");
Iterator i = c.iterator();
while( i.hasNext() ) {
System.out.print( i.next() + " " );
}
}
}
Resultado: 
Joao Jose Maria Ana
Exemplo 1 TreeSet
import java.util.*;
public class ExemploTreeSet {
public static void main(String[] args) {
Collection<String> c = new TreeSet<String>();
c.add("Maria");c.add("Maria");
c.add("Joao");
c.add("Ana");
c.add("Joao");
c.add("Jose");
Iterator i = c.iterator();
while( i.hasNext() ) {
System.out.print( i.next() + " " );
}
}
} Qual o resultado?
• Resultado é : Ana Joao Jose Maria
• Observe que não é permitido repetições, como em um
HashSet, e que neste caso os elementos já estão
Exemplo 1 TreeSet
HashSet, e que neste caso os elementos já estão
ordenados.
Exemplo 2 TreeSet
import java.util.*;
public class ExemploTreeSet2 {
public static void escreve(Collection d) {
Iterator i = d.iterator();
while( i.hasNext() ) {
System.out.print( i.next() + " " );
}
}
...
public static void main(String[] args) {
Collection <String> c = new TreeSet <String>();
Collection <String> c2 = new TreeSet <String>();
Exemplo 2 TreeSet
c.add("Maria");
c.add("Joao");
c.add("Ana");
c.add("Joao");
c.add("Jose");
c.add("Andre");
System.out.println(“Elementos de c ");
escreve( c );
...
Iterator j = c.iterator();
while( j.hasNext() ) {
Object o = j.next();
if( o.equals("Jose") ) {
Exemplo 2 TreeSet
if( o.equals("Jose") ) {
j.remove();
}
}
System.out.println(“Elementos de c menos Jose ");
escreve( c );
c.remove("Andre");
System.out.println(“Elementos de c menos Andre ");
escreve( c );
...
...
c2.add("Claudia");
c2.add("Paulo");
c2.add("Ana");
System.out.println(“Elementos de c2 ");
Exemplo 2 TreeSet
System.out.println(“Elementos de c2 ");
escreve( c2 );
c.addAll(c2);
System.out.println(“Elementos de c união c2 ");
escreve( c );
c.removeAll(c2);
System.out.println(“Elementos de c menos c2 ");
escreve( c );
}
}
Resultado – Exemplo 2 
>Elementos de c
>Ana Andre Joao Jose Maria
>Elementos de c menos Jose
>Ana Andre Joao Maria>Ana Andre Joao Maria
>Elementos de c menos Andre
>Ana Joao Maria
>Elementos de c2 
>Ana Claudia Paulo
>Elementos de c união c2 
>Ana Claudia Joao Maria Paulo
>Elementos de c menos c2 
>Joao Maria
Exemplo 3 TreeSet
• Agora vamos ver um exemplo usando um TreeSet com
elementos do conjunto que possuem mais de um campo.
• Nestes exemplos os elementos são funcionários de uma• Nestes exemplos os elementos são funcionários de uma
empresa que tem nome e salário. Para definir o campo para
o qual queremos ordenação usamos a interface Comparable .
Exemplo 3 TreeSet
public class Empregado implements Comparable<Empregado>{
private String nome;
private int salario;
Empregado(String nome, int salario) {
this.setNome(nome);
this.setSalario(salario);
}
// métodos set´s// métodos set´s
public String getNome(){
return this.nome;
}
public int getSalario(){
return this.salario;
}
public int compareTo (Empregado o) {
return this.salario - o.getSalario();
}
}
import java.util.*;
public class CriaEmpregado {
public static void main(String[] args) {
Empregado emp1 = new Empregado("Joao", 100);
Empregado emp2 = new Empregado("Maria", 120);
Empregado emp3 = new Empregado("Jose", 130);
Empregado emp4 = new Empregado("Ana", 110);
Empregado emp5 = new Empregado("Jimy", 130);
Collection <Empregado> c = new TreeSet <Empregado>();
Exemplo 3 TreeSet
Collection <Empregado> c = new TreeSet <Empregado>();
c.add(emp1);
c.add(emp2);
c.add(emp3);
c.add(emp4);
c.add(emp5);
Iterator i = c.iterator();
while ( i.hasNext() ) {
Empregado e = (Empregado) i.next();
System.out.println(e.getNome() + " " + e.getSalario());
}
}
}
>Joao 100
>Ana 110
>Maria 120
>Jose 130
Resultado – Exemplo 3 
>Jose 130
Algoritmos de coleções
� Página 686, seção 19.6 (Livro Deitel)
• Algoritmo sort
• Algoritmo shuffle
• Algoritmos reverse, fill, copy, max e min
• Algoritmo binarySearch