Aula 04 – 22/03
Listas Duplamente Encadeada – Listas Encadeada Circular – Lista
Duplamente Encadeada Circular
Continuação exercício aula 15/03
Lista duplamente encadeadas
• Lista encadeadas simples são unidirecionais, ou seja, a navegação na
lista começa de um ponto, o inicio e vai até o final.
• Lista duplamente escadeadas são bidirecionais, ou seja, a navegação
na lista pode ser feito do início até o fina ou do final até o início.
• Estrutura muito semelhante a lista encadeada simples porem temos
um novo ponteiro no nó que faz referencia ao nó anterior.
• A estratégia para manipular esse tipo de lista é ter um nó cabeça,
primeiro item da lista, e um nó cauda, último item da lista.
• O nó em uma lista duplamente encadeada possui dois ponteiros um
apontando para o primeiro nó anterior e outro apontando par ó
próximo nó, além do campo Dado.
Representação gráfica de uma lista com nós
Representação gráfica de inserção na lista
Representação gráfica de exclusão na lista
Operações em listas duplamente encadeadas
• Incluir, remover os nós em listas duplamente encadeadas requer mais
trabalho pois temos o nó cabeça e o nó cauda para serem atualizados.
• Percorres a lista, liberar os nós alocados são operações semelhantes
as listas simplesmente encadeadas.
Estrutura básica de um nó
PApontador = ^TItem;
TItem = record
Anterior: PApontador;
Valor: string;
Proximo: PApontador;
end;
Incluindo um novo nó
New( NoAuxiliar );
NoAuxiliar.Proximo:= LDEPrimeiroNo;
NoAuxiliar.Anterior:= nil;
NoAuxiliar.Valor:= InputBox( '', 'Digite o nome', '' );
if ( LDEPrimeiroNo <> nil ) and ( LDEPrimeiroNo.Anterior = nil ) then
LDEPrimeiroNo.Anterior:= NoAuxiliar;
LDEPrimeiroNo:= NoAuxiliar;
if ( LDEPrimeiroNo.Proximo = nil ) then
LDEUltimoNo:= NoAuxiliar;
Excluindo um nó
if
( LDEPrimeiroNo.Valor = ValorASerExcluido ) then
begin
NoAuxiliar:= LDEPrimeiroNo;
LDEPrimeiroNo:= LDEPrimeiroNo.Proximo;
if ( LDEPrimeiroNo <> nil ) then
LDEPrimeiroNo.Anterior:= nil;
if ( NoAuxiliar = LDEUltimoNo ) then
LDEUltimoNo:= nil;
Dispose( NoAuxiliar );
end else
Excluindo um nó – continuação
NoAuxiliar:= LDEPrimeiroNo;
while ( NoAuxiliar.Proximo <> nil ) do
begin
if ( NoAuxiliar.Proximo.Valor = ValorASerExcluido ) then
begin
NoAnterior:= NoAuxiliar;
NoAserExcluido:= NoAuxiliar.Proximo;
NoAnterior.Proximo:= NoAserExcluido.Proximo;
if ( NoAserExcluido = LDEUltimoNo ) then
LDEUltimoNo:= NoAserExcluido.Anterior
else
NoAnterior.Proximo.Anterior:= NoAnterior;
Dispose( NoAserExcluido );
Exit();
end;
NoAuxiliar:= NoAuxiliar.Proximo;
Percorrendo a lista – pelo último elemento
NoAuxiliar:= LDEUltimoNo;
while ( NoAuxiliar <> nil ) do
begin
ShowMessage(NoAuxiliar.Valor) ;
NoAuxiliar:= NoAuxiliar.Anterior;
end;
Observações
• Para identificar o final de uma lista duplamente encadeada utilizamos
o nó cauda que é uma variável especial. E continuamos a utilizar uma
variável especial para identificar o primeiro nó.
• Sempre que efetuarmos operações de inclusão ou exclusão de itens
da lista devemos nós certificar que estamos atualizando corretamente
o nó anterior e o nó atual do item.
Lista Encadeada Circular
• Possui a mesma estrutura de uma lista simplesmente encadeada
• Porem o último item da lista aponta para o primeiro item da lista
• Passamos a ter o nó atual ao invés do nó cabeça
Listas Duplamente Encadeada Circular
• Possui a mesma estrutura de uma lista duplamente encadeada.
• O nó anterior do primeiro elemento aponta para o último
• O próximo no do último elemento apontar para o primeiro elemento
da lista.
Exercícios
Download : aula04 – exercícios