Listas Duplamente Encadeadas C++

Listas duplamente encadeadas

Listas duplamente encadeadas
A estrutura de lista encadeada vista nos slides anteriores 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, pois, dado um determinado elemento, não temos como acessar diretamente seu elemento anterior.

Listas duplamente encadeadas
Para solucionar esse problema, podemos formar o que chamamos de listas duplamente encadeadas. Nelas, cada elemento tem um ponteiro para o próximo elemento e um ponteiro para o elemento anterior.

Lista duplamente encadeada

Lista circular duplamente encadeada

Listas duplamente encadeadas
Para exemplificar a implementação de listas duplamente encadeadas vamos novamente considerar o exemplo simples no qual queremos armazenar valores inteiros na lista. O nó da lista pode ser representado pela estrutura abaixo e a lista pode ser representada através do ponteiro para o primeiro nó. struct node { int info; struct node * ant; struct node * prox;
};
typedef struct node Node;

Listas duplamente encadeadas
Inclusão de novo nó
O código a seguir mostra uma possível implementação para inserção de elementos no início da lista:
/* inserção no início */
Node* insere (Node* l, int v)
{
Node* novo = (Node*) malloc(sizeof(Node)); novo->info = v; novo->prox = l; novo->ant = NULL;
/* verifica se lista não está vazia */ if (l != NULL) l->ant = novo; return novo;
}

Listas duplamente encadeadas
Busca de um nó
A função de busca recebe a informação referente ao elemento que queremos buscar e tem como valor de retorno o ponteiro do nó da lista que representa o