Como construir uma lista duplamente encadeada?

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.

nó lista dupla — Representação visual do nó de uma lista duplamente encadeada.

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;
}