[399] Listas Encadeadas: A Estrutura que Só Existe com Ponteiros

Este é um dos artigos mais importantes de todo o curso. Chegamos ao momento em que tudo que construímos na Fase 2 — ponteiros, memória dinâmica, structs autorreferentes — se une numa estrutura viva. A lista encadeada é a primeira estrutura de dados que cresce e encolhe em tempo de execução, e ela é impensável sem ponteiros. Se você entender esta aula profundamente, terá cruzado uma fronteira: deixará de apenas usar dados e passará a construir as estruturas que os organizam. Respire fundo; vamos com calma e cada peça no lugar.

Por que os vetores não bastam

Vetores são ótimos, mas têm uma limitação fundamental que já sentimos: seu tamanho é fixo. Um vetor declarado com 100 posições sempre terá 100 posições. Inserir um elemento no meio exige empurrar todos os seguintes; crescer além do limite exige realocar tudo. Para dados que mudam de tamanho imprevisivelmente — uma fila de tarefas, um histórico que cresce, uma coleção da qual removemos itens no meio — precisamos de algo mais flexível. A lista encadeada resolve isso: ela cresce um elemento por vez, aloca cada um sob demanda, e insere ou remove sem mover nada.

A ideia central: nós ligados por ponteiros

Uma lista encadeada é uma corrente de nós. Cada nó guarda dois tipos de coisa: o dado que ele armazena e um ponteiro para o próximo nó da corrente. É esse ponteiro que "encadeia" os nós — cada um sabe onde está o seguinte, formando uma sequência. O último nó aponta para NULL, sinalizando o fim da lista.

Reencontramos aqui aquele exemplo que guardamos lá na aula typedef e o Design de Tipos Legíveis, sobre typedef — o nó autorreferente:

typedef struct No {
    int valor;           // o dado guardado neste nó
    struct No *proximo;  // ponteiro para o próximo nó (ou NULL, se for o último)
} No;

Lembra por que precisamos de struct No * em vez de apenas No * no campo proximo? Porque, dentro da definição, o apelido No ainda não existe. Agora esse detalhe ganha propósito completo: o campo proximo é um ponteiro para outro nó do mesmo tipo, e é exatamente essa autorreferência que permite encadear elementos indefinidamente. Cada nó vive no heap, alocado individualmente, e os ponteiros costuram todos numa sequência.

Criando um nó

O primeiro passo é uma função que cria um nó no heap, guarda um valor e o deixa pronto para entrar na lista:

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

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

// cria um nó no heap com o valor dado
No *criar_no(int valor) {
    No *novo = malloc(sizeof(No));
    if (novo == NULL) {
        return NULL; // falha de alocação
    }
    novo->valor = valor;
    novo->proximo = NULL; // ainda não aponta para ninguém
    return novo;
}

Cada nó é alocado com malloc (a lição da aula Alocação Dinâmica: malloc, calloc, realloc e free), preenchido via a seta -> (a lição da aula Ponteiros para Struct e o Operador Seta), e devolvido — vivendo no heap, portanto sobrevivendo ao retorno da função. Note que proximo começa como NULL: um nó recém-criado ainda não está ligado a nada. Toda a estrutura da lista se apoia nesses nós individuais alocados dinamicamente.

Inserindo no início: a operação mais simples

A forma mais fácil de adicionar um elemento é inseri-lo no começo da lista. A lista é representada por um ponteiro para seu primeiro nó — a "cabeça" (head). Inserir no início significa: criar o nó novo, fazer ele apontar para a antiga cabeça, e então ele vira a nova cabeça.

// insere um valor no início da lista; retorna a nova cabeça
No *inserir_inicio(No *cabeca, int valor) {
    No *novo = criar_no(valor);
    if (novo == NULL) return cabeca; // se falhou, lista inalterada

    novo->proximo = cabeca; // o novo nó aponta para o antigo primeiro
    return novo;            // o novo nó é a nova cabeça
}

Acompanhe a dança dos ponteiros, porque ela é a essência de tudo. O novo nó passa a apontar para quem era a cabeça (novo->proximo = cabeca), e depois o novo nó se torna a cabeça (retornamos novo). Dois ajustes de ponteiro e a inserção está feita — sem mover nenhum outro elemento, não importa o tamanho da lista. Compare com um vetor, onde inserir no início exigiria empurrar todos os elementos uma posição adiante. É essa eficiência nas inserções e remoções que justifica a lista encadeada.

Percorrendo a lista

Para visitar todos os elementos, começamos na cabeça e seguimos os ponteiros proximo até chegar a NULL:

void imprimir(No *cabeca) {
    No *atual = cabeca; // começa na cabeça
    printf("Lista: ");
    while (atual != NULL) {       // enquanto não chegou ao fim
        printf("%d -> ", atual->valor);
        atual = atual->proximo;   // avança para o próximo nó
    }
    printf("NULL\n");
}

O padrão é fundamental e você vai repeti-lo sempre: um ponteiro auxiliar (atual) começa na cabeça e, a cada volta, "salta" para o próximo nó com atual = atual->proximo, até que atual seja NULL (o fim). É a versão em lista daquele "andar com um ponteiro" que vimos ao percorrer vetores — só que agora seguimos ligações explícitas em vez de posições contíguas. E aqui reaparece a intuição da recursão (aula Recursão: Quando uma Função Chama a Si Mesma): "processar este nó e depois processar o resto" é naturalmente recursivo, como veremos nos exercícios.

Um programa completo: montando e percorrendo

Vamos juntar as peças e ver a lista ganhar vida:

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

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

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

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

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

// libera TODA a lista, nó por nó — indispensável!
void liberar(No *cabeca) {
    No *atual = cabeca;
    while (atual != NULL) {
        No *proximo = atual->proximo; // guarda o próximo ANTES de liberar
        free(atual);                  // libera o nó atual
        atual = proximo;              // avança
    }
}

int main(void) {
    No *lista = NULL; // lista vazia começa como NULL

    lista = inserir_inicio(lista, 30);
    lista = inserir_inicio(lista, 20);
    lista = inserir_inicio(lista, 10);

    imprimir(lista); // 10 -> 20 -> 30 -> NULL

    liberar(lista); // devolve toda a memória ao sistema
    return 0;
}

Saída: 10 -> 20 -> 30 -> NULL.

Note que inserimos 30, 20 e 10 nessa ordem, mas a lista imprime 10 -> 20 -> 30 — porque cada inserção no início coloca o novo elemento na frente. E observe como uma lista vazia é simplesmente NULL: a cabeça nula representa "nenhum nó ainda". Cada inserir_inicio reatribui lista à nova cabeça retornada, um padrão que você verá sempre.

A responsabilidade que vem junto: liberar a lista

Preste atenção especial à função liberar, porque ela reúne toda a disciplina de memória da Fase 2. Cada nó foi alocado com malloc, então cada nó precisa de um free — a lista inteira precisa ser desalocada nó por nó. E há uma sutileza crucial: antes de liberar um nó, guardamos o endereço do próximo numa variável temporária (No *proximo = atual->proximo). Por quê? Porque depois de free(atual), o nó deixa de existir — tentar ler atual->proximo depois seria um use-after-free, o erro que estudamos na aula Vazamentos de Memória e Como Caçá-los. Guardamos o "próximo" antes de destruir o "atual". Esquecer a função liberar (ou errá-la) causa um vazamento de toda a lista. A flexibilidade da alocação dinâmica vem com o preço da liberação manual — e numa estrutura de nós, esse preço se multiplica por cada nó.

O que vem a seguir

Hoje construímos nossa primeira estrutura de dados dinâmica: a lista encadeada, uma corrente de nós no heap, cada um apontando para o próximo, capaz de crescer e encolher elemento a elemento. Vimos como criar nós, inserir no início, percorrer seguindo ponteiros, e — essencial — liberar toda a estrutura com disciplina. Esta é a estrutura fundadora; tudo nas próximas aulas se apoia nela. Na próxima, vamos torná-la mais poderosa com as listas duplamente encadeadas (onde cada nó aponta para o anterior e o próximo, permitindo caminhar nos dois sentidos) e as circulares, além de operações mais completas como inserção no fim e remoção de um nó específico.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 6.5, Self-referential Structures
• Algorithms, Robert Sedgewick — capítulo sobre listas encadeadas e suas operações
• cppreference — sobre structs autorreferentes e alocação dinâmica — https://en.cppreference.com/w/c/language/struct
• Data Structures Using C, Tenenbaum — tratamento clássico e detalhado de listas em C
• Modern C, Jens Gustedt — seção sobre estruturas encadeadas — https://gustedt.gitlabpages.inria.fr/modern-c/

Exercícios

Exercício 1

Usando as funções criar_no e inserir_inicio do artigo, monte uma lista com os valores 5, 10, 15, 20 e imprima-a. Depois libere toda a lista com liberar. Compile sob Valgrind e confirme que não há vazamentos.

int main(void) {
    No *lista = NULL;
    lista = inserir_inicio(lista, 20);
    lista = inserir_inicio(lista, 15);
    lista = inserir_inicio(lista, 10);
    lista = inserir_inicio(lista, 5);
    imprimir(lista); // 5 -> 10 -> 15 -> 20 -> NULL
    liberar(lista);
    return 0;
}

Exercício 2

Escreva uma função int contar(No *cabeca) que percorra a lista e retorne quantos nós ela possui. Teste com uma lista de tamanho conhecido.

int contar(No *cabeca) {
    int n = 0;
    for (No *atual = cabeca; atual != NULL; atual = atual->proximo) {
        n++;
    }
    return n;
}

Exercício 3

Escreva uma função No *inserir_fim(No *cabeca, int valor) que insira um novo nó no final da lista. Cuidado com o caso especial da lista vazia (quando a cabeça é NULL). Explique por que inserir no fim é mais trabalhoso que inserir no início.

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

    if (cabeca == NULL) {   // caso especial: lista vazia
        return novo;        // o novo nó vira a cabeça
    }

    No *atual = cabeca;
    while (atual->proximo != NULL) { // caminha até o último nó
        atual = atual->proximo;
    }
    atual->proximo = novo; // liga o último nó ao novo
    return cabeca;         // a cabeça não muda
}

Exercício 4

Escreva uma função recursiva void imprimir_rec(No *cabeca) que imprima a lista usando recursão em vez de um laço. Identifique o caso base e o caso recursivo, conectando com a aula Recursão: Quando uma Função Chama a Si Mesma.

void imprimir_rec(No *cabeca) {
    if (cabeca == NULL) {   // caso base: fim da lista
        printf("NULL\n");
        return;
    }
    printf("%d -> ", cabeca->valor); // processa o nó atual
    imprimir_rec(cabeca->proximo);   // caso recursivo: o resto da lista
}

Exercício 5

Explique, com suas palavras, por que a função liberar precisa guardar o ponteiro proximo numa variável temporária antes de chamar free(atual). O que aconteceria se a ordem fosse invertida?