Lista Duplamente Encadeada

Como o nome sugere, são compostas de nós ligados por dois ponteiros. Cada nó de uma lista duplamente encadeada consiste de três partes: alem dos dados e do ponteiro próximo (next), o nó passa a incorporar um ponteiro para o elemento anterior (prior).

Ao avaliar o exemplo de lista ligada, pode-se perceber a dependência do mecanismo de inserir e excluir de uma busca que irá percorrer a toda a lista e a necessidade de durante toda a procura manter a informação do elemento anterior.

A melhoria para este tipo de situação se faz com o nó apontando também para o membro anterior da lista, apesar do aumento do tamanho do nó de informação, a vantagem aparece em termos de flexibilidade ao poder percorrer a lista em ambas as direções, ao somar a capacidade de percorrer a lista a partir de seus extremos, passa a incluir mais um apontador para o fim (end) da lista, junto do inicio (start).

Null

<

Prior

<

Prior

<

End

Info

Info

Info

Start

>

Next

>

Next

>

Null

O resultado das operações para este tipo de lista se torna mais intuitivo no momento de passar o conceito para o código do programa, tanto para inserir, como para remover, analisando uma inserção entre dois elementos:

a)      Encontrar a posição da lista para incluir o novo nó.

b)      Novo nó atualiza os endereços de seus apontadores, usando os dados do nó que utiliza a posição a ser ocupada na lista.

c)       Inclui o novo nó ao mudar o apontamento de próximo do nó anterior e o apontamento de anterior do próximo nó.

  

                Mesma situação se repete para excluir, ao inverter a sequencia de operação.

                Abaixo segue os Detalhes para as três situações que podem ocorrer quando se insere um item na lista duplamente encadeada:

1.                   Item pode se tornar o primeiro da lista;

Info
			Info			Info
	Start	>		Next	>		Nulo
			Nulo		<	Prior		<	End

·         Ponteiro anterior do primeiro da lista indica o novo item.

·         Novo item copia o endereço de próximo que está em Start.

·         Novo item coloca nulo para anterior.

·         Start aponta para o novo item.

Info

Start

next

Nulo

Info

Info

Next

Nulo

Prior

Prior

End

2.       Inserir entre dois outros itens;

Info

Info

Info

Start

Next

Nulo

Nulo

Prior

End

·         Novo item copia o endereço de próximo que está no item anterior.

·         Novo item copia o endereço de anterior que está no item próximo.

·         Item próximo atualiza o endereço anterior para o novo item.

·         Item anterior atualiza o endereço próximo para o novo item.

Info

Next

Prior

Info

Info

Start

Next

Nulo

Nulo

Prior

End

3.       Ser o ultimo item da lista;

		Info			Info					Info
Start			Next			Nulo
		Nulo			Prior			End

·         Troca o Nulo pelo endereço do novo item no ultimo item da lista.

·         Novo item atualiza endereço de anterior para o ultimo da lista.

·          Novo item atualiza endereço de próximo para Nulo.

·         End aponta para o novo item.

		Info			Info			Info
Start			Next			Next			Nulo
		Nulo			Prior			Prior			End

Por fim, mais três situações podem ocorrer quando se remove um item na lista duplamente encadeada, repare que como reflexo da inserção, a sequência de operação se inverte:

1.       Excluir o primeiro da lista;

		Info			Info			Info
Start			Next			Next			Nulo
		Nulo			Prior			Prior			End

·         Copia o endereço de próximo no primeiro item para Start.

·         Coloca endereço anterior nulo para o novo primeiro item.

					Info			Info
Start						Next			Nulo
					Nulo			Prior			End

2.       Elimina numa posição intermediaria;

		Info			Info			Info
Start			Next			Next			Nulo
		Nulo			Prior			Prior			End

·         Copia no item anterior ao que vai ser excluído o endereço de próximo.

·         Copia no item próximo ao que vai ser excluído o endereço de anterior.

		Info						Info
Start			Next						Nulo
		Nulo						Prior			End

3.       Excluir o ultimo item;

		Info			Info			Info
Start			Next			Next			Nulo
		Nulo			Prior			Prior			End

·         Troca o endereço que aponta para o item a ser excluído por nulo.

·         Copia o endereço de anterior do item a ser excluído em End.

		Info			Info
Start	>		Next			Nulo
		Nulo			Prior			End

Um modelo simples e didático de código em linguagem C para uma lista duplamente encadeada está incluído na próxima postagem “Exemplo de lista duplamente encadeada” e serve como complemento prático mostrando a programação completa das rotinas para inserir, excluir e percorrer.