Prof. Frederico Brito [email protected]
Listas Encadeadas Listas Encadeadas Listas Encadeadas Listas Encadeadas
CONTEÚDO
(1) Motivação(2) Definição(3) Operações(4) Comparando Vetores e Listas Ligadas(5) Lista Circular(6) Lista Duplamente Encadeada
Frederico Brito FernandesFrederico Brito Fernandes 2Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
• Prever o número máximo de elementos no vetor durante a codificação– dimensionar o vetor com um número absurdamente alto
• isto levaria a um desperdício de memória que é inaceitável em diversas aplicações
• E se tivermos mais de 700 reservas simultâneas?
...
0 1 2 3 699
Motivação...Motivação...
(1) Motivação
RESERVAS AÉREASRESERVAS AÉREAS
nome
e-ticket
nome
e-ticket
nome
e-ticket
nome
e-ticket
nome
e-ticket
Frederico Brito FernandesFrederico Brito Fernandes 3Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
SoluçãoSolução
• Algumas aplicações requerem a inserção/deleção constantes de elementos
• Solução: – Usar listas ligadas
Dado
Dado
Dado
Dado /
(1) Motivação
Frederico Brito FernandesFrederico Brito Fernandes 4Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
ListasListas
• Uma lista é uma estrutura de dados dinâmica. • O número de nós de uma lista pode variar
consideravelmente à medida que elementos são inseridos ou removidos.
• A natureza dinâmica de uma lista pode ser comparada à natureza estática de um vetor, cujo tamanho permanece constante.
(2) Definição
Frederico Brito FernandesFrederico Brito Fernandes 5Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Lista Simplesmente EncadeadaLista Simplesmente Encadeada
• É uma estrutura de dados concreta que consiste de uma seqüência de nós
• Cada nó armazena– O conteúdo do elemento– Uma ligação para o próximo nó
próximodado
nó
A B C D
(2) Definição
Frederico Brito FernandesFrederico Brito Fernandes 6Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
O tipo NóO tipo Nó
• Possui os campos de informação• Possui um campo de ligação com o próximo elemento
do tipo Nó• As operações sobre nó são:
– Atualiza informação
– Atualiza próximo
– Recupera informação
– Recupera próximo próximodado nó
(2) Definição
Frederico Brito FernandesFrederico Brito Fernandes 7Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Exemplo: Reserva AéreaExemplo: Reserva Aérea
• Ex:#include <stdlib.h>
#include <stdio.h>
typedef struct eReserva {
char nome[60];
char e_ticket[20];
struct eReserva *prox;
} tReserva;
main(){
tReserva *cabeca, *segundoNo, *terceiroNo;
cabeca = (tReserva *) malloc(sizeof(tReserva));
cabeca->prox = NULL;
segundoNo = (tReserva *) malloc(sizeof(tReserva));
cabeca->prox = segundoNo;
segundoNo->prox = NULL;
terceiroNo = (tReserva *) malloc(sizeof(tReserva));
segundoNo->prox = aux;
terceiroNo->prox = NULL;
}
nome e-ticket prox nome e-ticket prox
cabecacabeca
nome e-ticket NULL
segundoNosegundoNo
struct eReservastruct eReserva
nome e-ticket NULL
terceiroNoterceiroNo
tReservatReserva
(2) Definição
Frederico Brito FernandesFrederico Brito Fernandes 8Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
O tipo Lista EncadeadaO tipo Lista Encadeada
• Possui um campo que referencia o início da lista (também chamado de cabeça da lista)
• Possui um campo que representa o número total de nós da lista.
• As operações sobre lista encadeada são:– Inserir nó no início
– Inserir nó no fim
– Inserir nó no meio
– Remover nó no início
– Remover nó no fim
– Remover nó no meio
(2) Definição
Frederico Brito FernandesFrederico Brito Fernandes 9Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Inserir nó no início da listaInserir nó no início da lista
1. Aloque um novo nó
2. Faça o campo próximo do novo nó apontar para o nó cabeça da lista
3. Atualize o campo que aponta para a cabeça para apontar para o novo nó
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 10Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Inserir um nó no fim da listaInserir um nó no fim da lista
1. Localize a cauda da lista
2. Aloque um novo nó3. Faça o campo próximo
do novo nó apontar para null
4. Faça o campo próximo do nó cauda apontar para o novo nó
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 11Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Inserir um nó no meio da listaInserir um nó no meio da lista
1. Use uma variável auxiliar do tipo Nó para localizar o nó “V” após o qual se deseja inserir o novo nó
2. Aloque um novo nó
3. Faça o campo próximo do novo nó apontar para o nó apontado pelo campo próximo do nó “V”
4. Faça o campo próximo do nó “V” apontar para o novo nó
V
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 12Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Remover um nó da cabeça da listaRemover um nó da cabeça da lista
1. Use uma variável auxiliar do tipo Nó para apontar para a cabeça da lista
2. Atualize o campo que aponta para a cabeça da lista para apontar para o próximo nó na lista
3. Desaloque o nó da variável auxiliar.
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 13Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
1. Use uma variável auxiliar do tipo Nó para localizar o penúltimo nó da lista
2. Use uma outra variável auxiliar do tipo Nó para apontar para a cauda da lista
3. Coloque o campo próximo do penúltimo nó da lista para null
4. Desaloque o último nó
Remover um nó da cauda da listaRemover um nó da cauda da lista
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 14Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Remover um nó do meio da listaRemover um nó do meio da lista
1. Use uma variável auxiliar do tipo Nó para localizar o nó anterior “V” ao nó a ser removido da lista
2. Use uma outra variável auxiliar do tipo Nó para apontar para o nó “W” a ser removido da lista
3. Faça o campo próximo do nó “V” apontar para o nó apontado pelo campo próximo do nó a ser removido da lista
4. Desaloque o nó “W”
V W
(3) Operações
Frederico Brito FernandesFrederico Brito Fernandes 15Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Forma de acessoForma de acesso
• Um item é acessado numa lista encadeada, percorrendo-se a lista a partir do início, porque não existe relação entre a posição de memória ocupada por um elemento de uma lista e sua posição dentro dessa lista.
• Um item é acessado num vetor através de uma única operação (usando o índice)
Dado
Dado
Dado
Dado /
Dado Dado Dado Dado0 1 2 3
(4) Comparando vetores e listas ligadas
Frederico Brito FernandesFrederico Brito Fernandes 16Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
FlexibilidadeFlexibilidade
• Por outro lado o vetor não é uma estrutura de dados muito flexível– É preciso dimensioná-lo com um número máximo de
elementos
– Se o número de elementos que precisarmos armazenar exceder a dimensão do vetor, teremos um problema
– Se o número de elementos que precisarmos armazenar no vetor for muito inferior à sua dimensão, estaremos subutilizando o espaço de memória reservado
– Se precisarmos retirar ou inserir um elemento no meio do vetor, teremos de deslocar alguns elementos do vetor
(4) Comparando vetores e listas ligadas
Frederico Brito FernandesFrederico Brito Fernandes 17Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Lista CircularLista Circular
• O campo próximo do último nó aponta de volta para o primeiro nó, em vez de apontar para null.
• Não tem um "primeiro" ou um "último" nó natural. É preciso estabelecer um primeiro e um último nó por convenção.– Uma variável auxiliar do tipo Nó aponta para o último nó e o nó seguinte
se torna o primeiro nó
– Se a variável auxiliar do tipo Nó apontar para null então a lista circular está vazia
(5) Lista Circular
Dado
Dado
Dado
Dado
Frederico Brito FernandesFrederico Brito Fernandes 18Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Lista Circular - LimitaçõesLista Circular - Limitações
• Não se pode atravessar uma lista desse tipo no sentido contrário
• Para eliminar um nó de uma lista circularmente ligada, é preciso usar pelo menos uma variável auxiliar do tipo Nó– A solução é usar Lista Duplamente Encadeada
(5) Lista Circular
Frederico Brito FernandesFrederico Brito Fernandes 19Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Lista Duplamente EncadeadaLista Duplamente Encadeada
• O encadeamento simples também dificulta a retirada de um elemento da lista – Temos que percorrer a lista, elemento por elemento, para
encontrarmos o elemento anterior àquele que queremos eliminar.
• A solução é usar uma lista duplamente encadeada
(6) Lista Duplamente Encadeada
Dado
Dado
Dado
Dado
Frederico Brito FernandesFrederico Brito Fernandes 20Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Lista Duplamente EncadeadaLista Duplamente Encadeada
• Cada nó armazena :– O conteúdo do elemento
– A ligação para o próximo nó
– A ligação para o nó anterior
ant prox
dado
nó
(6) Lista Duplamente Encadeada
Frederico Brito FernandesFrederico Brito Fernandes 21Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Inserir novo elemento na listaInserir novo elemento na lista
A B X C
A B C
p
A B C
p
Xq
p q
(6) Lista Duplamente Encadeada
Frederico Brito FernandesFrederico Brito Fernandes 22Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
E
E
E
Remover elemento na listaRemover elemento na lista
A B C D
p
A B C
D
p
A B C
(6) Lista Duplamente Encadeada
Frederico Brito FernandesFrederico Brito Fernandes 23Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
ExercícioExercício
• Escreva o pseudo-código para as operações de inserir e remover um elemento em lista duplamente encadeada
(6) Lista Duplamente Encadeada