O Conceito de Lista Encadeada

Diferente dos arrays, onde os elementos são armazenados de forma contígua na memória, uma lista encadeada organiza os dados de maneira dinâmica. Ela é composta por unidades chamadas nós. Cada nó contém a informação útil e um ponteiro que indica o endereço do próximo elemento, criando uma estrutura lógica linear, embora física e esparsamente distribuída na memória.

Estrutura de um Nó

Para implementar essa estrutura em C, utilizamos structs. Um nó padrão é composto pelo dado (que pode ser de qualquer tipo) e um ponteiro para o próximo nó do mesmo tipo.

typedef int TipoDado;

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

O controle da lista geralmente é fieto por um ponteiro inicial, muitas vezes chamado de head ou topo, que armazena o endereço do primeiro nó. Se a lista estiver vazia, esse ponteiro será NULL.

Criação e Alocação de Nós

Como o tamanho da lista pode variar durente a execução, os nós devem ser alocados no heap usando malloc. Isso garante que os dados persistam além do escopo da função de criação.

No* criar_novo_no(TipoDado x) {
    No* novo = (No*)malloc(sizeof(No));
    if (novo == NULL) {
        perror("Erro na alocação de memória");
        exit(EXIT_FAILURE);
    }
    novo->valor = x;
    novo->proximo = NULL;
    return novo;
}

Exibição dos Dados

Para imprimir os elementos, percorremos a lista partindo do início até encontrarmos um ponteiro nulo. Como essa operação não altera a estrutura da lista, passamos apenas uma cópia do ponteiro inicial.

void imprimir_lista(No* cabeca) {
    No* navegador = cabeca;
    while (navegador != NULL) {
        printf("%d -> ", navegador->valor);
        navegador = navegador->proximo;
    }
    printf("NULL\n");
}

Inserção no Início

A inserção no topo da lista exige a atualização do ponteiro principal da lista. Por isso, passamos o endereço do ponteiro (ponteiro duplo) para que a alteração reflita fora da função.

void inserir_no_inicio(No** p_cabeca, TipoDado x) {
    No* novo = criar_novo_no(x);
    novo->proximo = *p_cabeca;
    *p_cabeca = novo;
}

Inserção no Final

Para inserir no fim, existem dois cenários: se a lista estiver vazia, o novo nó se torna a cabeça. Caso contrário, percorremos até o último nó (onde proximo == NULL) e o conectamos ao novo nó.

void inserir_no_fim(No** p_cabeca, TipoDado x) {
    No* novo = criar_novo_no(x);
    if (*p_cabeca == NULL) {
        *p_cabeca = novo;
        return;
    }
    No* atual = *p_cabeca;
    while (atual->proximo != NULL) {
        atual = atual->proximo;
    }
    atual->proximo = novo;
}

Remoção de Elementos

A remoção pode ocorrer no início ou no fim. Em ambos os casos, é vital liberar a memória com free().

Remoção no Início

void remover_inicio(No** p_cabeca) {
    if (*p_cabeca == NULL) return;
    
    No* temporario = *p_cabeca;
    *p_cabeca = (*p_cabeca)->proximo;
    free(temporario);
}

Remoção no Final

Para remover o último, precisamos encontrar o penúltimo nó para transformar seu ponteiro proximo em NULL.

void remover_fim(No** p_cabeca) {
    if (*p_cabeca == NULL) return;
    if ((*p_cabeca)->proximo == NULL) {
        free(*p_cabeca);
        *p_cabeca = NULL;
        return;
    }
    No* anterior = NULL;
    No* atual = *p_cabeca;
    while (atual->proximo != NULL) {
        anterior = atual;
        atual = atual->proximo;
    }
    free(atual);
    anterior->proximo = NULL;
}

Busca de Informação

A função de busca percorre a lista comparando o valor de cada nó com o valor procurado, retornando o endereço do nó se encontrado.

No* buscar_valor(No* cabeca, TipoDado x) {
    No* navegador = cabeca;
    while (navegador) {
        if (navegador->valor == x) return navegador;
        navegador = navegador->proximo;
    }
    return NULL;
}

Operações em Posições Específicas

Muitas vezes precisamos inserir ou remover dados em relação a um nó específico (chamado de pos).

Inserção após um nó específico

void inserir_depois(No* pos, TipoDado x) {
    if (pos == NULL) return;
    No* novo = criar_novo_no(x);
    novo->proximo = pos->proximo;
    pos->proximo = novo;
}

Remoção de um nó específico

Se o nó a ser removido for a cabeça, atuailzamos o ponteiro inicial. Caso contrário, ligamos o nó anterior diretamente ao sucessor do nó atual.

void remover_no_especifico(No** p_cabeca, No* pos) {
    if (p_cabeca == NULL || pos == NULL || *p_cabeca == NULL) return;
    
    if (*p_cabeca == pos) {
        *p_cabeca = pos->proximo;
    } else {
        No* anterior = *p_cabeca;
        while (anterior->proximo != pos) {
            anterior = anterior->proximo;
        }
        anterior->proximo = pos->proximo;
    }
    free(pos);
}

Liberação de Memória Total

Ao finalizar o uso da lista, todos os nós devem ser liberados individualmente para evitar vazamentos de memória (memory leaks).

void destruir_lista(No** p_cabeca) {
    No* atual = *p_cabeca;
    while (atual != NULL) {
        No* prox = atual->proximo;
        free(atual);
        atual = prox;
    }
    *p_cabeca = NULL;
}