Aula Listas Escadeadas - Estruturas de Dados

Listas Duplamente
Encadeadas

Algoritmos e Estruturas de Dados

1

Introdução
A estrutura de lista encadeada vista até agora caracterizase por formar um encadeamento simples entre os elementos: cada elemento armazena um ponteiro para o próximo elemento da lista.
Desta forma, não temos como percorrer eficientemente os elementos em ordem inversa, isto é, do final para o início da lista.
O encadeamento simples também dificulta a retirada de um elemento da lista.
Mesmo se tivermos o ponteiro do elemento que desejamos retirar, temos que percorrer a lista, elemento por elemento, para encontrarmos o elemento anterior.
Algoritmos e Estruturas de Dados

2

Definição

Para solucionar esses problemas, podemos formar o que chamamos de listas duplamente encadeadas.
Cada elemento tem um ponteiro para o próximo elemento e um ponteiro para o elemento anterior.
Desta forma, dado um elemento, podemos acessar ambos os elementos adjacentes: o próximo e o anterior.

Algoritmos e Estruturas de Dados

3

Definição
Se tivermos um ponteiro para o último elemento da lista, podemos percorrer a lista em ordem inversa, bastando acessar continuamente o elemento anterior, até alcançar o primeiro elemento da lista, que não tem elemento anterior
(o ponteiro do elemento anterior vale NULL).

Algoritmos e Estruturas de Dados

4

Estrutura de uma lista duplamente encadeada O nó da lista pode ser representado pela estrutura abaixo e a lista pode ser representada utilizando o ponteiro para o primeiro nó. struct lista2 { int info; struct lista2* ant; struct lista2* prox;
}TLista2;
typedef TLista2 *PLista2;

Algoritmos e Estruturas de Dados

5

Inserção em lista duplamente encadeada
O código a seguir mostra uma possível implementação da função que insere novos elementos no início da lista.
PLista2 insere (PLista2 l, int v) {
PLista2 novo = (PLista2) malloc(sizeof(TLista2)); novo->info = v; novo->prox = l; novo->ant = NULL; if (l