4a Listas Encadeadas

Prévia do material em texto

Estrutura de Dados
Aula 4 - Listas Simplesmente Encadeadas
UNIP – Universidade Paulista
Prof. Rafael de Alencar Segura Última atualização: 2º Sem 2017
Índice
• Listas
• Introdução
• Vantagens em relação ao uso de vetores 
• Alocação dinâmica
• Listas Encadeadas
• Listas Simples
• Listas Circulares
• Listas Duplamente Encadeadas
• Listas Simples Encadeadas
• Nós
• Inserindo no início
• Exibindo elementos
• Excluindo no início
• Pesquisando elemento
• Inserindo em outro ponto da lista
• Excluindo em outro ponto da lista
Listas
• É uma coleção de elementos do mesmo tipo, dispostos 
linearmente, que podem ou não seguir determinada 
organização.
Exemplo de lista simples
Lista de pagamentos
Prestação do carro
Cartão de crédito
Conta de luz
Condomínio
TV a cabo
Supermercado
• Lista de pagamentos ← [prestação do carro, cartão de crédito, conta de luz, 
condomínio, TV a cabo, supermercado]
Essa é uma lista 
que possui seis 
elementos do tipo 
literal, e os 
elementos estão 
armazenados em um 
vetor .
Lista simples: relembrando vetores — pseudocódigo 
Var
Lista_pagamentos: vetor[0..5] de literais
Inicio
Lista_pagamento[0] ← “prestação do carro” 
Lista_pagamento[1] ← “cartão de crédito”
Lista_pagamento[2] ← “conta de luz”
Lista_pagamento[3] ← “ condomínio”
Lista_pagamento[4] ← “ TV a cabo”
Lista_pagamento[5] ← “ Supermercado”
Slide 6
Lista simples: relembrando vetores — Java 
String Lista_pagamento[];
Lista_pagamentos = new String[6];
Lista_pagamento[0] = “prestação do carro” ;
Lista_pagamento[1] = “cartão de crédito”;
Lista_pagamento[2] = “conta de luz”;
Lista_pagamento[3] = “ condomínio”;
Lista_pagamento[4] = “ TV a cabo”;
Lista_pagamento[5] = “ Supermercado”;
LISTA 
SIMPLESMENTE 
ENCADEADA
Slide 8
Lista encadeada
• É um conjunto de elementos que estão dispostos em uma dada organização 
física não linear, isto é, estão espalhados pela memória.
Lista encadeada — exemplo: lista de pagamentos
Lista de pagamentos Próximo elemento
(1) Prestação do carro 2
(2) Cartão de crédito 3
(3) Conta de luz 4
(4) Condomínio 5
(5) TV a cabo 6
(6) Supermercado Não tem próximo elemento
Tipos de listas encadeadas
• Listas de encadeamento simples.
• Listas duplamente encadeadas.
• Listas circulares.
Listas de Encadeamento Simples – Listas Simplesmente Encadeadas
• O primeiro elemento da lista é E1.
• O último elemento da lista é Em.
• O predecessor de E2 é E1.
• O sucessor de E2 é E3.
• E assim por diante até o último elemento.
E1 E2 E3 En...
Listas de Encadeamento Simples Circular – Listas Circulares Simplesmente Encadeadas
• O próximo do último elemento é o primeiro elemento da lista ( E1) .
E1 E2 E3 En...
Listas Duplamente Encadeadas
• Cada elemento possui um campo que aponta 
para o seu predecessor (anterior) e outro para 
o seu sucessor (próximo):
Listas Circulares Duplamente Encadeadas
• O ponteiro próximo do último elemento aponta para 
o primeiro; e o ponteiro anterior do primeiro 
elemento aponta para o último.
Relembrando.....
Link someLink = new Link();
Link aLink = someLink;
Cria o objeto 
someLink e 
instancia o 
mesmo
Cria o objeto 
aLink e 
referencia outro 
objeto do tipo 
Link 
Exemplo das Alocações.....
O heap é acessado através de ponteiros. Mesmo em linguagens que não exista o conceito de ponteiros 
disponíveis para o programador, isto é realizado internamente.
Stack = alocação estática
Heap = alocação dinâmica
Referência imagem: https://pt.stackoverflow.com/questions/3797/o-que-s%C3%A3o-e-onde-est%C3%A3o-o-stack-e-heap
Estruturas de Dados Dinâmicas
• Nós
O nó de uma lista simples possui uma área de dados e uma área contendo a referência para o próximo elemento
1001
A1
1002
A2
1003
A3
1004
A4
1005
A5
Estruturas de Dados Dinâmicas
• Lista
1001
A1
1002
A2
1003
A3
1004
A4
1005
A5
null
Referência 
primeiro 
elemento
Último 
elemento
NoSimples
valor
prox
NoSimples
Código Java — NoSimples
package ListasEncadeadas;
public class NoSimples {
private int valor;
private NoSimples prox;
NoSimples (int valorNo){
valor=valorNo;
prox=null;
}
public void mostrarNo() {
System.out.print("O número do aluno é: " + valor + "\n");
}
public int getValor() {
return valor;
}
public void setValor(int valor) {
this.valor = valor;
}
public NoSimples getProx() {
return prox;
}
public void setProx(NoSimples prox) {
this.prox = prox;
}
}
-int: valor
-NoSimples prox;
+NoSimples(int valorNo)
+mostrarNo():void
+getValor():int
+setValor(int: valor):void
+getProx():NoSimples
+setProx(NoSimples prox):void
NoSimples
ListaSimples
null
ListaSimples
referenciaPrimeiroNo
A classe ListaSimples cria a estrutura de uma lista cujos nós terão a estrutura definida pela classe NoSimples
Código Java - ListaSimples
package ListasEncadeadas;
public class ListaSimples {
private NoSimples referenciaPrimeiroNo;
private int tamanho;
ListaSimples(){
referenciaPrimeiroNo=null;
tamanho=0;
}
-NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
1) Lista Vazia?
2)Inserindo no Início 
da Lista Encadeada
null
ListaSimples
null
ListaSimples
ListaSimples: Inserindo no início : Funcionamento
null
referenciaPrimeiroNo
1 Lista vazia
valor null
referenciaPrimeiroNo
1 Lista com um nó
valor null
valor
novoNo
referenciaPrimeiroNo
2 criando novo nó
valor nullvalor
referenciaPrimeiroNo
referenciaPrimeiroNo apontando para o novoNo
valor
novoNo null
referenciaPrimeiroNo
Criado o primeiro nó 2
valor
novoNo
null
referenciaPrimeiroNo
referenciaPrimeiroNo apontando para o novoNo3
valor null
valor
novoNo
referenciaPrimeiroNo
3 novoNo aponta para referenciaPrimeiroNo
4
Código Java - ListaSimples: Verificando se a lista está vazia e inserindo no início
//isEmpty
public boolean estaVazia () {
return (referenciaPrimeiroNo==null);
}
//insertFirst
public void inserirNoInicio(int valor) {
NoSimples novoNo= new NoSimples(valor);
novoNo.setProx(referenciaPrimeiroNo);
referenciaPrimeiroNo= novoNo;
tamanho++;
}
Retorna se a Lista está vazia: 
true= vazia
false não vazia
-NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
Apagando no 
Início da Lista 
Encadeada
null
Código Java — ListaSimples: Apagando o primeiro elemento da lista
ListaSimples
//deleteFirst
public void apagarPrimeiro() {
NoSimples temp=referenciaPrimeiroNo;
System.out.println("Apagando o nó " + referenciaPrimeiroNo.getValor() + 
"\n");
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
temp.setProx(null);
tamanho--;
}
valor nullvalor
referenciaPrimeiroNo
valor nullvalor
referenciaPrimeiroNo
valor null
referenciaPrimeiroNo
-NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
Exibindo 
Elementos da 
Lista Encadeada
null
Código Java — ListaSimples: Mostrar Elementos da Lista
public void mostrarLista () {
NoSimples no = referenciaPrimeiroNo;
while(no != null) {
no.mostrarNo();no=no.getProx();
}
-NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
Código Java — ListaSimplesApp
package ListasEncadeadas;
public class ListaSimplesApp {
public static void main (String args[]) {
ListaSimples Aluno = new ListaSimples();
Aluno.inserirNoInicio(1001);
Aluno.inserirNoInicio(1002);
Aluno.inserirNoInicio(1003);
Aluno.inserirNoInicio(1004);
Aluno.inserirNoInicio(1005);
Aluno.mostrarLista();
Aluno.apagarPrimeiro();
Aluno.mostrarLista();
}
}
Implementar 
método que 
retorne o 
tamanho da 
lista e testar
Exercícios
Alterar o programa 
ListaSimplesApp para:
Solicitar , via JOptionPane, a 
entrada dos valores.
Alterar o método 
apagarPrimeira de modo que 
se a lista estiver vazia exibir 
uma mensagem dizendo que 
a lista está vazia e finalizar o 
programa.
Busca de 
Elementos na 
Lista Encadeada
BUSCA DE UM DETERMINADO NÓ NA LISTA ENCADEADA [I/V]
public NoSimples buscarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
while (atual.getValor() != val) {
if (atual.getProx()==null)
return null;
else
atual=atual.getProx();
}
return atual;
}
1002 null1001
referenciaPrimeiroNo
atual
buscarNo
(1002)
- NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
public NoSimples buscarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
while (atual.getValor() != val) {
if (atual.getProx()==null)
return null;
else
atual=atual.getProx();
}
return atual;
}
1002 null1001
referenciaPrimeiroNo
atual
BUSCA DE UM DETERMINADO NÓ NA LISTA ENCADEADA [II/V]
buscarNo
(1002)
É 
nulo?
public NoSimples buscarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
while (atual.getValor() != val) {
if (atual.getProx()==null)
return null;
else
atual=atual.getProx();
}
return atual;
}
1002 null1001
referenciaPrimeiroNo
atual
BUSCA DE UM DETERMINADO NÓ NA LISTA ENCADEADA [III/V]
buscarNo
(1002)
public NoSimples buscarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
while (atual.getValor() != val) {
if (atual.getProx()==null)
return null;
else
atual=atual.getProx();
}
return atual;
}
1002 null1001
referenciaPrimeiroNo
atual
BUSCA DE UM DETERMINADO NÓ NA LISTA ENCADEADA [IV/V]
buscarNo
(1002)
public NoSimples buscarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
while (atual.getValor() != val) {
if (atual.getProx()==null)
return null;
else
atual=atual.getProx();
}
return atual;
}
1002
buscarNo
(1002)
atual
BUSCA DE UM DETERMINADO NÓ NA LISTA ENCADEADA [V/V]
Buscando e 
Apagando 
Elemento da Lista 
Encadeada
deletarNo
1004
atual
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // nao encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx(
);
else{
anterior.setProx(atual.getProx());
atual.setProx(null); 
}
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
- NoSimples: referenciaPrimeiroNo
-int tamanho
+ListaSimples()
+estaVazia():boolean
+inserirNoInicio(int valor) : void
+apagarPrimeiro(): void
+mostarLista(): void
+buscarNo(int val):NoSimples
+deletarNo(int val):NoSimples
ListaSimples
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null); 
}
tamanho--; 
return atual;
}
deletarNo
1004
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual.getValor()=1001 != 1004 ?
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
}
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
É nulo?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
}
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual.getValor()=1002!= 1004 ?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
}
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
É nulo?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimplesatual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual.getValor()=1003!= 1004 ?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
É nulo?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual;
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual.getValor()=1004!= 1004 ?
FALSO!!!
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else {
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual == referenciaPrimeiroNo?
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else{
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
anterior
1001 1002 1003 1004 1005
referencia
PrimeiroNo
null
atual
1001 1002 1003 1005
referencia
PrimeiroNo
null
deletarNo
1004
DELEÇÃO DE UM DETERMINADO NÓ NA LISTA ENCADEADA
public NoSimples deletarNo(int val) {
NoSimples atual = referenciaPrimeiroNo;
NoSimples anterior=referenciaPrimeiroNo;
while (atual.getValor()!= val) {
if (atual.getProx()==null)
return null; // não encontrou valor
else
{
anterior=atual; 
atual=atual.getProx();
}
}
if (atual==referenciaPrimeiroNo) 
referenciaPrimeiroNo=referenciaPrimeiroNo.getProx();
else{
anterior.setProx(atual.getProx());
atual.setProx(null);
} 
tamanho--; 
return atual;
}
1004
Referências Bibliográficas
O material desta aula foi baseado e adaptado dos livros abaixo:
Estruturas de Dados 
Fundamentais -
Conceitos e Aplicações
Silvio do Lago Pereira.
Editora: Érica 2 ed. 1996