[Curso de AeED - Aula 13] - Listas lineares - variações


Esta aula é uma continuação da aula anterior. Ela tratará de uma variação das listas encadeadas. A sua implementação e lógica é similar, porém possui alguns detalhes que a diferenciam.

  1. Listas duplamente encadeadas
A estrutura de lista encadeada vista nas seções anteriores caracteriza-se 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.
Para solucionar esses problemas, 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. Desta forma, dado um elemento, podemos acessar ambos os elementos adjacentes: o próximo e o anterior. 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).
Figura 1 - Representação de uma lista duplamente encadeada

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 lista2 {
int info;
struct lista2* ant;
struct lista2* prox;
};
typedef struct Lista2 Lista2;

Com base nas definições acima, exemplificamos a seguir a implementação de algumas funções que manipulam listas duplamente encadeadas.

1.1- Função de inserção

O código a seguir mostra uma possível implementação da função que insere novos elementos no início da lista. Após a alocação do novo elemento, a função acertar o duplo encadeamento.
Lista2* insere (Lista2* l, int v) {
Lista2* novo = (Lista2*) malloc(sizeof(Lista2));
novo->info = v;
novo->prox = l;
novo->ant = NULL;
if (l != NULL) l->ant = novo;
return novo;
}

Nessa função, o novo elemento é encadeado no início da lista. Assim, ele tem como próximo elemento o antigo primeiro elemento da lista e como anterior o valor NULL. A seguir, a função testa se a lista não era vazia, pois, neste caso, o elemento anterior do então primeiro elemento passa a ser o novo elemento. De qualquer forma, o novo elemento passa a ser o primeiro da lista, e deve ser retornado como valor da lista atualizada. A Figura a seguir ilustra a operação de inserção de um novo elemento no início da lista.


1.2- Função de busca
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 elemento. Caso o elemento não seja encontrado na lista, o valor retornado é NULL.
Lista2* busca (Lista2* l, int v) {
Lista2* p;
for (p=l; p!=NULL; p=p->prox)
if (p->info == v)
return p;
return NULL;
}


1.3- Função que retira um elemento da lista

A função de remoção fica mais complicada, pois temos que acertar o encadeamento duplo. Em contrapartida, podemos retirar um elemento da lista conhecendo apenas o ponteiro para esse elemento. Desta forma, podemos usar a função de busca acima para localizar o elemento e em seguida acertar o encadeamento, liberando o elemento ao final.
Se p representa o ponteiro do elemento que desejamos retirar, para acertar o encadeamento devemos conceitualmente fazer:
p->ant->prox = p->prox;
p->prox->ant = p->ant;
isto é, o anterior passa a apontar para o próximo e o próximo passa a apontar para o anterior. Quando p apontar para um elemento no meio da lista, as duas atribuições acima são suficientes para efetivamente acertar o encadeamento da lista. No entanto, se p for um elemento no extremo da lista, devemos considerar as condições de contorno. Se p for o primeiro, não podemos escrever p->ant->prox, pois p->ant é NULL; além disso, temos que atualizar o valor da lista, pois o primeiro elemento será removido.

Uma implementação da função para retirar um elemento é mostrada a seguir:

/* função retira: retira elemento da lista */
Lista2* retira (Lista2* l, int v) {
Lista2* p = busca(l,v);
if (p == NULL)
return l;
if (l == p)
l = p->prox;
else
p->ant->prox = p->prox;
if (p->prox != NULL)
p->prox->ant = p->ant;
free(p);
return l;
}


2- Lista circular duplamente encadeada

Uma lista circular também pode ser construída com encadeamento duplo. Neste caso, o que seria o último elemento da lista passa ter como próximo o primeiro elemento, que, por sua vez, passa a ter o último como anterior. Com essa construção podemos percorrer a lista nos dois sentidos, a partir de um ponteiro para um elemento qualquer. Abaixo, ilustramos o código para imprimir a lista no sentido reverso, isto é, percorrendo o encadeamento dos elementos anteriores.

void imprime_circular_rev (Lista2* l) {
Lista2* p = l;  
if (p) {    
do {
printf("%d\n", p->info);
p = p->ant;
}while (p != l);

}
[Curso de AeED - Aula 13] - Listas lineares - variações [Curso de AeED - Aula 13] - Listas lineares - variações Reviewed by Vinicius dos Santos on 10:42:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!