Uma lista duplamente encadeada se baseia em uma lsta que conterá elementos com 2 ponteiros. Dessa forma, através desses elementos, a lista poderá ser varrida tanto de uma forma crescente, como decrescente. Ou seja, esses elementos irá possuir apontadores para o elemento anterior e para o elemento seguinte, tornando-a mais fácil de manuseio e percorrimento. Para isso, a lista duplamente encadeada contará com o auxílio de um descritor que funcionará como um elemento universal que irá se encontrá fora da lista. Este terá a função de facilitar a orientação da lista, conseguindo indicar e manipular de maneira mais fácil os elementos de inicio e fim da lista, além de conter um indicador da quantidade de elementos que a lista possui.
De forma geral, suas funções continuam na mesma ideia que das demais listas, onde terá de criar a lista, inserir elemento, remover elemento e liberar a lista. Porém, a grande segredo estará nas funções de inserção e remoção de elemento, uma vez que agora 2 ponteiros estarão sendo trabalhados. Portando, segue abaixo as etapas a serem seguidas para a criação da lista duplamente encadeada:
Os elementos da lsta serão de extrema semeçhança dos demais elementos das outras listas, com a única diferença de 1 ponteiro a mais, o apontador para o elemento anterior, que terá a mesma forma do apontador prox. Criados por uma struct simples:
/*Struct - Elemento*/
struct elemento{
struct elemento *ant;
int valor;
struct elemento *prox;
}
typedef struct elemento Elem;
Perceba que sua decalaração de typedef se deu logo em seguida de sua criação, isso pelo fato de sua chamada ser necessáia na struct seguinte.
Como dito anteriormente, para o bom fucionamento dessa lista, ela deverá contar com o acompanhamento de um descritor que conterá apontadores para os elementos de inicio e de fim da lista, além de uma variável contadora que receberá a quantidade de elementos existentes na lista. Essa struct ficará logo em seguida a criação da struct de elementos, pois receberá parâmetros da struct de elemento. Logo, sua criação se dá por uma simples struct:
/*Struct - Descritor*/
struct descritor{
Elem *inicio;
int tamanho;
Elem *final;
}
Os apontadores para os elementos de inicio e fim, deverá ser exatamente dos mesmos tipos dos demais elementos, afinal, também será elementos a serem apontados. Logo, devem ser ponteiros do tipo Elem. Além disso, no momento de criação da lista no arquivo main.c, ela ao invés de ser declarada como Elem, será como Descritor, ou seja: Descritor *lista;
A função que realiza a criação da lista se faz diferente das demais, onde nas listas simples e encadeada, apenas retornava um valor NULL. Nesta lista, por se tratar de um descritor, devemos passar os valores iniciais do descritor e da lista nesta função. Portanto, deverá ser criada uma alocação dinâmica da lista sendo do tipo Descritor e passar os valores iniciais do descritor:
Descritor *criar(void){
Descritor *descritor;
descritor = (Descritor *)malloc(sizeof(Descritor));
descritor->final = NULL;
descritor->inicio = NULL;
descritor->tamanho = 0;
return descritor;
}
Dessa forma, o descritor que aponta para o elemento inicial e final da lista, recebe valores NULL já que inicialmente a lista não possui elemento algum. Assim como o tamanho da lista é zero.
Por se tratar de uma lista duplamente encadeada, deduz-se que a lista será automaticamente encadeada. Portanto, seus valores da função se tornam muito semelhantes a de lista ordenada. Além disso, 4 verificações devem ser realizadas:
O grande ponto aqui, é que além de definir o *prox de cada elemento, também indicaremos o *ant e se necessário, o faremos descritor->inicio ou descritor->final.
int inserir(Descritor *descritor, int valor){
Elem *novo;
novo = (Elem *)malloc(sizeof(Elem));
novo->num = valor;
novo->ant = NULL;
novo->prox = NULL;
//Caso 1 - Lista vazia
if(descritor->tamanho == 0){
descritor->inicio = novo;
descritor->final = novo;
}else{
//Caso 2 - Inserir Inicio
if(valor < descritor->inicio->num){
descritor->inicio->ant = novo;
novo->prox = descritor->inicio;
descritor->inicio = novo;
}else{
//Caso 3 - Inserir final
if(valor > descritor->final->num){
descritor->final->prox = novo;
novo->ant = descritor->final;
descritor->final = novo;
}else{
//Caso 4 - Inserir meio
Elem *aux;
aux = descritor->inicio->prox;
while(aux->num < valor){
aux = aux->prox;
}
novo->prox = aux;
novo->ant = aux->ant;
aux->ant->prox = novo;
aux->ant = novo;
}
}
}
(descritor->tamanho)++;
return 1;
}
Peceba que ao final da função, não pode-se esquecer de que como um novo elemento foi inserido, o tamanho da lista aumentou (descritor->tamanho).
A remoção de elementos da lista duplamente encadeada segue a mesma lógica das demais listas, onde dependendo da posição do elemento que for removido, os seus arredores devem ser realocaods de forma a manter a linhagem da lista. Diante disso, 5 verificações devem ser realizadas:
int remover(Descritor *descritor, int valor){
//Caso 1 - Lista vazia
if(descritor->tamanho == 0){
return 0;
}else{
Elem *aux;
//Caso 2 - Remover único
if(descritor->tamanho == 1 && descritor->inicio->num == valor){
aux = descritor->inicio;
free(aux);
descritor->inicio = NULL;
descritor->final = NULL;
}else{
//Caso 3 - Remover inicio
if(descritor->inicio->num == valor){
aux = descritor->inicio;
descritor->inicio = aux->prox;
descritor->inicio->ant = NULL;
free(aux);
}else{
//Caso 4 - Remover final
if(descritor->final->num == valor){
aux = descritor->final;
descritor->final = aux->ant;
descritor->final->prox = NULL;
free(aux);
}else{
//Caso 5 - Remover meio
aux = descritor->inicio->prox;
while(aux->num < valor){
aux = aux->prox;
}
if(aux->num == valor){
aux->ant->prox = aux->prox;
aux->prox->ant = aux->ant;
free(aux);
}else{
return 0;
}
}
}
}
}
(descritor->tamanho)--;
return 1;
}
Perceba que na última verificação, de remoção do inicio, foi também verificado se o aux->num == valor. Isso pel fato de que há a possibilidade de que o valor a ser removido, não se encontre na lista, fazendo com que elemento algum seja removido. Além disso, não pode-se esquecer que ao remover um elemento, o tamanho (descritor->tamanho) da lista deverá ser diminuido.
A exibição da lista é exatamente a mesma para qualquer outra lista, sempre exibindo o aux até que seja enontrado o NULL:
int liberarLista(Descritor **descritor){
if(descritor->tamanho == 0){
printf("\n LISTA VAZIA \n");
return 0;
}else{
Elem *aux;
printf("\n LISTA: ");
aux = descritor->inicio;
while(aux != NULL){
printf("- %d ",aux->num);
aux = aux->prox;
}
printf("- ");
return 1;
}
}
A lberação se faz muito semelhante a exibição, bastando percorrer a lista removendo o elemento aux até que toda a lista seja removida.
int liberarLista(Descritor **descritor){
if((*descritor)->tamanho == 0){
return 0;
}
Elem *aux;
aux = (*descritor)->inicio;
while((*descritor)->inicio != NULL){
(*descritor)->inicio = aux->prox;
free(aux);
aux = (*descritor)->inicio;
}
free(*descritor);
return 1;
}