LISTAS DUPLAMENTE ENCADEADAS
Listas Encadeadas: Características
• Listas encadeadas são percorridas do início ao final.
• E se for necessário percorrer uma lista nas duas
direções indiferentemente?
– Ex.: Ponteiro para o “nó anterior" necessário para muitas
operações (busca, inserção, ...)
• Utilização de um ponteiro extra em cada nó, que
indica o ponteiro anterior ao nó
• O gasto de memória imposto por um novo campo de
ponteiro é justificado pela facilidade no processamento de toda lista
Implementação de Listas com
Ponteiros
• Os nós (itens) da lista são registros com dois ponteiros,
para guardar o endereço do seu sucessor e antecessor
Antecessor (esq)
x1
x1
x2
x3
...
Sucessor (dir)
xn
Implementação da Lista Duplamente
Encadeada
type
Ponteiro
TipoItem
= ^TipoNo;
= record
chave: TipoChave;
{outros componentes desejadas...}
end;
TipoNo
= record
Item: TipoItem;
Ant, Prox: Ponteiro;
end;
TipoListaDupla = record
Primeiro: Ponteiro;
Último : Ponteiro;
end;
var L: TipoListaDupla;
Implementação: Inicia_Lista e
Lista_Vazia
procedure Inicia_Lista (var LD: TipoListaDupla);
begin
New (LD.Primeiro);
LD.Último := LD.Primeiro;
LD.Primeiro^.Prox := nil;{LD.Último^.Prox := nil}
LD.Primeiro^.Ant := nil;{LD.Último^.Ant := nil}
end;
function Lista_Vazia (var LD: TipoListaDupla): boolean;
begin
Lista_Vazia := LD.Último = LD.Primeiro;
end;
Implementação: Imprime_Lista
procedure Imprime_Lista(var LD: TipoLista);
var Aux: Ponteiro;
begin
Aux:= LD.Primeiro^.Prox;
while (Aux <> nil) do
begin
writeln (‘Chave: ‘, Aux^.Item.Chave);
Aux := Aux^.Dir;
end;
end;
Implementação: Imprime_Lista
procedure Imprime_Lista(var LD: TipoLista);
var Aux: Ponteiro;
begin
Aux:= LD.Ultimo;
while (Aux <> LD.Primeiro) do
begin
writeln (‘Chave: ‘, Aux^.Item.Chave);
Aux := Aux^.Esq;
end;
end;
Inserção de um Nó
• Duas situações: Inserção à Direita de um
nó e Inserção à Esquerda de um Nó
• Caso 1: Inserção à Direita
– Procedimento recebe o nó à esquerda do qual se
deseja inserir (o item vai ser inserido à
direita desse nó passado como parâmetro)
– Cria-se um novo nó
– Ponteiro à direita do novo nó recebe o ponteiro
à direita do nó passado como parâmetro
– Ponteiro à esquerda do novo nó recebe o ponteiro
passado como parâmetro
– Ponteiro à direita do nó passado como parâmetro
recebe o novo nó
– Ponteiro à esquerda do nó à direita do novo nó
recebe o novo nó
Inserção do Nó X à direita de P em
Lista Duplamente Encadeada
P
Último
Primeiro
cabeça
X
Inserção à direita de p
procedure Insere_a_Direita (p:Ponteiro; x:TipoItem; var
LD:TipoListaDupla; var flag: boolean);
{O nó será inserido à direita do ponteiro p passado como
parâmetro}
var pNovo: Ponteiro;
begin
new(pNovo);
if pNovo = nil then flag := FALSE
else begin
pNovo^.Item.chave := x.chave;
pNovo^.Prox := p^.Prox;
pNovo^.Ant := p;
p^.Prox := pNovo;
{Caso em que p aponta para o último
if pNovo^.prox = nil then
elemento, então o novo elemento será
LD.Ultimo := pNovo
último da lista}
else
pNovo^.Prox^.Esq := pNovo;
flag := TRUE;
end
end;
o
Inserção de um Nó
• Caso 2: Inserção à Esquerda
– Procedimento recebe o nó à direita do qual se
deseja inserir (o item vai ser inserido à
esquerda desse nó passado como parâmetro)
– Cria-se um novo nó
– Ponteiro à esquerda do novo nó recebe o ponteiro
à esquerda do nó passado como parâmetro
– Ponteiro à direita do novo nó recebe o ponteiro
passado como parâmetro
– Ponteiro à esquerda do nó passado como parâmetro
recebe o novo nó
– Ponteiro à direita do nó à esquerda do novo nó
recebe o novo nó
Inserção do Nó X à esquerda de P em
Lista Duplamente Encadeada
P
Primeiro
Último
cabeça
X
Inserção à esquerda de p
procedure Insere_a_Esquerda (p:Ponteiro; x:TipoItem; var
LD:TipoLista; var flag: boolean);
{ A inserção é feita à esquerda do ponteiro p }
var pNovo: Ponteiro;
begin
new(pNovo);
if pNovo = nil or p = LD.Primeiro then flag := FALSE
else begin
pNovo^.Item := x;
pNovo^.Prox := p;
pNovo^.Ant := p^.Ant;
p^.Ant := pNovo;
pNovo^.Esq^.Dir := pNovo;
flag := TRUE;
end
end;
Remoção de um Nó
• Também duas situações: Remoção à Direita
de um nó e Remoção à Esquerda de um Nó
• Caso 1: Remoção à Direita
– Procedimento recebe o nó à esquerda do qual se
deseja remover(o item vai ser removido à direita
desse nó passado como parâmetro)
– Cria-se um auxiliar para apontar para o nó à
direita
– Ponteiro à direita do nó passado como parâmetro
aponta para a direita do nó auxiliar
– Ponteiro à esquerda do nó à esquerda do nó
auxiliar aponta para o nó à esquerda do nó
auxiliar
– Retorna o ítem que está no nó auxiliar
– Apaga-se o nó auxiliar
Remoção do Nó X à direita de P em
Lista Duplamente Encadeada
P
Primeiro
cabeça
X
Último
Remoção à direita de p
procedure Remove_a_Direita (p:Ponteiro; x:TipoItem; var
LD:TipoListaDupla; var flag: boolean);
{O nó será removido à direita do ponteiro p passado como parâmetro}
var aux: Ponteiro;
begin
if Vazia(LD) or LD^.prox=nil then flag := false
else begin
aux := p^.prox;
x := aux^.Item;
p^.prox := aux^.Prox;
{Caso em que aux aponta para o último
if aux^.prox = nil then
elemento, então o apontador para última
LD.Ultimo := p
posição será P}
else
aux^.Prox^.Ant := aux^.Ant;
Dispose (aux);
flag := TRUE;
end
end;
Remoção à Esquerda de um Nó
• Caso 2: Remoção à Esquerda
– Procedimento recebe o nó à direita do qual se
deseja remover(o item vai ser removido à
esquerda desse nó passado como parâmetro)
– Cria-se um auxiliar para apontar para o nó à
esquerda
– Ponteiro à esquerda do nó passado como parâmetro
aponta para a esquerda do nó auxiliar
– Ponteiro à direita do nó à direita do nó
auxiliar aponta para o nó à direita do nó
auxiliar
– Retorna o ítem que está no nó auxiliar
– Apaga-se o nó auxiliar
Remoção do Nó X à Esquerda de P em
Lista Duplamente Encadeada
X
Primeiro
cabeça
P
Último
Remoção à direita de p
procedure Remove_a_Esquerda (p:Ponteiro; x:TipoItem; var
LD:TipoListaDupla; var flag: boolean);
{O nó será removido à esquerda do ponteiro p passado como parâmetro}
var aux: Ponteiro;
begin
if Vazia(LD) or p=LD.Primeiro then flag := false
else begin
aux := p^.ant;
x := aux^.Item;
p^.ant := aux^.ant;
aux^.Ant^.Prox := aux^.Prox;
Dispose (aux);
flag := TRUE;
end
end;