Embed Size (px)
Citation preview
COLÉGIO ESTADUAL ULYSSES GUIMARÃES
CURSO TÉCNICO PROFISSIONALIZANTE EM INFORMÁTICA
ERINALDO SANCHES NASCIMENTO
LISTA DUPLAMENTE ENCADEADA
FOZ DO IGUAÇU
2013
LISTA DE QUADROS
QUADRO 1 – EXEMPLO DE UM NÓ PARA LISTA DUPLAMENTE ENCADEADA ..... 1
QUADRO 2 – CONSTRUTOR PARA NÓS EM LISTA DUPLAMENTE ENCADEADA . 1
QUADRO 3 – ADICIONA O NÓ QUE SERÁ O PRIMEIRO NÓ NA LISTA .................... 2
QUADRO 4 – EXCLUIR UM NÓ DE UMA LISTA DUPLAMENTE ENCADEADA ......... 3
QUADRO 5 – LISTA DUPLAMENTE ENCADEADA COM UM ITERADOR ................. 4
QUADRO 6 – A UTILIZAÇÃO DE UMA LISTA DUPLAMENTE ENCADEADA COM
ITERADOR ........................................................................................................... 8
SUMÁRIO
12 LISTA DUPLAMENTE ENCADEADA ................................................................... 1 12.1 A CLASSE NÓ PARA UMA LISTA DUPLAMENTE ENCADEADA ....................... 1 12.1.1 Método Adicionar no Início ............................................................................... 2 12.1.2 Excluir um Nó ................................................................................................... 3 12.1.3 Exemplo de uma Lista Duplamente Encadeada ............................................... 4 12.2 DEMONSTRAÇÃO DE UMA LISTA DUPLAMENTE ENCADEADA .................... 7 12.3 ESTUDO DE CASO ............................................................................................. 9 12.4 REFERÊNCIAS BIBLIOGRÁFICAS .................................................................. 10
1
12 LISTA DUPLAMENTE ENCADEADA
Uma lista encadeada comum permite mover a lista em uma única direção
(seguindo os links). Uma lista duplamente encadeada tem uma ligação que tem uma
referência para o próximo nó e uma referência para o nó anterior. Em alguns casos,
a ligação ao nó anterior pode simplificar o código.
12.1 A CLASSE NÓ PARA UMA LISTA DUPLAMENTE ENCADEADA
O quadro 1 apresente a classe nó para uma lista duplamente encadeada.
Quadro 1 – Exemplo de um nó para lista duplamente encadeada
private class NoDuplo{
private String item;
private NoDuplo anterior;
private NoDuplo proximo;
Os construtores e alguns métodos na classe lista duplamente encadeada
exigirão mudanças (do caso simplesmente encadeada) em suas definições para
acomodar o link extra. As principais alterações são para os métodos que adiciona e
exclui nós.
O quadro 2 adiciona um novo construtor que define os nós anterior e
próximo.
Quadro 2 – Construtor para nós em lista duplamente encadeada
public NoDuplo(String novoItem, NoDuplo noAnterior,
NoDuplo noProximo){
item = novoItem;
proximo = noProximo;
anterior = noAnterior;
2
}
12.1.1 Método Adicionar no Início
Para adicionar um novo nó no início da lista requer a criação de links em
dois nós em vez de um. A figura 1exibe uma lista duplamente encadeada. No
método addInicio, primeiro cria-se um novo noDuplo. O novo nó vai no início da lista,
definindo-se o link anterior para nulo e o próximo link para o atual nó cabeça.
Figura 1 – Uma lista duplamente encadeada.
Em seguida, deve-se definir o link anterior no nó principal antigo para fazer
referência ao novo nó cabeça. Deve-se tomar cuidado para garantir que a cabeça
não seja nulo (ou seja, a lista não está vazia).
O quadro 3 mostra o processo para adicionar um novo nó ao início. Nesse
caso, o novo nó será inserido na frente do iterador referenciado por posição.
Quadro 3 – Adiciona o nó que será o primeiro nó na lista
public void addInicio(String nomeItem){
NoDuplo novaCabeca = new NoDuplo(nomeItem, null, cabeca);
if (cabeca != null){
cabeca.anterior = novaCabeca;
}
cabeca = novaCabeca;
}
3
Há também casos especiais para a rotina de inserção quando a inserção no
início ou ao fim da lista.
12.1.2 Excluir um Nó
Para excluir um nó de uma lista duplamente encadeada também exige a
atualização das referências de ambos os lados do nó a ser excluído. A exclusão de
um nó no início ou no final da lista devem ser tratados separadamente.
O processo geral de exclusão de um nó referenciado por posição é mostrado
no quadro 4.
Quadro 4 – Excluir um nó de uma lista duplamente encadeada
public void excluir(){
if (posicao == null)
throw new IllegalStateException();
else if (posicao.anterior == null){
//Exclui o primeiro nó
cabeca = cabeca.proximo;
posicao = cabeca;
}
else if (posicao.proximo == null){
//Exclui o último nó
posicao.anterior.proximo = null;
posicao = null;
}
else{
posicao.anterior.proximo = posicao.proximo;
posicao.proximo.anterior = posicao.anterior;
posicao = posicao.proximo;
}
}
4
12.1.3 Exemplo de uma Lista Duplamente Encadeada
O quadro 5 apresenta um exemplo completo de uma lista duplamente
encadeada. O uso da lista duplamente encadeada é praticamente idêntico ao de
uma lista simplesmente encadeada.
Quadro 5 – Lista duplamente encadeada com um iterador
1 package listaduplamenteendadeada;
2
3 import java.util.NoSuchElementException;
4
5 public class ListaDuplamenteEncadeada {
6 private class NoDuplo{
7 private String item;
8 private NoDuplo anterior;
9 private NoDuplo proximo;
10
11 public NoDuplo(){
12 item = null;
13 proximo = null;
14 anterior = null;
15 }
16
17 public NoDuplo(String novoItem, NoDuplo noAnterior,
18 NoDuplo noProximo){
19 item = novoItem;
20 proximo = noProximo;
21 anterior = noAnterior;
22 }
23 }//fim da classe interna NoDuplo
24
25 public class IteradorDuplamenteLigado{
5
26 private NoDuplo posicao = null;
27
28 public IteradorDuplamenteLigado(){
29 posicao = cabeca;
30 }
31 public void reiniciar(){
32 posicao = cabeca;
33 }
34
35 public boolean temProximo(){
36 return (posicao != null);
37 }
38
39 public String observar(){
40 if (!temProximo())
41 throw new IllegalStateException();
42 return posicao.item;
43 }
44
45 public String proximo(){
46 if (!temProximo())
47 throw new IllegalStateException();
48 String retorno = posicao.item;
49 posicao = posicao.proximo;
50 return retorno;
51 }
52 public void insereAqui(String novoDado){
53 if (posicao == null && cabeca != null){
54 /*
55 * Adiciona ao fim.
56 * Primeiro move um ponteiro temporário para o
final da lista.
57 */
6
58 NoDuplo temp = cabeca;
59 while (temp.proximo != null)
60 temp = temp.proximo;
61 temp.proximo = new NoDuplo(novoDado, temp,
null);
62 }
63 else if (cabeca == null || posicao.anterior == null)
64 //a cabeça de lista
65 ListaDuplamenteEncadeada.this.addInicio(novoDado);
66 else{
67 //insere antes da posição atual
68 NoDuplo temp = new NoDuplo(novoDado,
69 posicao.anterior, posicao);
70 posicao.anterior.proximo = temp;
71 posicao.anterior = temp;
72 }
73 }
74
75 public void excluir(){
76 if (posicao == null)
77 throw new IllegalStateException();
78 else if (posicao.anterior == null){
79 //Exclui o primeiro nó
80 cabeca = cabeca.proximo;
81 posicao = cabeca;
82 }
83 else if (posicao.proximo == null){
84 //Exclui o último nó
85 posicao.anterior.proximo = null;
86 posicao = null;
87 }
88 else{
89 posicao.anterior.proximo = posicao.proximo;
7
90 posicao.proximo.anterior = posicao.anterior;
91 posicao = posicao.proximo;
92 }
93 }
94 }//Iterador Duplamente Ligado
95
96 private NoDuplo cabeca;
97
98 public IteradorDuplamenteLigado iterador(){
99 return new IteradorDuplamenteLigado();
100 }
101
102 public ListaDuplamenteEncadeada(){
103 cabeca = null;
104 }
105
106 //adiciona o nó que será o primeiro nó na lista
107 public void addInicio(String nomeItem){
108 NoDuplo novaCabeca = new NoDuplo(nomeItem, null, cabeca);
109 if (cabeca != null){
110 cabeca.anterior = novaCabeca;
111 }
112 cabeca = novaCabeca;
113 }
114 }
12.2 DEMONSTRAÇÃO DE UMA LISTA DUPLAMENTE ENCADEADA
O quadro 6 demonstra os métodos de adição, exclusão e inclusão em uma
lista duplamente ligada.
8
Quadro 6 – A utilização de uma lista duplamente encadeada com iterador
1 package listaduplamenteendadeada;
2
3 public class AppListaDuplamenteEncadeada {
4 public static void main(String[] args) {
5 ListaDuplamenteEncadeada lista = new
ListaDuplamenteEncadeada();
6 ListaDuplamenteEncadeada.IteradorDuplamenteLigado i =
lista.iterador();
7
8 lista.addInicio("Sapatos");
9 lista.addInicio("Suco de laranja");
10 lista.addInicio("Casaco");
11 System.out.println("A lista contém:");
12 i.reiniciar();
13 while (i.temProximo())
14 System.out.println(i.proximo());
15 System.out.println();
16 i.reiniciar();
17 i.proximo();
18 i.proximo();
19 System.out.println("Apaga "+i.observar());
20 i.excluir();
21
22 System.out.println("A lista agora contém: ");
23 i.reiniciar();
24 while(i.temProximo())
25 System.out.println(i.proximo());
26 System.out.println();
27
28 i.reiniciar();
29 i.proximo();
30 System.out.println("Inserir Meias antes de "+i.observar());
9
31 i.insereAqui("Meias");
32
33 i.reiniciar();
34 System.out.println("A lista agora contém:");
35 while (i.temProximo())
36 System.out.println(i.proximo());
37 System.out.println();
38 }
39 }
A figura 2 mostra a saída produzida pela aplicação de exemplo.
Figura 2 – Exemplo da saída produzida pela aplicação.
12.3 ESTUDO DE CASO
Desenvolva um programa para uma pequena biblioteca para incluir novos
livros, registrar a saída e o retorno de livros.
1. Crie uma lista simplesmente encadeada incluindo os autores de todos os livros
da biblioteca.
A lista deve ser ordenada alfabeticamente e a busca pode ser interrompida se
o nome for autor for encontrado ou se atingirmos o final da lista.
10
2. O programa usa uma matriz Pessoas de todas as pessoas que usaram a
biblioteca pelo menos uma vez. Essa matriz deve ser indexada pela letra.
3. O programa define quatro classes: Autor, Livro, Pessoa e LivroRetirado.
12.4 REFERÊNCIAS BIBLIOGRÁFICAS
DROZDEK, Adam. Estrutura de dados e algoritmos em C++. 1ª Edição. São
Paulo: Cengage Learning, 2009.
SAVITCH, Walter. Absolute Java, 5ª ed. New Jersey: Pearson Education, 2012.
