Estruturas de Dados - Filas e Listas

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Filas e Listas
Definição de Fila
● Fila é um conjunto ordenado de ítens do qual 
pode-se retirar ítens de uma extremidade, 
denominada início, e colocar ítens na outra 
extremidade, denominada fim da fila.
● A estrutura fila é também denominada lista 
fifo (first in first out, isso é, o primeiro a 
entrar é o primeiro a sair). O conceito é 
nosso conhecido de longa data, em bancos, 
lojas, restaurantes universitário e outros 
locais :)
Definição de Fila
● As três operações principais em filas 
são:
– inserirf (f, x), na qual o ítem x é inserido no final da fila f 
(teoricamente não ocorre overflow em uma fila – na 
prática pode haver)
– x = removerf (f), na qual o elemento que está no início 
da fila é removido e entregue na variável x
– vaziaf (f), que retorna true ou false, dependendo se a 
fila contém ou não contém elementos. 
Definição de Fila
● Após a seqüência de inserções:
 inserirf(f,'A'); inserirf(f,'B'); inserirf(f,'C')
● A fila f ficaria assim:
 iní
 A B C
 fim
Definição de Fila
● Após a operação:
 x = removerf (f)
● A fila f ficaria assim:
 iní
 B C
 fim
Definição de Fila
● Após a seqüência de inserções:
 inserirf (f,'D'); inserirf (f,'E')
● A fila f ficaria assim:
 iní
 B C D E
 fim
Implementação de Fila
● Em C, uma fila pode ser implementada por meio de 
um vetor, usado de forma circular:
 #define MAXF 5
 typedef struct fila {
 char item[MAXF];
 int ini, fim;
 } 
 ini
 B C D E
 0 1 2 3 4 
 
 fim
Implementação de Fila
● A idéia é: quando um espaço é liberado no 
início, ele pode ser reusado, isso é, na 
inserção, se o ponteiro fim == MAXF, ele se 
torna 0 (se a posição 0 estiver disponível)
 
 
 ini
 F B C D E
 0 1 2 3 4 
 fim
Implementação de Fila
● Porém na tentativa de inserção, de um novo 
elemento, o ponteiro de início ficaria igual ao 
ponteiro de fim...
 
 
 ini
 F B C D E
 0 1 2 3 4 
 fim
Implementação de Fila
● Uma boa idéia seria inicializar a fila 
com ini e fim = a MAXF-1:
 
void initf (fila *f) {
 int i;
 f->ini=f->fim=MAXF-1;
 for (i=0;i<MAXF;i++) f->item[i]=' ';
}
Implementação de Fila
● Esquematicamente, uma fila recém criada 
teria o seguinte aspecto, com ini == fim :
 
 ini
 
 0 1 2 3 4 
 fim
Implementação de Fila
● Porém, após sucessivas inclusões e retiradas, a 
fila vazia poderia ter qualquer aspecto :
 
 ini
 
 0 1 2 3 4 
 fim
Implementação de Fila
● O algorítmo de inserção sacrifica uma 
posição para diferenciar fila cheia e 
vazia:
 void inserirf (fila *f, char x); {
 if (f->fim==MAXF -1) f->fim=0;
 else f->fim++;
 if (f->fim==f->ini) {
 printf(''Estouro na fila'');
 exit(1); }
 else f->item[f->fim] = x;
 return;
 }
Implementação de Fila
● Na retirada de um elemento, a posição do 
início será adiantada... mas isso somente se 
houver ao menos um elemento na fila:
 
 ini
 F C D E
 0 1 2 3 4 
 fim
Implementação de Fila
● Na retirada de um elemento, a posição do 
início será adiantada... mas isso somente se 
houver ao menos um elemento na fila:
 
 ini
 F D E
 0 1 2 3 4 
 fim
Implementação de Fila
● Porisso é necessário um algoritmo de 
verificação se há elementos na fila:
 
 int vaziaf(fila *f) {
 return f->ini == f->fim;
}
Implementação de Fila
● E dessa forma o algoritmo de retirada é 
assim
 
 
char retirarf(fila *f) {
 if (vaziaf(f)) {
 printf("Underflow na fila");
 exit(1);
 }
 if (f->ini==MAXF-1) f->ini=0;
 else f->ini++;
 return f->item[f->ini]; 
}
Fila de prioridade
● Uma fila de prioridade é uma fila na qual os 
elementos são inseridos na ordem que chegam 
mas são retirados em uma ordem específica – 
pode ser pelo valor de um campo do nodo de 
informação, ou por algum outro critério 
calculável, em ordem ascendente ou 
descendente.
● Uma pilha é uma fila de prioridade pelo tempo, 
em ordem descendente :)
 
 
Fila de prioridade
● Em pilhas ou filas não é necessária nenhuma 
busca para a remoção de um elemento
● Em filas de prioridade, sim
● As operações possíveis são as mesmas, 
basicamente:
– insere
– remove
– vazia
– cheia (?)
 
 
Fila de prioridade
● Como nos outros casos, é possível a utilização 
de vetores para implementar uma fila de 
prioridades
● No entanto, são necessárias algumas decisões 
estratégicas:
– A ordenação será na entrada ou na saída?
– Os espaços serão reusados? 
– Será feita compactação dos dados retirados? 
Quando? Se faltar espaço?
 
 
Fila de prioridade
● Formem grupos de quatro pessoas, discutam e 
definam uma solução para fila de prioridades 
usando vetor como estrutura básica de dados
● Definam os tipos e os procedimentos
● Ao final da aula, cada grupo apresentará sua 
solução, justificando.
 
 
Listas encadeadas
● A implementação de filas através de arrays 
tem um problema fundamental – a limitação 
de espaço – quando acabar o espaço máximo 
do array, acabou a fila.
● Uma alternativa é tratar os nodos de 
informação com elementos independentes no 
ponto de vista espacial, que contém, 
entretanto, um ponteiro para o próximo 
elemento da lista.
 
 
Listas encadeadas
● O esquema seguinte ilustra o modelo:
lista
 info prox
 info prox
 info prox
 info prox
 
 
Listas encadeadas
● Nesse modelo, no início a lista está vazia e 
aponta para um endereço ´´nulo´´.
● Não existe, nesse momento, nenhum espaço 
alocado para a lista.
● É requerido, portanto, um mecanismo para 
prover o espaço, quando ele for necessário
● Da mesma forma, é interessante poder 
devolver-se espaço que não é mais preciso.
 
 
Listas encadeadas
● Esses procedimentos, conceitualmente devem 
funcionar assim:
● p = getnode( ) - arranja um espaço para 
abrigar o nodo e devolve, em p, o endereço
● freenode (p) – volta o espaço não mais 
necessário, apontado por p, para a lista de 
espaço disponível
 
 
Listas encadeadas
● Linguagens distintas implementam essas 
funções de formas diferentes.
● No caso de C, utiliza-se para essa finalidade as 
funções de biblioteca padrão (stdlib.h) malloc, 
free, calloc e realloc.
● void *malloc (size_t size) – retorna umponteiro para o primeiro byte de memória de 
tamanho size, alocado do heap.
 
 
Listas encadeadas
● void *free (void *ptr) – retorna ao heap 
a área de memória apontada por *ptr. 
● void *calloc (size_t num, size_t size) – 
retorna um ponteiro para o primeiro byte 
de memória de tamanho num * size, 
alocado do heap.
 
 
Listas encadeadas
● void *realloc (void *ptr, size_t size) – muda o 
tamanho da área de memória apontada por 
*ptr. A área pode ser maior ou menor, e o 
ponteiro pode apontar para a mesma ou para 
outra posição. Não há perda de dado.
● Em todos os casos, quando o ponteiro 
retornado é nulo, significa que não foi possível 
alocar o espaço requerido. Em *realloc, o 
tamanho == 0 significa que o espaço deve ser 
liberado.
 
 
Listas encadeadas
● As listas encadeadas podem servir para 
implementar estruturas de dados 
diferentes. Por exemplo, uma pilha:
 s 5 3 8
 
 
O topo da pilha é apontado por s, e o fundo é encontrado 
quando o ponteiro do próximo elemento == nulo
Listas encadeadas
● As estruturas de dados em C
struct nodo{
 char info;
 struct nodo *prox;
};
typedef struct nodo *ptrnodo;
● Uma pilha começa com um ponteiro vazio:
ptrnodo pilha = NULL; 
 
Listas encadeadas
● A operação push (&s, x) pode ser assim:
void push (ptrnodo *s, char x) {
 ptrnodo p;
 p = malloc (sizeof(struct nodo));
 p->info=x;
 p->prox=*s;
 *s = p;
 contanodo++;
} 
 
Listas encadeadas
● A operação pop (&s) pode ser assim:
 ptrnodo pop (ptrnodo *s) {
 ptrnodo p;
 p=*s;
 *s=p->prox;
 contanodo--;
 return (p);
}
● Ela devolve um ponteiro para o elemento 
retirado
 
Listas encadeadas
● Para imprimir a pilha:
int vazia (ptrnodo s) {
 return (s==NULL);
}
void printpilha(ptrnodo s) {
 int i;
 i=contanodo-1;
 do {
 if (!vazia(s)) {
 printf("pilha[%i] info=%c prox=%d\n",i, s->info,s->prox);
 s=s->prox;
 i--;
 }
 } while (!vazia(s)); 
} 
Listas encadeadas
● int main(void) {
● char func, val, nl;
● ptrnodo temp, pilha=NULL;
● do {
● printf("Entre funcao: (e)mpilhar, (d)esempilhar, (p)arar, e o valor: ");
● scanf("%c %c%c", &func, &val, &nl); // por exemplo 'e a' para empilhar o valor a
● if (func == 'e') { 
● push(&pilha,val);
● printpilha(pilha);
● } else 
● if (func == 'd') {
● if (vazia(pilha)) printf("Impossível tirar, pilha vazia\n");
● else { temp=pop(&pilha);
● printf("desemp val == %c prox == %i\n", temp->info, temp->prox);
● if (!vazia(pilha)) {
● printpilha(pilha);
● free(temp);
● temp=NULL;
● }
● }
● } else 
● if (func !='p') printf("func invalida\n");
● } while(func != 'p');
● return 0;
● }
Listas encadeadas
● Discussão:
Como modificar o programa para fazer 
uma fila FIFO ao invés de uma pilha?
Listas encadeadas
● As listas encadeadas podem servir para 
implementar filas também:
 fim
 inicio 5 3 8 
 
 
 
Serão necessários dois ponteiros, um para o início e outro 
para o fim da fila. 
Listas encadeadas
● Os algorítmos são simples, uma vez que os 
elementos são incluídos no fim e retirados do 
início.
● O único cuidado especial deve ocorrer quando 
retira-se o último elemento da lista, situação 
na qual o ponteiro de fim também deve se 
tornar nulo também.
Listas encadeadas
● Retirada do último elemento:
 fim
 fim
 inicio 8 inicio 
 
 
 
Listas encadeadas
● O algorítmo de retirada (tira) pode ser 
assim:
 
ptrnodo tira (ptrnodo *i, ptrnodo *f) {
 ptrnodo p;
 p=*i;
 *i=(*i)->prox;
 if (*i==NULL) *f=NULL; /* ultimo elemento retirado... 
*/
 contanodo--;
 return (p);
}
Listas encadeadas
● O algorítmo de inclusão (poe) pode ser 
assim:
 
 void poe (ptrnodo *f, ptrnodo *i, char x) {
 ptrnodo p;
 p = malloc (sizeof(struct nodo));
 p->info=x;
 p->prox=NULL;
 if (*f==NULL) *i=p;
 else (*f)->prox=p;
 *f = p;
 contanodo++;
}
Listas encadeadas
● O programa principal: 
 
 
int main(void) {
 char func, val, nl;
 ptrnodo temp, inicio=NULL, fim=NULL;
 do {
 printf("Entre funcao: (r)etira, (p)õe, (t)ermina, e o valor: ");
 scanf("%c %c%c", &func, &val, &nl); 
 if (func == 'p') { 
 poe(&fim,&inicio,val);
 printf("=> incluido valor == %c prox == %i\n",inicio->info,inicio->prox); 
 printfila(inicio);
 } else 
 if (func == 'r') {
 if (vazia(inicio)) printf("Impossível tirar, fila vazia\n");
 else { temp=tira(&inicio,&fim);
 printf("=> retirado valor == %c prox == %i\n",temp->info,temp->prox);
 if (!vazia(inicio))
 printfila(inicio);
 free(temp);
 temp=NULL;}
 } else 
if (func !='t') printf("func invalida\n");
 } while(func != 't');
 return 0;
Fila de prioridade em 
listas encadeadas
● O segredo é manter a lista ordenada por 
prioridade.
● O primeiro elemento é sempre o de maior 
prioridade, e o algoritmo de busca é trivial – 
igual ao ´´tira´´ já mostrado
 
 
Fila de prioridade em 
listas encadeadas
● Para a inclusão, no entanto, deve-se percorrer 
a lista até encontrar o primeiro elemento de 
menor prioridade...
● O elemento ´´entrante´´ fica na frente deste.
● Como fazê-lo? Modificar o procedimento “poe“ 
para atender a essa exigência:
 
 
Listas encadeadas em 
vetores
● É possível a implementação do conceito de 
listas encadeadas em vetores.
● A idéia é ter os nós de informação em um 
vetor, incluindo um campo que é um índice 
que aponta para o próximo elemento da lista.
● Um vetor como esse pode ter várias listas 
convivendo juntas
 
 
Listas encadeadas em 
vetores
● Exemplo:
 info próximo
 0: Marco 7 
1: Maria 11
2: José 0
3: Carla -1
Lista H -> 4: Paulo 2
5:
Lista M -> 6: Arminda 1
7: Antonio -1
8:
9: Joaquina 3
10:
11: Joana 9
12:
...
 
Listas encadeadas 
circulares
● Uma das dificuldades das listas encadeadas é 
o atingimento de um nodo já processado, ou 
ultrapassado. Se não houver um ponteiro 
externo à lista, esse nó não pode mais ser 
atingido.
● Uma forma de contornar isso são as listas 
circulares.
 
Listas encadeadas 
circulares
●
 
 5 3 8 
 
 
 
● Uma lista circular não tem um primeiro ou um último 
elemento natural
Listas encadeadas 
circulares
● Uma boa estratégia seria manter um 
ponteiro para o fim da lista.
 fim
 
 5 3 8 
 
 
 
● Dessa forma será possível atingir o fim da lista e o seu início, 
logo a seguir...
Listas encadeadas 
circulares
● Tal estrutura permite implementar pilhas ou 
filas. 
Veja algoritmo para colocar um elemento em 
uma pilha circular:Pilhas encadeadas 
circulares
● Para incluir um elemento:
 
●
 
●
 void pushcirc (ptrnodo *u, char x) {
 ptrnodo p;
 p = malloc (sizeof(struct nodo));
 p->info=x;
 if (vazia(*u)) *u=p;
 else p->prox = (*u)->prox;
 (*u)->prox = p;
 contanodo++;
}
Pilhas encadeadas 
circulares
● Para retirar um elemento:
char popcirc (ptrnodo *u) {
 char x;
 ptrnodo p;
 p=(*u)->prox;
 x=p->info;
 if (p==*u) // ha somente um nó na pilha
 *u=NULL;
 else 
 (*u)->prox=p->prox;
 contanodo--;
 free(p);
 return (x);
}
 
Pilhas encadeadas 
circulares
● Para listar pilhas circulares
void printpilhacirc(ptrnodo u) {
 int i;
 ptrnodo p;
 i=contanodo-1;
 p=u->prox;
 while (i>-1) {
 printf("pilha[%i] info=%c prox=%d\n",i, p->info,p->prox);
 p=p->prox;
 i--;
 }
} 
Filas encadeadas 
circulares
● Os algoritmos para manipular filas do tipo fifo 
em listas circulares são muito semelhantes aos 
algorítmos de pilhas circulares. 
● A única diferença algorítmica é que o 
procedimento poe da fila é equivalente à
push(&fim, x);
 fim = fim->prox; 
Listas encadeadas 
circulares
● De fato, para a pilha seguinte:
 fim
 
 5 3 8 
 
 
 
● A inclusão de um nó seria esquemáticamente assim:
Listas encadeadas 
circulares
● De fato, para a pilha seguinte:
 fim
 
 5 3 8 
 
 7
 
● A inclusão de um nó seria esquemáticamente assim:
Listas encadeadas 
circulares
● E para uma fila, seria assim:
 fim
 
 5 3 8 
 
 7
 
Listas encadeadas 
circulares
● O seguinte algoritmo de inclusão na fila 
resolveria o problema:
void poecirc (ptrnodo *u, char x) {
 ptrnodo p;
 p = malloc (sizeof(struct nodo));
 p->info=x;
 if (vazia(*u)) *u=p;
 else p->prox = (*u)->prox;
 (*u)->prox = p;
 *u=p; // <=== aqui a unica diferença
 contanodo++;}
Listas encadeadas 
circulares
● E para retirar da fila faríamos o mesmo que no pop:
char retcirc (ptrnodo *u) {
 char x;
 ptrnodo p;
 p=(*u)->prox;
 x=p->info;
 if (p==*u) // ha somente um nó na pilha
 *u=NULL;
 else 
 (*u)->prox=p->prox;
 contanodo--;
 free(p);
 return (x);
}
Listas duplamente 
encadeadas
● Essas listas permitem caminhar-se nos dois 
sentidos, pois cada nó tem 2 ponteiros:
● O ponteiro esquerdo do primeiro nó e o direito 
do último apontam para ´´nulo´´
Listas duplamente 
encadeadas
● Cada uma das listas pode também ser circular:
Listas duplamente 
encadeadas
● As estruturas de dados em C pode ser 
assim:
struct nodo{
 char info;
 struct nodo *left,*right;
};
typedef struct nodo *ptrnodo;
int contanodo=0; // Para contar elementos
Listas duplamente 
encadeadas
●
char delete (ptrnodo *p) {
 char x;
 ptrnodo q,r;
 if (p==NULL) {
 printf("lista vazia\n");
 exit(-1);
 }
 x=(*p)->info;
 q=(*p)->left;
 r=(*p)->right;
 q->right=r;
 r->left=q;
 contanodo--;
 free(*p);
 *p=r;
 return (x);
}
Listas duplamente 
encadeadas
● Exercício para segunda feira, grupos de até 2 pessoas:
1 - Implementar e testar inclusão à esquerda de 
elemento na lista dupla.
2 – Implementar e testar inclusão à direita na lista 
dupla. Usem criatividade.
3 – Examinar a implementação de lista dupla em java no 
moodle para discussão na próxima aula
Listas duplamente 
encadeadas em Java
● Este não é um curso de Java, porém pretendemos dar 
uma idéia de como as estruturas de dados podem ser 
trabalhadas nessa linguagem.
● Java tem muitas semelhanças sintáticas com C, porém 
é, por natureza, uma linguagem orientada a objetos. 
Dessa forma, a declaração de variáveis e procedimentos 
ocorre em blocos, denominados classes, que podem ser 
instanciados dentro de outras classes.
● Para se manipular os dados de uma classe, utiliza-se os 
métodos, que são procedures daquela classe que se 
prestam a manipular tais dados de forma precisa.
Listas duplamente 
encadeadas em Java
● Os programas em Java são compilados por um 
compilador denominado javac.
● O programa a ser compilado deve estar em um arquivo 
do tipo ascii que tenha o nome da principal classe a ser 
compilada, seguido da terminação .java
● No nosso exemplo, a classe principal é DoublyLinkedList, 
que está em um arquivo chamado DoublyLinkedList.java
● Para compilá-lo faremos, na linha de comando:
 
 javac DoublyLinkedList.java
Listas duplamente 
encadeadas em Java
● O compilador Java é livre e gratuito, e pode ser baixado 
do site da Sun Microsystems – Sun Developer Network:
http://java.sun.com/javase/downloads
● Existe para diversas plataformas. Uma vez baixado, 
deve ser instalado. A versão que estamos usando é
jdk1.6.0_04 e para usar o meu compilador eu faço
 
 
 ~/jdk1.6.0_04/bin/javac DoublyLinkedList.java
Listas duplamente 
encadeadas em Java
● A compilação de nosso arquivo '.java' gerará um ou 
mais arquivos '.class'
● O nosso arquivo fonte (observar agora) tem duas 
classes, a saber DoublyLinkedList e Link
● São gerados, portanto, os arquivos 
DoublyLinkedList.class e Link.class
● Caso os arquivos não estivessem juntos, ao encontrar 
uma chamada à classe Link, o compilador procuraria no 
diretório um arquivo chamado Link.java, para proceder à 
compilação.
Listas duplamente 
encadeadas em Java
● Os arquivos do tipo '.class' estão codificados em uma 
linguagem virtual denominada 'bytecode', própria para 
ser interpretada por uma máquina virtual Java (JVM).
● Existem diversas versões, ou variações de JVM, porém 
as mais famosas e populares são aquelas que se 
encontram embutidas nos browsers da Internet, tais 
como o Microsoft Explorer ou o Mozilla Firefox.
● Dessa forma é que os programas feitos em Java podem 
ser rodados em sites que oferecem aplicações mais 
complexas (o do Banco do Brasil, por exemplo)
Listas duplamente 
encadeadas em Java
● Java tem dispositivos de segurança, para garantir que as 
aplicações que são rodadas no seu computador venham 
a trabalhar exclusivamente com os dados contidos no 
computador de onde originalmente vêm os programas 
em bytecode (ou javacode).
● Há também a possibilidade de programas serem 
projetados e rodados na sua máquina em Java. Para isso 
é distribuída uma JVM local (denominada 'java') e uma 
JVM local com capacidade gráfica (como a do browser), 
denominada 'appletviewer'.
Listas duplamente 
encadeadas em Java
● Java é, portanto, uma linguagem que é interpretada na 
ponta, e porisso é muito menos eficiente para 
aplicações locais do que C, por exemplo.
● Mas a comunidade Java vem trabalhando para que os 
processos de interpretação sejam os mais eficientes 
possível, de forma que em aplicações 'limitadas por 
dados' a relativa lentidão de Java é praticamente 
imperceptível.
Listas duplamente 
encadeadas em Java
● Uma classe Java que venha a ser executada pela JVM 
local deve ter um método publico 'main'que será o 
ponto de entrada da classe, e onde a aplicação se 
iniciará.
● Uma classe que venha a rodar em um browser ou pelo 
'appletviewer' deve ter um método público 'start', que 
será o ponto de início da aplicação.
Listas duplamente 
encadeadas em Java
● Segue-se o método 'main' de nosso exemplo:
 public static void main(String[] args) {
 DoublyLinkedList theList = new DoublyLinkedList();
 theList.insertFirst(22);
 theList.insertFirst(44);
 theList.insertLast(33);
 theList.insertLast(55);
 theList.displayForward();
 theList.displayBackward();
 theList.deleteFirst();
 theList.deleteLast();
 theList.deleteKey(11);
 theList.displayForward();
 theList.insertAfter(22, 77); // insert 77 after 22
 theList.insertAfter(33, 88); // insert 88 after 33
 theList.displayForward();
 }
Listas duplamente 
encadeadas em Java
● Na primeira linha está a definição do protocolo de 
chamada do método – é um método público, estático da 
classe, não retorna nada, chama-se 'main' e pode 
receber parâmetros em uma array do tipo 'String' 
denominada 'args'
● Apesar de ser um método da classe principal, o método 
main é independente, e tem o direito de definir suas 
instâncias de outras classes e até da sua própria. É isso 
que ele faz a seguir, criando a instância 'theList' da 
classe DoublyLinkedList:
DoublyLinkedList theList = new DoublyLinkedList();
Listas duplamente 
encadeadas em Java
● Então,a instância da classe referenciada por 'theList' é 
criada, seu método DoublyLinkedList() é executado e 
'main' poderá acessar os métodos (e dados) de theList
● Pelos nomes dá pra ter uma idéia do que cada um faz:
– theList.insertFirst
– theList.insertLast
– theList.displayForward
– theList.displayBackward
– theList.deleteFirst
– theList.deleteLast
– theList.deleteKey
– theList.insertAfter
Listas duplamente 
encadeadas em Java
● theList.insertFirst(22);
● theList.insertFirst(44);
● theList.insertLast(33);
● theList.insertLast(55);
● theList.displayForward();
● theList.displayBackward();
● theList.deleteFirst();
● theList.deleteLast();
● theList.deleteKey(11);
● theList.displayForward();
● theList.insertAfter(22, 77); // insert 77 after 22
● theList.insertAfter(33, 88); // insert 88 after 33
● theList.displayForward();
List (first to last): 44 22 33 55
List : 55 33 22 44
List (first to last): 22 33
List (first to last): 22 77 33 88
Listas duplamente 
encadeadas em Java
●A classe Link serve para definir a estrutura de cada nodo e 
os métodos para manipulá-lo:
class Link {
 public long dData; // data item
 public Link next; // next link in list
 public Link previous; // previous link in list
 public Link(long d) // set dData value
 {
 dData = d;
 }
 public void displayLink(){
 System.out.print(dData + " "); // print dData
 }
}
Listas duplamente 
encadeadas em Java
●Veja que quando uma instância da classe é criada é dado 
um valor para dData (pelo construtor 'public Link(long d)') 
mas os links 'next' e 'previous' ficam indeterminados:
class Link {
 public long dData; // data item
 public Link next; // next link in list
 public Link previous; // previous link in list
 public Link(long d) // set dData value
 {
 dData = d;
 }
 public void displayLink(){
 System.out.print(dData + " "); // print dData
 }
}
Listas duplamente 
encadeadas em Java
● Vamos agora à classe principal:
public class DoublyLinkedList {
 private Link first; 
 private Link last; 
 public DoublyLinkedList() {
 first = null; 
 last = null;
 }
● Ela contém duas instâncias de Link e inicializa ambas 
com nulos.
Listas duplamente 
encadeadas em Java
● O método empty é capaz de dizer se a lista está vazia:
 public boolean isEmpty(){
 return first == null;
 }
Listas duplamente 
encadeadas em Java
● O método 'insertFirst' começa criando um Link de nome 
'newLink', com o valor do dado passado em 'dd'
 public void insertFirst(long dd){
 Link newLink = new Link(dd); 
 if (isEmpty()) 
 last = newLink; 
 else
 first.previous = newLink; 
 newLink.next = first; 
 first = newLink; 
 }
Listas duplamente 
encadeadas em Java
● Veja o que acontece com a inserção de 22 e depois 44:
1 – no início first last
2 – insere 22 first last
 
 22
Listas duplamente 
encadeadas em Java
● Veja o que acontece com a inserção de 22 e depois 44:
 
3 – insere 44 first last
 
 22
 44
Listas duplamente 
encadeadas em Java
● O método 'insertLast' é bem semelhante ao método 
'insertFirst' 
 public void insertLast(long dd){
 Link newLink = new Link(dd); 
 if (isEmpty()) 
 first = newLink; 
 else{
 last.next = newLink; 
 newLink.previous = last;
 } 
 last = newLink; 
 }
Listas duplamente 
encadeadas em Java
● O método 'deleteFirst' ilustra a retirada de nodos, 
devolvendo uma referência para um Link: 
● Esse método não tem proteção contra link null e não 
devolve o link para a lista de espaço disponível
 public Link deleteFirst(){
 Link temp = first; 
 if (first.next == null) 
 last = null; 
 else
 first.next.previous = null; 
 first=first.next;
 return temp; 
 }
Listas duplamente 
encadeadas em Java
●
 public Link deleteKey(long key){
 Link current = first; 
 while (current.dData != key)
 { current = current.next;
 if (current == null)
 return null; // cannot find it
 }
 if (current == first) // found it; first item?
 first = current.next; 
 else
 current.previous.next = current.next;
 if (current == last) // last item?
 last = current.previous; 
 else // not last
 current.next.previous = current.previous;
 return current; // return value
 }
Listas duplamente 
encadeadas em Java
 public void displayForward() {
 System.out.print("List (first to last): ");
 Link current = first; // start at beginning
 while (current != null) // until end of list,
 {
 current.displayLink();
 current = current.next; // move to next link
 }
 System.out.println("");
 }