Dando continuidade ao nosso Curso de Programação C e ao estudo da estrutura de dados dinâmica do tipo lista encadeada, vamos aprender nesta aula como construir uma lista duplamente encadeada.
As estruturas dinâmicas que vimos até o momento possuía apenas um ponteiro conectando cada nó, isso não significa que tem que ser sempre assim. Se o problema exigir podem ser criados outros ponteiros. Isso nos leva a outra estrutura de dados dinâmica clássica, a Lista Duplamente Encadeada.
Como o nome sugere, é uma lista encadeada como a que conhecemos nas aulas anteriores. A diferença reside no fato de que cada nó possui dois ponteiros, um apontando para o próximo nó e outro apontando para o nó anterior.
O fato de cada nó possuir dois ponteiros possui ao menos duas implicações importantes que exigem nossa atenção. O primeiro é que agora podemos percorrer a lista nos dois sentidos, não apenas do início para o fim, mas também do fim para o início. O segundo é que em cada operação realizada na lista precisamos atualizar dois ponteiros, o ponteiro que aponta para o próximo nó e o ponteiro que aponta para o nó anterior.
O nó representado na figura acima pode ser criado da seguinte forma:
/*
Estrutura nó para a lista duplamente encadeada
*/
typedef struct no{
int valor;
struct no *proximo;
struct no *anterior;
}No;
Como mencionado, a partir de agora cada alteração na lista precisa atualizar os dois ponteiros de cada nó envolvido na operação. A seguir é apresentado um procedimento para inserir um novo nó no início da lista dupla. Observe que os dois ponteiros são atualizados de acordo com a operação realizada, neste caso uma inserção no início.
/*
procedimento para inserir um novo nó no início da lista
*/
void inserir_no_inicio(No **lista, int num){
No *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
// próximo do novo nó aponta para o início da lista
novo->proximo = *lista;
// o anterior é nulo pois é o primeiro nó
novo->anterior = NULL;
// se a lista não estiver vazia, o anterior do primeiro nó aponta para o novo nó
if(*lista)
(*lista)->anterior = novo;
// o novo nó passa a ser o início da lista (o primeiro nó da lista)
*lista = novo;
}
else
printf("Erro ao alocar memoria!\n");
}
A seguir temos um código completo de exemplo para manipular uma lista duplamente encadeada com as seguintes operações:
– inserir no início
– inserir no meio
– inserir no fim
– inserir ordenado
– remover
– buscar
– imprimir do início ao fim
– imprimir do fim ao início
Uma dica para ajudar na compreensão de cada uma destas operações é desenhar uma lista no papel e simular as operações. Por exemplo, se for inserir de forma ordenada, desenhe uma lista com alguns elementos e um novo nó a ser inserido de forma ordenada. Agora rastreie o procedimento de inserção ordenada, fazendo no papel o que cada linha de código faz. Isso ajuda a entender a manipulação dos ponteiros.
Código de exemplo completo em C para uma Lista Duplamente Encadeada
/*
Aula 257: Lista Duplamente Encadeada
Código escrito por Wagner Gaspar
Agosto de 2021
*/
typedef struct no{
int valor;
struct no *proximo;
struct no *anterior;
}No;
// procedimento para inserir no início
void inserir_no_inicio(No **lista, int num){
No *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
novo->proximo = *lista;
novo->anterior = NULL;
if(*lista)
(*lista)->anterior = novo;
*lista = novo;
}
else
printf("Erro ao alocar memoria!\n");
}
// procedimento para inserir no fim
void inserir_no_fim(No **lista, int num){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
novo->proximo = NULL;
// é o primeiro?
if(*lista == NULL){
*lista = novo;
novo->anterior = NULL;
}
else{
aux = *lista;
while(aux->proximo)
aux = aux->proximo;
aux->proximo = novo;
novo->anterior = aux;
}
}
else
printf("Erro ao alocar memoria!\n");
}
// procedimento para inserir no meio
void inserir_no_meio(No **lista, int num, int ant){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
// é o primeiro?
if(*lista == NULL){
novo->proximo = NULL;
novo->anterior = NULL;
*lista = novo;
}
else{
aux = *lista;
while(aux->valor != ant && aux->proximo)
aux = aux->proximo;
novo->proximo = aux->proximo;
if(aux->proximo)
aux->proximo->anterior = novo;
novo->anterior = aux;
aux->proximo = novo;
}
}
else
printf("Erro ao alocar memoria!\n");
}
void inserir_ordenado(No **lista, int num){
No *aux, *novo = malloc(sizeof(No));
if(novo){
novo->valor = num;
// a lista está vazia?
if(*lista == NULL){
novo->proximo = NULL;
novo->anterior = NULL;
*lista = novo;
} // é o menor?
else if(novo->valor < (*lista)->valor){
novo->proximo = *lista;
(*lista)->anterior = novo;
*lista = novo;
}
else{
aux = *lista;
while(aux->proximo && novo->valor > aux->proximo->valor)
aux = aux->proximo;
novo->proximo = aux->proximo;
if(aux->proximo)
aux->proximo->anterior = novo;
novo->anterior = aux;
aux->proximo = novo;
}
}
else
printf("Erro ao alocar memoria!\n");
}
No* remover(No **lista, int num){
No *aux, *remover = NULL;
if(*lista){
if((*lista)->valor == num){
remover = *lista;
*lista = remover->proximo;
if(*lista)
(*lista)->anterior = NULL;
}
else{
aux = *lista;
while(aux->proximo && aux->proximo->valor != num)
aux = aux->proximo;
if(aux->proximo){
remover = aux->proximo;
aux->proximo = remover->proximo;
if(aux->proximo)
aux->proximo->anterior = aux;
}
}
}
return remover;
}
No* buscar(No **lista, int num){
No *aux, *no = NULL;
aux = *lista;
while(aux && aux->valor != num)
aux = aux->proximo;
if(aux)
no = aux;
return no;
}
void imprimir(No *no){
printf("\n\tLista: ");
while(no){
printf("%d ", no->valor);
no = no->proximo;
}
printf("\n\n");
}
// retorna ponteiro para o último nó da lista
No* ultimo(No **lista){
No *aux = *lista;
while(aux->proximo)
aux = aux->proximo;
return aux;
}
// imprime a lista do fim para o início
// recebe um ponteiro para o último nó da lista
void imprimirContrario(No *no){
printf("\n\tLista: ");
while(no){
printf("%d ", no->valor);
no = no->anterior;
}
printf("\n\n");
}
int main(){
int opcao, valor, anterior;
No *removido, *lista = NULL;
do{
printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - InserirM\n\t4 - InserirO\n\t5 - Remover\n\t6 - Imprimir\n\t7 - Buscar\n\t8 - ImprimirC\n");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_no_inicio(&lista, valor);
break;
case 2:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_no_fim(&lista, valor);
break;
case 3:
printf("Digite um valor e o valor de referencia: ");
scanf("%d%d", &valor, &anterior);
inserir_no_meio(&lista, valor, anterior);
break;
case 4:
printf("Digite um valor: ");
scanf("%d", &valor);
inserir_ordenado(&lista, valor);
break;
case 5:
printf("Digite um valor a ser removido: ");
scanf("%d", &valor);
removido = remover(&lista, valor);
if(removido){
printf("Elemento a ser removido: %d\n", removido->valor);
free(removido);
}
else
printf("Elemento inexistente!\n");
break;
case 6:
imprimir(lista);
break;
case 7:
printf("Digite um valor a ser buscado: ");
scanf("%d", &valor);
removido = buscar(&lista, valor);
if(removido)
printf("Elemento encontrado: %d\n", removido->valor);
else
printf("Elemento nao encontrado!\n");
break;
case 8:
imprimirContrario(ultimo(&lista));
break;
default:
if(opcao != 0)
printf("Opcao invalida!\n");
}
}while(opcao != 0);
return 0;
}
Suas aulas tem me ajudado muito mestre.