Lista duplamente encadeada

Estrutura de Dados
Listas duplamente encadeadas

Prof. Luciano Z. Wolski

Lista duplamente encadeada
Cada elemento tem um ponteiro para o próximo elemento e um ponteiro para o elemento anterior.
Dado um elemento podemos acessar ambos elementos adjascentes: o próximo e o anterior.
Se tivermos um ponteiro para o último elemento da lista, podemos percorrer a lista em ordem inversa. Basta acessar o elemento anterior até chegar ao primeiro elemento da lista, que não tem elemento anterior, o ponteiro do elemento anterior vale NULL.

Estruturação Lista duplamente encadeada

P

/

...

/

Representação do nodo
Para exemplificar a implementação de listas duplamente encadeadas, vamos utilizar um exemplo simples onde vamos armazenar valores inteiros. typedef struct cel celula; struct cel{ int dado; struct cel *prox; struct cel *ant;
};

Inicializa p = malloc (sizeof (celula)); p->ant = NULL; p->prox = NULL;

Função de inserção /* Insere no inicio da lista*/
/* O ponteiro 'p' é a cabeça da lista*/ void insereInicio(int x, celula *p)
{
celula *nova, *q; nova = malloc (sizeof (celula)); nova->dado = x; nova->prox = p->prox; if (p->prox != NULL)
{
q = nova->prox; q->ant = nova;
}
p->prox = nova; nova->ant = p;
}

Função de inserção /* Insere no último da lista*/ void insereUltimo(int x, celula *p)
{
celula *q, *nova; nova = malloc (sizeof (celula)); nova->dado = x; q = p; while (q->prox != NULL) q = q->prox; q->prox = nova; nova->ant = q; nova->prox = NULL;
}

Função remove void buscaEremove (int y, celula *p)
{
celula *w, *q; w = p; q = p->prox; while (q != NULL && q->dado != y) { w = q; q = q->prox;
}
if (q != NULL) { w->prox = q->prox; q->prox->ant = w; free (q);
}
}

Função remove
Exemplo – Função para retirar um elemento da lista, um ponteiro apenas q aponta para o elemento no meio da lista:
- o anterior passa a apontar para o próximo: q->ant->prox = q->prox
- o próximo passa a apontar para o anterior: q->prox->ant = q->ant
Se q aponta para o último elemento
- não é