Estruturas de dados: lista encadeada

1. Introdução à Lista Encadeada

Uma lista encadeada é uma estrutura de dados linear e dinâmica, composta por nós que armazenam um valor e um ponteiro para o próximo elemento da sequência. Diferente dos arrays estáticos, que exigem tamanho fixo em tempo de compilação, a lista encadeada cresce e encolhe conforme a necessidade, alocando memória sob demanda.

Vantagens principais:
- Inserção e remoção eficientes no início da lista (O(1))
- Alocação dinâmica de memória, sem desperdício
- Não requer realocação de todos os elementos ao inserir/remover

Desvantagens:
- Acesso sequencial obrigatório (O(n) para acessar um elemento)
- Overhead de memória para armazenar os ponteiros
- Maior complexidade de implementação comparada a arrays

2. Estrutura do Nó e Alocação Dinâmica

Cada nó da lista é definido por uma struct contendo dois campos: o dado propriamente dito e um ponteiro para o próximo nó.

typedef struct Node {
    int data;           // campo de dado
    struct Node* next;  // ponteiro para o próximo nó
} Node;

Para criar um novo nó, utilizamos malloc() para alocar memória dinamicamente. É fundamental verificar se o retorno de malloc() não é NULL antes de usar o ponteiro.

Node* criarNo(int valor) {
    Node* novo = (Node*)malloc(sizeof(Node));
    if (novo == NULL) {
        printf("Erro: falha na alocação de memória.\n");
        exit(EXIT_FAILURE);
    }
    novo->data = valor;
    novo->next = NULL;
    return novo;
}

3. Operações Básicas: Inserção

Inserção no início

A operação mais simples: o novo nó aponta para a cabeça atual, e a cabeça passa a ser o novo nó.

void inserirInicio(Node** head, int valor) {
    Node* novo = criarNo(valor);
    novo->next = *head;
    *head = novo;
}

Inserção no fim

Percorremos a lista até o último nó e ajustamos seu ponteiro next.

void inserirFim(Node** head, int valor) {
    Node* novo = criarNo(valor);
    if (*head == NULL) {
        *head = novo;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = novo;
}

Inserção em posição específica

Aqui percorremos a lista até a posição desejada (índice) e ajustamos os ponteiros.

void inserirPosicao(Node** head, int valor, int pos) {
    if (pos == 0) {
        inserirInicio(head, valor);
        return;
    }
    Node* novo = criarNo(valor);
    Node* temp = *head;
    for (int i = 0; temp != NULL && i < pos - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL) return; // posição inválida
    novo->next = temp->next;
    temp->next = novo;
}

4. Operações Básicas: Remoção e Busca

Remoção do primeiro nó

void removerInicio(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

Remoção por valor

Buscamos o nó que contém o valor e ajustamos o ponteiro do nó anterior.

void removerValor(Node** head, int valor) {
    Node* temp = *head;
    Node* anterior = NULL;

    while (temp != NULL && temp->data != valor) {
        anterior = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // valor não encontrado

    if (anterior == NULL) {
        *head = temp->next; // remoção do primeiro nó
    } else {
        anterior->next = temp->next;
    }
    free(temp);
}

Remoção por posição

void removerPosicao(Node** head, int pos) {
    if (*head == NULL) return;
    Node* temp = *head;

    if (pos == 0) {
        *head = temp->next;
        free(temp);
        return;
    }

    Node* anterior = NULL;
    for (int i = 0; temp != NULL && i < pos; i++) {
        anterior = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // posição inválida

    anterior->next = temp->next;
    free(temp);
}

5. Percorrimento e Impressão

Para percorrer a lista, usamos um ponteiro auxiliar que avança nó por nó até encontrar NULL.

void imprimirLista(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

6. Operações Auxiliares e Limpeza

Contar número de nós

int tamanhoLista(Node* head) {
    int count = 0;
    Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

Liberar toda a lista

Essa função é crucial para evitar vazamento de memória.

void liberarLista(Node** head) {
    Node* temp;
    while (*head != NULL) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

Verificar lista vazia

int listaVazia(Node* head) {
    return head == NULL;
}

7. Comparação com Outras Estruturas da Série

Característica Lista Encadeada Pilha (array) Fila (array)
Inserção/remoção início O(1) O(n) O(n)
Acesso aleatório O(n) O(1) O(1)
Tamanho dinâmico Sim Não Não
Overhead de memória Ponteiros Nenhum Nenhum

A lista encadeada é ideal quando há muitas inserções e remoções no início da coleção, ou quando o tamanho máximo é imprevisível. Para acesso aleatório frequente, arrays são superiores.

8. Exemplo Completo e Boas Práticas

Abaixo, um programa CRUD básico que demonstra as operações principais.

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* criarNo(int valor) {
    Node* novo = (Node*)malloc(sizeof(Node));
    if (novo == NULL) {
        printf("Erro de alocação.\n");
        exit(1);
    }
    novo->data = valor;
    novo->next = NULL;
    return novo;
}

void inserirInicio(Node** head, int valor) {
    Node* novo = criarNo(valor);
    novo->next = *head;
    *head = novo;
}

void imprimirLista(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

void liberarLista(Node** head) {
    Node* temp;
    while (*head != NULL) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

int main() {
    Node* lista = NULL;

    inserirInicio(&lista, 10);
    inserirInicio(&lista, 20);
    inserirInicio(&lista, 30);

    printf("Lista: ");
    imprimirLista(lista);

    liberarLista(&lista);
    return 0;
}

Boas práticas:
- Use ponteiro duplo (**head) em funções que modificam a cabeça da lista
- Sempre verifique retorno de malloc()
- Libere toda a memória alocada antes de encerrar o programa
- Para debug, imprima os endereços dos ponteiros e use ferramentas como GDB ou Valgrind

Referências