Listas Encadeadas
Fabrı́cio J. Barth
BandTec - Faculdade de Tecnologia Bandeirantes
Fevereiro de 2011
Disciplina de Estrutura de Dados e Armazenamento
Tópicos Principais
• Motivação
• Listas encadeadas
• Implementações recursivas
• Listas de tipos estruturados
Listas Encadeadas —
Tópicos Principais
Faculdade de Tecnologia Bandeirantes 2
Disciplina de Estrutura de Dados e Armazenamento
Tópicos complementares
• Listas circulares
• Listas duplamente encadeadas
Listas Encadeadas —
Tópicos complementares
Faculdade de Tecnologia Bandeirantes 3
Tópicos Principais
4
Disciplina de Estrutura de Dados e Armazenamento
Motivação
• Vetor:
? ocupa um espaço contı́guo de memória
? permite acesso randômico aos elementos
? deve ser dimensionado com um número máximo de
elementos
Tópicos Principais —
Motivação
Faculdade de Tecnologia Bandeirantes 5
Disciplina de Estrutura de Dados e Armazenamento
Motivação
• Estruturas de dados dinâmicas: crescem ou decrescem
à medida que elementos são inseridos ou removidos.
• Exemplo: listas encadeadas.
• Listas encadeadas são amplamentes utilizadas para
implementar outras estruturas de dados.
Tópicos Principais —
Motivação
Faculdade de Tecnologia Bandeirantes 6
Disciplina de Estrutura de Dados e Armazenamento
Listas Encadeadas
• sequência encadeada de elementos, chamados nós da
lista.
• nó da lista é representado por dois campos:
? a informação armazenada e
? o ponteiro para o próximo elemento da lista
Tópicos Principais —
Listas Encadeadas
Faculdade de Tecnologia Bandeirantes 7
Disciplina de Estrutura de Dados e Armazenamento
• a lista é representada por um ponteiro para o primeiro
nó
• o ponteiro do último elemento é NULL.
Tópicos Principais —
Listas Encadeadas
Faculdade de Tecnologia Bandeirantes 8
Disciplina de Estrutura de Dados e Armazenamento
Estrutura com ponteiro para ela mesma
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Nodo {
private int info;
private Nodo prox;
public int getInfo() {
return info;
}
public void setInfo(int info) {
this.info = info;
}
public Nodo getProx() {
return prox;
}
public void setProx(Nodo prox) {
this.prox = prox;
}
}
Tópicos Principais —
Estrutura com ponteiro para ela mesma
Faculdade de Tecnologia Bandeirantes 9
Disciplina de Estrutura de Dados e Armazenamento
Criação da lista vazia
1
2
3
4
5
6
public class Lista {
private Nodo prim;
public void criaLista(){
prim = null;
}
}
Tópicos Principais —
Criação da lista vazia
Faculdade de Tecnologia Bandeirantes 10
Disciplina de Estrutura de Dados e Armazenamento
Listas encadeadas de inteiros: inserção
• Aloca memória para armazenar o elemento
• Encadeia o elemento na lista existente
Tópicos Principais —
Listas encadeadas de inteiros: inserção
Faculdade de Tecnologia Bandeirantes 11
Disciplina de Estrutura de Dados e Armazenamento
Listas encadeadas de inteiros: inserção
1
2
3
4
5
6
7
8
9
/*
* insercao no inicio
*/
public void add(int i){
Nodo novo = new Nodo();
novo.setInfo(i);
novo.setProx(prim);
prim = novo;
}
Tópicos Principais —
Listas encadeadas de inteiros: inserção
Faculdade de Tecnologia Bandeirantes 12
Disciplina de Estrutura de Dados e Armazenamento
Exemplo de utilização
1
2
3
4
5
6
7
public Main(){
Lista lista = new Lista();
lista.criaLista();
lista.add(45);
lista.add(60);
lista.add(1);
}
Tópicos Principais —
Exemplo de utilização
Faculdade de Tecnologia Bandeirantes 13
Disciplina de Estrutura de Dados e Armazenamento
Função que percorre os elementos da lista
1
2
3
4
5
public void print(){
for(Nodo n = prim; n != null; n = n.getProx()){
System.out.println(n.getInfo());
}
}
Tópicos Principais —
Função que percorre os elementos da lista
Faculdade de Tecnologia Bandeirantes 14
Disciplina de Estrutura de Dados e Armazenamento
Exemplo de utilização
1
2
3
4
5
6
7
8
9
10
11
public Main(){
Lista lista = new Lista();
lista.criaLista();
System.out.println("Imprimindo valores");
lista.print();
lista.add(45);
lista.add(60);
lista.add(1);
System.out.println("Imprimindo valores");
lista.print();
}
Tópicos Principais —
Exemplo de utilização
Faculdade de Tecnologia Bandeirantes 15
Disciplina de Estrutura de Dados e Armazenamento
Função que verifica se a lista está vazia
1
2
3
4
5
6
public boolean
if(prim ==
return
else
return
}
Tópicos Principais —
isEmpty(){
null)
true;
false;
Função que verifica se a lista está vazia
Faculdade de Tecnologia Bandeirantes 16
Disciplina de Estrutura de Dados e Armazenamento
Função de busca
• Recebe a informação referente ao elemento a pesquisar
• Retornar o objeto da lista que representa o elemento
ou null, caso o elemento não seja encontrado na lista.
Tópicos Principais —
Função de busca
Faculdade de Tecnologia Bandeirantes 17
Disciplina de Estrutura de Dados e Armazenamento
1
2
3
4
5
6
7
8
9
10
11
/*
* busca por um elemento na lista
*/
public Nodo search(int i){
for(Nodo n = prim; n != null; n = n.getProx()){
if(n.getInfo()==i){
return n;
}
}
return null; /* nao achou o elemento*/
}
Tópicos Principais —
Função de busca
Faculdade de Tecnologia Bandeirantes 18
Disciplina de Estrutura de Dados e Armazenamento
Exemplo de utilização da função de busca
1
2
3
4
5
Nodo temp;
if((temp = lista.search(60)) != null)
System.out.println("Achou "+temp.getInfo());
else
System.out.println("Nao achou o elemento");
Tópicos Principais —
Exemplo de utilização da função de busca
Faculdade de Tecnologia Bandeirantes 19
Disciplina de Estrutura de Dados e Armazenamento
Função que retira um elemento da lista
• Recebe como entrada o valor do elemento a retirar.
• Atualiza o valor do ponteiro para a lista (prim) se o
elemento removido for o primeiro.
Tópicos Principais —
Função que retira um elemento da lista
Faculdade de Tecnologia Bandeirantes 20
Disciplina de Estrutura de Dados e Armazenamento
• caso contrário, remove apenas o elemento da lista.
Tópicos Principais —
Função que retira um elemento da lista
Faculdade de Tecnologia Bandeirantes 21
Disciplina de Estrutura de Dados e Armazenamento
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void remove(int i){
/*objeto para o elemento anterior*/
Nodo anterior = null;
/*objeto para percorrer a lista*/
Nodo p = prim;
/*procura elemento na lista, guardando anterior*/
while(p != null && p.getInfo() != i){
anterior = p;
p = p.getProx();
}
/*verifica se achou elemento*/
if(p == null){
/*nao achou: mantem prim da forma como estah*/
return;
}
/*retira elemento*/
if(anterior == null){
/*retira elemento do inicio*/
prim = p.getProx();
}else{
/*retira elemento do meio da lista*/
anterior.setProx(p.getProx());
}
}
Tópicos Principais —
Função que retira um elemento da lista
Faculdade de Tecnologia Bandeirantes 22
Disciplina de Estrutura de Dados e Armazenamento
Função para liberar a lista
1
2
3
4
5
6
7
public void free(){
while (prim != null){
Nodo temp = prim.getProx();
prim = null;
prim = temp;
}
}
• Em Java, quando um objeto não é mais utilizado, a
JVM é responsável por desalocar a memória que não é
mais utilizada.
• No entanto, em outras linguagens de programação o
programador deve explicitamente liberar a memória
consumida pela variável desnecessária.
Tópicos Principais —
Função para liberar a lista
Faculdade de Tecnologia Bandeirantes 23
Disciplina de Estrutura de Dados e Armazenamento
Manutenção da lista ordenada
Função de inserção percorre os elementos da lista até
encontrar a posição correta para a inserção do novo.
Tópicos Principais —
Manutenção da lista ordenada
Faculdade de Tecnologia Bandeirantes 24
Disciplina de Estrutura de Dados e Armazenamento
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void addOrdenado(int i){
Nodo novo;
/*objeto para o elemento anterior*/
Nodo anterior = null;
/*objeto para percorrer a lista*/
Nodo p = prim;
/*procura elemento na lista, guardando anterior*/
while(p != null && p.getInfo() < i){
anterior = p;
p = p.getProx();
}
/*cria novo elemento*/
novo = new Nodo();
novo.setInfo(i);
/*encadeia o elemento*/
if(anterior == null){ /*inseri o elemento no inicio*/
novo.setProx(prim);
prim = novo;
}else{ /*inseri elemento no meio da lista*/
novo.setProx(anterior.getProx());
anterior.setProx(novo);
}
}
Tópicos Principais —
Manutenção da lista ordenada
Faculdade de Tecnologia Bandeirantes 25
Disciplina de Estrutura de Dados e Armazenamento
Definição recursiva de lista
Uma lista é:
• uma lista vazia, ou;
• um elemento seguido de uma (sub-)lista.
Tópicos Principais —
Definição recursiva de lista
Faculdade de Tecnologia Bandeirantes 26
Disciplina de Estrutura de Dados e Armazenamento
Exemplo: função recursiva para imprimir
uma lista
• se a lista for vazia, não imprima nada
• caso contrário,
? imprima a informação associada ao primeiro nó,
dada por prim.getInf o()
? imprima a sub-lista, dada por prim.getP rox(),
chamando recursivamente a função.
Tópicos Principais —
Exemplo: função recursiva para imprimir uma lista
Faculdade de Tecnologia Bandeirantes 27
Disciplina de Estrutura de Dados e Armazenamento
Função imprime recursiva
1
2
3
4
5
6
7
8
public void printRecursivo(Nodo n){
if(!isEmpty(n)){
/*imprime o primeiro elemento*/
System.out.println(n.getInfo());
/*imprime a sub-lista*/
printRecursivo(n.getProx());
}
}
Tópicos Principais —
Função imprime recursiva
Faculdade de Tecnologia Bandeirantes 28
Disciplina de Estrutura de Dados e Armazenamento
Função imprime recursiva invertida
1
2
3
4
5
6
7
8
public void printRecursivoInvertido(Nodo n){
if(!isEmpty(n)){
/*imprime a sub-lista*/
printRecursivoInvertido(n.getProx());
/*imprime o elemento*/
System.out.println(n.getInfo());
}
}
Tópicos Principais —
Função imprime recursiva invertida
Faculdade de Tecnologia Bandeirantes 29
Disciplina de Estrutura de Dados e Armazenamento
Exemplo: função para retirar um
elemento da lista
• retire o elemento, se ele for o primeiro da lista (ou da
sub-lista)
• caso contrário, chame a função recursivamente para
retirar o elemento da sub-lista
Tópicos Principais —
Exemplo: função para retirar um elemento da lista
Faculdade de Tecnologia Bandeirantes 30
Disciplina de Estrutura de Dados e Armazenamento
Função retira elemento recursiva
1
2
3
4
5
6
7
8
9
10
11
12
public Nodo removeRecursivo(Nodo n, int v){
if(!this.isEmpty(n)){
/*verifica se o elemento a
*ser retirado e o primeiro*/
if(n.getInfo()==v){ n = n.getProx();
}else{
/*retira da sub-lista*/
n.setProx(removeRecursivo(n.getProx(),v));
}
}
return n;
}
Tópicos Principais —
Função retira elemento recursiva
Faculdade de Tecnologia Bandeirantes 31
Disciplina de Estrutura de Dados e Armazenamento
Igualdade de listas
boolean listasIguais(Nodo l1, Nodo l2)
Implementação não recursiva:
• percorre as duas listas usando dois ponteiros auxiliares:
? se duas informações forem diferentes então as listas
são diferentes.
• ao terminar uma das listas ou as duas:
? se os dois ponteiros auxiliares são NULL então as
duas listas tem o mesmo número de elementos e
são iguais.
Tópicos Principais —
Igualdade de listas
Faculdade de Tecnologia Bandeirantes 32
Disciplina de Estrutura de Dados e Armazenamento
Listas iguais: não recursiva
1
2
3
4
5
6
public boolean listasIguais(Nodo l1, Nodo l2){
Nodo t1; /*objeto para percorrer l1*/
Nodo t2; /*objeto para percorrer l2*/
for(t1=l1, t2=l2;
t1 != null && t2 != null;
t1=t1.getProx(), t2=t2.getProx()){
7
if(t1.getInfo() != t2.getInfo())
return false;
8
9
}
return true;
10
11
12
}
Tópicos Principais —
Listas iguais: não recursiva
Faculdade de Tecnologia Bandeirantes 33
Disciplina de Estrutura de Dados e Armazenamento
Igualdade de listas
boolean listasIguais(Nodo l1, Nodo l2)
Implementação recursiva:
• se as duas listas dadas são vazias então são iguais
• se não forem ambas vazias, mas uma delas é vazia,
então são diferentes
• se ambas não forem vazias, teste:
? se informações associadas aos primeiros nós são
iguais e
? se as sub-listas são iguais.
Tópicos Principais —
Igualdade de listas
Faculdade de Tecnologia Bandeirantes 34
Disciplina de Estrutura de Dados e Armazenamento
Listas iguais: recursiva
1
2
3
4
5
6
7
8
9
10
11
public boolean listasIguaisRec(Nodo l1, Nodo l2){
if(l1 == null && l2 == null){
return true;
}else if(l1 == null || l2 == null){
return false;
}else
return
((l1.getInfo()==l2.getInfo())
&&
listasIguaisRec(l1.getProx(),l2.getProx()));
}
Tópicos Principais —
Listas iguais: recursiva
Faculdade de Tecnologia Bandeirantes 35
Disciplina de Estrutura de Dados e Armazenamento
Listas de tipos estruturados
Lista de tipo estruturado:
• a informação associada a cada nó de uma lista
encadeada pode ser mais complexa, sem alterar o
encadeamento dos elementos;
• as funções apresentadas para manipular listas de
inteiros podem ser adaptadas para tratar listas de
outros tipos.
Tópicos Principais —
Listas de tipos estruturados
Faculdade de Tecnologia Bandeirantes 36
Disciplina de Estrutura de Dados e Armazenamento
• o campo da informação pode ser representado por um
objeto para uma estrutura, em lugar da estrutura em
si.
• independente da informação armazenada na lista, a
estrutura do nó é sempre composta por:
? um objeto para a informação e
? um objeto para o próximo nó da lista.
Tópicos Principais —
Listas de tipos estruturados
Faculdade de Tecnologia Bandeirantes 37
Disciplina de Estrutura de Dados e Armazenamento
Listas de tipos estruturados
1
2
3
4
public class Nodo{
private Aluno al;
private Nodo prox;
}
5
6
7
8
9
10
11
12
class Aluno{
private String nome;
private String matricula;
private float n1;
private float n2;
private float n3;
}
Tópicos Principais —
Listas de tipos estruturados
Faculdade de Tecnologia Bandeirantes 38
Disciplina de Estrutura de Dados e Armazenamento
Listas heterogêneas
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Nodo{
private FormasGeometricas fg;
private Nodo prox;
}
public class abstract FormasGeometricas{
private float b;
private float h;
public abstract float calculaArea();
}
public class Retangulo extends FormasGeometricas{
public float calculaArea(){
return b*h;
}
}
public class Triangulo extends FormasGeometricas{
public float calculaArea(){
return b*h/2;
}
}
Tópicos Principais —
Listas heterogêneas
Faculdade de Tecnologia Bandeirantes 39
Tópicos Complementares
40
Disciplina de Estrutura de Dados e Armazenamento
Tópicos Complementares
• Listas Circulares
• Listas Duplamente Encadeadas
Tópicos Complementares —
Tópicos Complementares
Faculdade de Tecnologia Bandeirantes 41
Disciplina de Estrutura de Dados e Armazenamento
Material de consulta
• Capı́tulo 10 do livro: “Introdução a Estruturas de
Dados” do Waldemar Celes, Renato Cerqueira e José
Lucas Rangel.
Tópicos Complementares —
Material de consulta
Faculdade de Tecnologia Bandeirantes 42
Disciplina de Estrutura de Dados e Armazenamento
Material de referência
• Capı́tulo 10 do livro: “Introdução a Estruturas de
Dados” do Waldemar Celes, Renato Cerqueira e José
Lucas Rangel.
• Imagens retiradas do site da disciplina de
Programação II da PUC do Rio de Janeiro.
http://www.inf.puc-rio.br/ inf1007/.
Tópicos Complementares —
Material de referência
Faculdade de Tecnologia Bandeirantes 43