Índice >
Lista >
Duplamente Encadeada
Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel, Maria Cristina e Rosane
Lista Duplamente Encadeada
Características
-
Listas foram percorridas do início ao final.
-
Ponteiro "anterior" necessário para muitas operações.
-
Em alguns casos pode-se desejar percorrer uma lista nas duas direções
indiferentemente.
-
Nestes casos, o gasto de memória imposto por um novo campo de ponteiro
pode ser justificado pela economia em não reprocessar a lista toda.
Type tpont = ^ trec;
trec = record
info:T;
esq, dir: tpont;
End;
Lista = tpont;
Var pont: Lista;
-
Como consequência, podemos realizar as operações de
inserção e eliminação à esquerda ou
à direita de um campo no interior de uma lista sem a necessidade
de ponteiros "anteriores".
Implementação de algumas oprações de lista
duplamente encadeada com alocação dinâmica
As operações 1 a 4 abaixo
são atômicas, isto é, elas realizam a reserva de espaço
(quando necessária) além do 'acerto dos ponteiros'. Pré-condição
para todas elas é que se conheça o ponteiro de um nó
ou de um vizinho. Além disso, elas não tratam casos especiais.
Assim, elas são operações de suporte para as inserções
e eliminações do TAD Lista, quando este é implementado
por lista duplamente encadeada. Tais operações não
ficariam disponíveis para o 'usuário' da TAD. Apenas o projetista
do tipo abstrato de dados as usa no desenvolvimento dos algoritmos genéricos
de inserção e eliminação (isto é, aqueles
que tratam todos os casos, além das condições de erro).
1) Inserção à direita de pont
Procedure ins_dir (pont: lista; x: T);
Var j: Lista;
Begin
new(j);
j^.info:=x;
j^.dir:=pont^.dir;
j^.dir^.esq:=j;
j^.esq:=pont;
pont^.dir:=j;
End;
2) Inserção à esquerda de pont
Procedure ins_esq (pont: Lista; x: T);
Var j: Lista;
Begin
new(j);
j^.info:=x;
j^.dir:=pont;
j^.esq:=pont^.esq;
j^.esq^.dir:=j;
pont^.esq:=j;
End;
3) Eliminação à direita de pont
Procedure elim_dir (pont: Lista);
Var j: Lista;
Begin
j:=pont^.dir;
pont^.dir:=j^.dir;
j^.dir^.esq:=pont;
dispose(j);
End;
4) Eliminação do próprio pont
Procedure elim (Var pont: Lista);
Begin
pont^.dir^.esq:=pont^.esq;
pont^.esq^.dir:=pont^.dir;
dispose(pont);
End;
5) Busca em uma lista circular
Funtion Busca_Dup_Ord(ptlista: Lista; x: T):Lista;
{ Lista Duplamente Encadeada Ordenada com sentinela apontado por ptlista }
Var pont, ultimo: Lista;
Begin
ultimo:=ptlista^.esq;
If x<=ultimo^.info then
Begin
pont:=ptlista;
While pont^.info < x do
pont:=pont^.dir;
Busca_Dup_Ord:=pont;
End
Else
Busca_Dup_Ord:=ptlista;
End;
-> Faça a Busca em lista duplamente encadeada simples (não circular).
Exercício
Lista Dinâmica