Prof. Frederico Brito Fernandes [email protected] Listas Encadeadas CONTEÚDO (1) Motivação (2) Definição (3) Operações (4) Comparando Vetores e Listas

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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ó



Inserir novo elemento na listaInserir novo elemento na lista

A B X C

A B C

p

A B C

p

Xq

p q



E

E

E

Remover elemento na listaRemover elemento na lista

A B C D

p

A B C

D

p

A B C



ExercícioExercício

• Escreva o pseudo-código para as operações de inserir e remover um elemento em lista duplamente encadeada


Documents

Prof. Frederico Brito Fernandes [email protected] Listas Encadeadas CONTEÚDO (1) Motivação (2) Definição (3) Operações (4) Comparando Vetores e Listas