aula Estrutura de Dados 05

Prévia do material em texto

Tecnologia em Sistemas para Internet - IFMS
Aula 05 – Listas (parte 2)
Estruturas de Dados
Prof.º Msc. Sidney Roberto de Sousa
sidney.sousa@ifms.edu.br
Tec. em Sistemas para Internet - IFMS 2
O que veremos nesta aula?
● Criando uma lista encadeada genérica
● A interface List do pacote java.util
● Formas de instanciação da interface List
Tec. em Sistemas para Internet - IFMS 3
Recapitulando...
● Na aula anterior, vimos uma classe que 
encapsula uma lista encadeada de valores 
inteiros
● Ou seja, uma instância daquela classe pode 
armazenar um conjunto teoricamente infinito 
de valores inteiros
Tec. em Sistemas para Internet - IFMS 4
Problema
● Digamos que desejamos criar uma lista 
encadeada para armazenar strings
● O que devemos fazer? talvez possamos →
re-escrever a classe ListaEncadeada de tal 
forma que ela possa armazenar strings ao 
invés de valores inteiros
● Problema resolvido!
Tec. em Sistemas para Internet - IFMS 5
Problema
● Digamos que desejamos criar uma lista 
encadeada para armazenar strings
● O que devemos fazer? → talvez possamos 
re-escrever a classe ListaEncadeada de tal 
forma que ela possa armazenar strings ao 
invés de valores inteiros
● Problema resolvido!
?
Tec. em Sistemas para Internet - IFMS 6
Problema
● Agora, digamos que estamos implementando 
um sistema complexo, no qual precisaremos 
utilizar listas de tipos variados →
possivelmente até tipos complexos
● Ex.: lista de usuários, lista de clientes, lista de 
pedidos, etc.
● Solução: escrever uma cópia da classe 
ListaEncadeada para cada tipo desejado!
Tec. em Sistemas para Internet - IFMS 7
Vamos realmente fazer isto?
Tec. em Sistemas para Internet - IFMS 8
Como resolver este problema?
● Realmente, criar uma classe para cada tipo de 
dados pode ser extremamente inviável!
● A questão é: como escrever o código da classe 
ListaEncadeada somente uma vez, porém 
permitindo que o tipo do item a ser 
armazenado possa ser definido apenas no 
momento em que a lista for criada?
● Ou seja, precisamos escrever uma classe 
genérica!
Tec. em Sistemas para Internet - IFMS 9
Generics
● Generics ou programação genérica em Java é 
uma forma de determinar ao compilador qual 
o tipo que deve ser interpretado em um 
determinado trecho do programa
● Isto facilita muito o reúso de software no →
nosso caso, escrever a classe ListaEncadeada 
somente uma vez!
Tec. em Sistemas para Internet - IFMS 10
Classes NoGenerico e ListaEncadeadaGenerica
(abaixo no blog)
Tec. em Sistemas para Internet - IFMS 11
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Tec. em Sistemas para Internet - IFMS 12
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
A classe NoGenerico 
implementa um nó de uma lista 
genérica. Assim, cada instância 
da classe NoGenerico pode 
armazenar um valor do tipo 
desejado.
Tec. em Sistemas para Internet - IFMS 13
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
A letra T identifica um tipo genérico. Assim, a 
classe NoGenerico pode utilizar o tipo genérico 
T em seus atributos e métodos para especificar 
o uso de um tipo que será definido 
posteriormente pelo trecho de código que 
utilizá-la. Você pode batizar o seu tipo genérico 
conforme o seu gosto. Por convenção, tipos 
genéricos são batizados com apenas uma letra 
maiúscula.
Tec. em Sistemas para Internet - IFMS 14
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Uma classe pode ter tantos tipos genéricos 
forem necessários à sua implementação. 
Obrigatoriamente, o trecho de código que 
utilizar a classe que contém os tipos genéricos 
deve definir qual será o tipo utilizado para cada 
tipo genérico.
Tec. em Sistemas para Internet - IFMS 15
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
O valor do item a ser 
armazenado é definido com o 
tipo genérico.
Tec. em Sistemas para Internet - IFMS 16
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
O próximo item após o item atual. Note que no 
instante da declaração do objeto é necessário 
definir qual será o tipo a ser utilizado. Como ainda 
não sabemos qual o tipo definitivo a ser utilizado, 
associamos o tipo T ao tipo do valor do próximo 
item.
Tec. em Sistemas para Internet - IFMS 17
A classe NoGenerico
public class NoGenerico<T> {
    private T item;
    private NoGenerico<T> proximoItem;
    public NoGenerico() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
O tipo genérico não precisa ser 
especificado no construtor da 
classe.
Tec. em Sistemas para Internet - IFMS 18
A classe ListaEncadeadaGenerica
● Os métodos e atributos da classe 
ListaEncadeadaGenerica são parecidos com 
os da classe ListaEncadeada
● Porém, o tipo genérico é utilizado sempre que 
o tipo dos ítens armazenados precisa ser 
referenciado
Tec. em Sistemas para Internet - IFMS 19
A classe ListaEncadeadaGenerica
public class ListaEncadeadaGenerica<T> {
    private int tamanho;
    private NoGenerico<T> primeiroItem;
    private NoGenerico<T> ultimoItem;
    public ListaEncadeadaGenerica() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Tec. em Sistemas para Internet - IFMS 20
A classe ListaEncadeadaGenerica
public class ListaEncadeadaGenerica<T> {
    private int tamanho;
    private NoGenerico<T> primeiroItem;
    private NoGenerico<T> ultimoItem;
    public ListaEncadeadaGenerica() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
A classe ListaEncadeadaGenerica utiliza 
o tipo genérico T para definir qual o tipo do 
valor a ser armazenado em cada item. O 
tipo genérico é propagado a cada item da 
lista no momento de sua instanciação.
Tec. em Sistemas para Internet - IFMS 21
A classe ListaEncadeadaGenerica
public class ListaEncadeadaGenerica<T> {
    private int tamanho;
    private NoGenerico<T> primeiroItem;
    private NoGenerico<T> ultimoItem;
    public ListaEncadeadaGenerica() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
O primeiro e último ítens da lista são criados com 
o tipo genérico. Assim, quando a lista for criada, 
estes ítens estarão preparados para armazenar 
os valores desejados de forma apropriada.
Tec. em Sistemas para Internet - IFMS 22
Utilizando o tipo genérico nas operações da lista
public void adicionarNoInicio(T novoItem) {
    if (tamanho== 0) {
        primeiroItem = new NoGenerico<T>();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        NoGenerico<T> antigoPrimeiroItem = primeiroItem;
        primeiroItem = new NoGenerico<T>();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Tec. em Sistemas para Internet - IFMS 23
Utilizando o tipo genérico nas operações da lista
public void adicionarNoInicio(T novoItem) {
    if (tamanho == 0) {
        primeiroItem = new NoGenerico<T>();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        NoGenerico<T> antigoPrimeiroItem = primeiroItem;
        primeiroItem = new NoGenerico<T>();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Tec. em Sistemas para Internet - IFMS 24
Utilizando a lista encadeada genérica
ListaEncadeadaGenerica<String> listaEncadeada = new ListaEncadeadaGenerica<String>();
listaEncadeada.adicionarNoInicio("ao");
listaEncadeada.adicionarNoInicio("foi");
listaEncadeada.adicionarNoInicio("João");
listaEncadeada.adicionarNoFinal("bar");
listaEncadeada.adicionarNaPosicao("Paulo", 2);
NoGenerico<String> item = listaEncadeada.pegarItem(1);
// Imprime na tela:
// João Paulo foi ao bar
while (item != null) {
    System.out.print(item.getItem() + " ");
    item = item.getProximoItem();
}
Tec. em Sistemas para Internet - IFMS 25
Utilizando a lista encadeada genérica
ListaEncadeadaGenerica<Double> listaEncadeada = new ListaEncadeadaGenerica<Double>();
listaEncadeada.adicionarNoInicio(2.54);
listaEncadeada.adicionarNoInicio(­123.234);
listaEncadeada.adicionarNoInicio(0.1735);
listaEncadeada.adicionarNoFinal(76D);
listaEncadeada.adicionarNaPosicao(­981.39, 2);
NoGenerico<Double> item = listaEncadeada.pegarItem(1);
// Imprime na tela:
// 0.1735 ­981.39 ­123.234 2.54 76.0
while (item != null) {
    System.out.print(item.getItem() + " ");
    item = item.getProximoItem();
}
Tec. em Sistemas para Internet - IFMS 26
Classe Cliente
public class Cliente {
    private String cpf;
    private Date dataAniversario;
    private String nomeCompleto;
    private String endereco;
    // Getters e setters para os atributos...    
}
Tec. em Sistemas para Internet - IFMS 27
Criando uma lista de clientes
Cliente cliente1 = new Cliente();
cliente1.setNomeCompleto("Ana Leite");
Cliente cliente2 = new Cliente();
cliente2.setNomeCompleto("Augusto Macedo");
Cliente cliente3 = new Cliente();
cliente3.setNomeCompleto("Maria dos Anjos Toledo");
ListaEncadeadaGenerica<Cliente> listaEncadeada = new ListaEncadeadaGenerica<Cliente>();
listaEncadeada.adicionarNoFinal(cliente1);
listaEncadeada.adicionarNoInicio(cliente2);
listaEncadeada.adicionarNaPosicao(cliente3, 2);
NoGenerico<Cliente> item = listaEncadeada.pegarItem(1);
while (item != null) {
    System.out.println(item.getItem().getNomeCompleto());
    item = item.getProximoItem();
}
Tec. em Sistemas para Internet - IFMS 28
A interface List do pacote java.util
● A interface List possui a definição de várias operações 
sobre listas
● É a alternativa mais adotada pelos programadores Java 
para a utilização de listas
● Por ser uma interface, ela não contém a implementação 
dos seus métodos; apenas a assinatura destes.
● Assim, existem duas implementações na JDK para o uso 
da interface List:
● A classe ArrayList
● A classe LinkedList
Tec. em Sistemas para Internet - IFMS 29
Instanciando uma lista do tipo List
List<Integer> lista1 = new ArrayList<Integer>();
List<Integer> lista2 = new LinkedList<Integer>();
Tec. em Sistemas para Internet - IFMS 30
A classe ArrayList
● A mais prática na maioria dos casos
● Por baixo dos panos, ela: 
● Oferece de fato acesso direto a um item da lista
● Não precisa alocar um novo nó para inserir um item novo
● Na prática, a classe ArrayList implementa uma lista estática, de 
tamanho inicial 10
● Quando existe a necessidade de se inserir o décimo primeiro 
item, a lista se redimensiona de forma implícita
● No geral, tem melhor desempenho que a classe LinkedList
Tec. em Sistemas para Internet - IFMS 31
A classe ArrayList 
(vantagens e desvantagens)
● A mais prática na maioria dos casos
● Por baixo dos panos, ela: 
● Oferece de fato acesso direto a um item da lista
● Não precisa alocar um novo nó para inserir um item novo
● Na prática, a classe ArrayList implementa uma lista estática, 
de tamanho inicial 10
● Quando existe a necessidade de se inserir o décimo primeiro 
item, a lista se redimensiona de forma implícita
● No geral, tem melhor desempenho que a classe LinkedList
Tec. em Sistemas para Internet - IFMS 32
A classe LinkedList
● Implementa uma lista encadeada
● O acesso ao primeiro e último ítens é feito de forma mais 
rápida do que o oferecido pela classe ArrayList
● Por ser uma lista encadeada, o acesso aos ítens 
intermediários não é feito de forma direta
● Não costuma ser mais prática que ArrayList na maioria 
dos casos
● Possui um melhor desempenho quando a inserção, 
leitura e remoção dos ítens da lista costumam ocorrer 
nas pontas da lista
Tec. em Sistemas para Internet - IFMS 33
A classe LinkedList 
(vantagens e desvantagens)
● Implementa uma lista encadeada
● O acesso ao primeiro e último ítens é feito de forma 
mais rápida do que o oferecido pela classe ArrayList
● Por ser uma lista encadeada, o acesso aos ítens 
intermediários não é feito de forma direta
● Não costuma ser mais prática que ArrayList na 
maioria dos casos
● Possui um melhor desempenho quando a inserção, 
leitura e remoção dos ítens da lista costumam ocorrer 
nas pontas da lista
Tec. em Sistemas para Internet - IFMS 34
Utilizando a interface List
● Como as classes ArrayList e LinkedList 
implementam a classe List, elas 
obrigatoriamente possuem a mesma assinatura 
de métodos
● Assim, independente da implementação 
escolhida, o uso da interface List é feito da 
mesma forma
● A real diferença entre as implementações só é 
percebida em termos de desempenho
Tec. em Sistemas para Internet - IFMS 35
Utilizando a interface List
Classe ExemploList
(abaixo no blog)
Tec. em Sistemas para Internet - IFMS 36
Adicionando ítens
// Inserindo ítens no final da lista
lista.add(12);
lista.add(­38);
lista.add(827);
// Inserindo ítens no início da lista
lista.add(0, 125);
lista.add(0, ­387);
lista.add(0, 82735);
Tec. em Sistemas para Internet - IFMS 37
Concatenando duas listas
List<Integer> listaExtra = new ArrayList<Integer>();
listaExtra.add(11);
listaExtra.add(22);
listaExtra.add(33);
// Adiciona todos os ítens da lista extra no final da 
// primeira lista
lista.addAll(listaExtra);
Tec. em Sistemas para Internet - IFMS 38
Inserindo uma lista no meio da outra
listaExtra.add(44);
listaExtra.add(55);
listaExtra.add(66);
/**
 * Adiciona todos os ítens da lista extra na posição  
 * desejada da primeira lista
 */
lista.addAll(3, listaExtra);
Tec. em Sistemas para Internet - IFMS 39
Removendo ítens por índice
/**
 * Removendo ítens da lista pelo índice. Na interface 
 * List, os elementos são indexados na forma 
 * [0..tamanho da lista ­ 1]
 */
lista.remove(0);
lista.remove(4);
Tec. em Sistemas para Internet - IFMS 40
Removendo ítens por ocorrência
/**
 * Removendo um item da lista caso ele exista. O cast 
 * para Object é necessário para que o compilador 
 * diferencie a chamada ao método de remoção por 
 * ocorrência do método de remoçãopor índice. Retorna 
 * true caso o item exista; false c.c.
 */
lista.remove((Object) 77); // Retorna false
Tec. em Sistemas para Internet - IFMS 41
Verificando a ocorrência de um item
// Verifica se um item está contido na lista
if (lista.contains(12)) {
    System.out.println("A lista contém o item 12.");
}
Tec. em Sistemas para Internet - IFMS 42
Pegando o índice de um ítem
// Imprime o índice da primeira ocorrência do item de 
// valor 125
System.out.println(lista.indexOf((Object) 125));
Tec. em Sistemas para Internet - IFMS 43
Verificando a ocorrência de uma sublista
// Verifica se a lista contém uma sublista
if (lista.containsAll(listaExtra)) {
    System.out.println("A primeira lista contém a lista extra!");
}
Tec. em Sistemas para Internet - IFMS 44
Substituindo um item
// Substituindo o elemento da terceira posição da lista
lista.set(3, 42);
Tec. em Sistemas para Internet - IFMS 45
Verificando se a lista está vazia
// Verifica se a lista está vazia
if (lista.isEmpty()) {
    System.out.println("A lista está vazia.");
} else {
    System.out.println("A lista contém " + lista.size() + " elemento(s).");
}
Tec. em Sistemas para Internet - IFMS 46
Verificando a última ocorrência de um valor na lista
System.out.println("A última ocorrência de 55 se dá na posição "
                   + lista.lastIndexOf(55));
Tec. em Sistemas para Internet - IFMS 47
Pegando o tamanho da lista
System.out.println("Tamanho atual da lista: " + lista.size());
Tec. em Sistemas para Internet - IFMS 48
Pegando partes da lista
/**
 * Pega uma parte da lista. O primeiro índice é inclusivo; o 
 * segundo é exclusivo.
 */
List<Integer> outraLista = lista.subList(2, 4);
Tec. em Sistemas para Internet - IFMS 49
Convertendo uma lista para vetor
// Converte a lista de inteiros em um vetor de objetos
Object[] vetor = lista.toArray();
// Converte a lista de inteiros em um vetor de inteiros
Integer[] vetorInteiros = new Integer[lista.size()];
lista.toArray(vetorInteiros);
Tec. em Sistemas para Internet - IFMS 50
Percorrendo uma lista
for (int i = 0; i < lista.size(); i++) {
    System.out.print(lista.get(i) + " ");
}
Tec. em Sistemas para Internet - IFMS 51
Percorrendo uma lista com o laço for each
for (Integer item : lista) {
    System.out.print(item + " ");
}
Tec. em Sistemas para Internet - IFMS 52
That's not all, folks!
Na próxima (e última) aula sobre listas, vamos 
empileirar e enfileirar algumas coisas...
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52