[402] Listas Duplamente Encadeadas e Circulares

Na aula anterior, construímos a lista encadeada simples: uma corrente de nós, cada um apontando para o próximo. Ela é elegante, mas tem uma limitação — só se pode andar num sentido, da cabeça para o fim. Não há como recuar. Hoje vamos superar isso com a lista duplamente encadeada, onde cada nó conhece tanto o próximo quanto o anterior, permitindo navegar nos dois sentidos e remover nós com muito mais facilidade. E veremos também as listas circulares, onde o fim se conecta de volta ao começo. São refinamentos que tornam as listas mais poderosas e revelam como pequenas mudanças na estrutura dos ponteiros abrem novas possibilidades.

O nó duplo: dois ponteiros em vez de um

A ideia é simples: além do ponteiro proximo, cada nó ganha um ponteiro anterior, que aponta para o nó que vem antes dele na corrente:

typedef struct No {
    int valor;
    struct No *proximo;   // aponta para o nó seguinte
    struct No *anterior;  // aponta para o nó anterior
} No;

Com esse segundo ponteiro, a lista deixa de ser uma via de mão única. De qualquer nó, você pode ir adiante (proximo) ou recuar (anterior). O primeiro nó da lista tem anterior igual a NULL (nada vem antes dele), e o último tem proximo igual a NULL (nada vem depois) — as duas pontas da corrente. Esse pequeno acréscimo custa um ponteiro a mais de memória por nó, mas paga esse custo com operações muito mais flexíveis.

Criando e inserindo no início

A criação de um nó agora inicializa os dois ponteiros como NULL:

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *proximo;
    struct No *anterior;
} No;

No *criar_no(int valor) {
    No *novo = malloc(sizeof(No));
    if (novo == NULL) return NULL;
    novo->valor = valor;
    novo->proximo = NULL;
    novo->anterior = NULL;
    return novo;
}

No *inserir_inicio(No *cabeca, int valor) {
    No *novo = criar_no(valor);
    if (novo == NULL) return cabeca;

    novo->proximo = cabeca;        // novo aponta para a antiga cabeça
    if (cabeca != NULL) {
        cabeca->anterior = novo;   // a antiga cabeça aponta de volta para novo
    }
    return novo; // novo é a nova cabeça
}

A diferença em relação à lista simples é a linha cabeca->anterior = novo: além de o novo nó apontar para a antiga cabeça (via proximo), a antiga cabeça precisa apontar de volta para o novo nó (via anterior). Toda ligação numa lista dupla é bidirecional — quando você conecta A a B com A->proximo = B, precisa também fazer B->anterior = A, mantendo os dois sentidos consistentes. Esquecer uma das duas ligações é o erro mais comum com listas duplas, e produz uma corrente "quebrada" num dos sentidos.

Percorrendo nos dois sentidos

A grande vantagem aparece ao percorrer. Podemos ir do início ao fim, como antes, mas também do fim ao início:

void imprimir_frente(No *cabeca) {
    printf("Frente: ");
    for (No *at = cabeca; at != NULL; at = at->proximo) {
        printf("%d ", at->valor);
    }
    printf("\n");
}

void imprimir_tras(No *cauda) {
    printf("Trás: ");
    for (No *at = cauda; at != NULL; at = at->anterior) { // usa 'anterior'!
        printf("%d ", at->valor);
    }
    printf("\n");
}

Para imprimir de trás para frente, começamos na cauda (o último nó) e seguimos os ponteiros anterior até chegar a NULL. Numa lista simples, isso seria impossível sem truques custosos; na lista dupla, é tão natural quanto percorrer para a frente. Essa capacidade de recuar é o que torna as listas duplas ideais para estruturas onde se navega em ambas as direções — históricos com "voltar" e "avançar", players de música, editores de texto.

A verdadeira vantagem: remover um nó com facilidade

Onde a lista dupla mais brilha é na remoção. Numa lista simples, para remover um nó você precisa do nó anterior a ele (para religar a corrente) — e encontrá-lo exige percorrer desde a cabeça. Na lista dupla, cada nó já conhece seu anterior, então a remoção é direta:

// remove um nó específico da lista dupla; retorna a (possivelmente nova) cabeça
No *remover(No *cabeca, No *alvo) {
    if (alvo == NULL) return cabeca;

    // religa o anterior do alvo ao próximo do alvo
    if (alvo->anterior != NULL) {
        alvo->anterior->proximo = alvo->proximo;
    } else {
        cabeca = alvo->proximo; // o alvo era a cabeça: a cabeça muda
    }

    // religa o próximo do alvo ao anterior do alvo
    if (alvo->proximo != NULL) {
        alvo->proximo->anterior = alvo->anterior;
    }

    free(alvo); // libera o nó removido
    return cabeca;
}

Acompanhe a lógica: para remover o alvo, fazemos o nó anterior a ele apontar para o nó seguinte a ele (alvo->anterior->proximo = alvo->proximo), e o nó seguinte apontar de volta para o anterior (alvo->proximo->anterior = alvo->anterior) — costurando a corrente por cima do alvo, nos dois sentidos. Depois, liberamos o alvo. Os if tratam os casos especiais: se o alvo é a cabeça (não tem anterior) ou a cauda (não tem próximo). Como cada nó conhece seus dois vizinhos, não precisamos percorrer a lista para achar o anterior — a remoção é imediata. Essa eficiência é a principal razão de existir da lista dupla.

Listas circulares: o fim encontra o começo

Uma variação interessante é a lista circular, onde o último nó, em vez de apontar para NULL, aponta de volta para o primeiro — fechando um ciclo. Numa lista circular dupla, a cabeça também aponta para trás para a cauda. Isso é útil quando os dados são naturalmente cíclicos: os turnos de um jogo, uma playlist em repeat, o escalonamento de tarefas em rodízio (round-robin).

// exemplo conceitual: percorrer uma lista circular simples
void imprimir_circular(No *inicio, int quantas_voltas) {
    if (inicio == NULL) return;
    No *atual = inicio;
    int contador = 0;
    int total = quantas_voltas * 3; // supondo 3 nós, para não rodar infinito

    while (contador < total) {
        printf("%d ", atual->valor);
        atual = atual->proximo;
        if (atual == inicio) {
            printf("| "); // completou uma volta
        }
        contador++;
    }
    printf("\n");
}

O cuidado central com listas circulares é o critério de parada. Como não há mais um NULL marcando o fim, um laço ingênuo while (atual != NULL) rodaria para sempre — o ciclo nunca termina. Você precisa de outra condição: contar um número de passos, ou detectar quando voltou ao ponto de partida (atual == inicio), como no exemplo. Essa é a troca da lista circular: ganha-se a continuidade cíclica, mas perde-se o marcador natural de fim, exigindo mais atenção para não criar laços infinitos.

Escolhendo a estrutura certa

Vale resumir quando usar cada variante. A lista simples é a mais econômica em memória (um ponteiro por nó) e adequada quando você só percorre num sentido e insere/remove principalmente no início. A lista dupla custa um ponteiro extra por nó, mas oferece navegação bidirecional e remoção eficiente de qualquer nó — vale a pena quando essas operações são frequentes. A lista circular serve a dados inerentemente cíclicos, ao custo de exigir cuidado redobrado com a terminação. Não há uma "melhor" absoluta: a escolha depende das operações que seu programa mais realiza. Saber avaliar esse equilíbrio é parte de pensar como um projetista de estruturas de dados.

O que vem a seguir

Hoje enriquecemos as listas: a lista dupla, com seu ponteiro anterior, permite navegar nos dois sentidos e remover nós com eficiência; a circular fecha a corrente num ciclo, útil para dados rotativos. Vimos que cada variante troca custo por capacidade, e que a escolha depende do uso. Com as listas dominadas, na próxima aula vamos usá-las como base para construir duas estruturas de dados clássicas e onipresentes — a pilha e a fila —, que impõem disciplinas específicas de inserção e remoção e aparecem em toda parte, de desfazer/refazer a processamento de requisições.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 6.5, estruturas autorreferentes
• Algorithms, Robert Sedgewick — capítulo sobre listas duplamente encadeadas
• Introduction to Algorithms (CLRS) — tratamento formal de listas duplas e circulares
• Data Structures Using C, Tenenbaum — implementações detalhadas em C
• cppreference — structs e ponteiros — https://en.cppreference.com/w/c/language/struct

Exercícios

Exercício 1

Monte uma lista duplamente encadeada com os valores 1, 2, 3, 4 (inserindo no início) e imprima-a nos dois sentidos: da frente para trás e de trás para frente. Confirme que uma é o inverso da outra.

int main(void) {
    No *lista = NULL;
    lista = inserir_inicio(lista, 4);
    lista = inserir_inicio(lista, 3);
    lista = inserir_inicio(lista, 2);
    lista = inserir_inicio(lista, 1);

    imprimir_frente(lista); // 1 2 3 4

    // encontra a cauda para imprimir de trás
    No *cauda = lista;
    while (cauda->proximo != NULL) cauda = cauda->proximo;
    imprimir_tras(cauda);   // 4 3 2 1
    return 0;
}

Exercício 2

Escreva uma função No *encontrar_cauda(No *cabeca) que percorra a lista dupla e retorne um ponteiro para o último nó (a cauda). Ela é necessária para imprimir de trás para frente a partir da cabeça.

No *encontrar_cauda(No *cabeca) {
    if (cabeca == NULL) return NULL;
    No *atual = cabeca;
    while (atual->proximo != NULL) {
        atual = atual->proximo;
    }
    return atual; // o nó cujo 'proximo' é NULL
}

Exercício 3

Escreva uma função inserir_fim para a lista dupla, lembrando de ajustar ambos os ponteiros (proximo do antigo último e anterior do novo nó). Teste inserindo alguns valores e imprimindo nos dois sentidos.

No *inserir_fim(No *cabeca, int valor) {
    No *novo = criar_no(valor);
    if (novo == NULL) return cabeca;

    if (cabeca == NULL) return novo; // lista vazia: novo é a cabeça

    No *cauda = cabeca;
    while (cauda->proximo != NULL) {
        cauda = cauda->proximo;
    }
    cauda->proximo = novo;    // o antigo último aponta para o novo
    novo->anterior = cauda;   // o novo aponta de volta para o antigo último
    return cabeca;
}

Exercício 4

Explique por que remover um nó do meio é mais eficiente numa lista dupla do que numa lista simples. O que a lista simples precisa fazer que a dupla não precisa?

Exercício 5

Explique o perigo específico de percorrer uma lista circular com um laço while (atual != NULL). Que condição de parada você usaria no lugar, e por quê?