As listas ligadas são estruturas de dados fundamentais na programação, especialmente em C, onde o gerenciamento de memória é explícito. Diferentemente dos arrays, que ocupam um bloco contíguo de memória, as listas ligadas consistem em nós alocados dinamicamente, cada um contendo um valor e um ponteiro para o próximo nó. Isso permite inserções e remoções eficientes sem a necessidade de deslocar elementos, embora o acesso a um elemento específico exija percorrer a lista desde o início.

Nesta aula, vamos explorar a implementação de listas ligadas simples em C, cobrindo a definição de nós com ponteiros, as operações básicas de inserção e remoção, a travessia para percorrer a lista e, crucialmente, a liberação de memória para evitar vazamentos. Ao final, você terá uma base sólida para construir estruturas mais complexas, como pilhas, filas e listas duplamente ligadas.

Nós com ponteiros

O coração de uma lista ligada é o nó. Em C, um nó é uma estrutura que armazena um dado (por exemplo, um inteiro) e um ponteiro para o próximo nó. Esse ponteiro é fundamental para encadear os nós, formando a sequência. A definição típica é:

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

// Definição do nó
typedef struct Node {
    int data;               // dado armazenado
    struct Node* next;      // ponteiro para o próximo nó
} Node;

Observe que usamos struct Node* dentro da própria estrutura. Isso é necessário porque o ponteiro deve apontar para outro nó do mesmo tipo. O uso de typedef simplifica a declaração de variáveis: podemos escrever Node* head em vez de struct Node* head.

Uma lista ligada é geralmente representada por um ponteiro para o primeiro nó, chamado de head. Se a lista estiver vazia, head é NULL. Cada nó aponta para o próximo, e o último nó aponta para NULL, indicando o fim da lista. Essa estrutura permite que os nós estejam em qualquer lugar da memória, pois os ponteiros mantêm a ordem lógica.

Inserção e remoção

As operações de inserção e remoção são as mais comuns em listas ligadas. Podemos inserir no início, no final ou em uma posição específica. A inserção no início é a mais simples: criamos um novo nó, apontamos seu next para o antigo head e atualizamos head para o novo nó. Veja um exemplo:

// Insere um novo nó no início da lista
void insertAtBeginning(Node** head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Erro: falha na alocação de memória.\n");
        return;
    }
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

Aqui, usamos um ponteiro para ponteiro (Node**) porque precisamos modificar o head original. Se passássemos apenas Node* head, a alteração não seria refletida fora da função (a menos que usássemos retorno). Essa técnica é comum em C para modificar ponteiros dentro de funções.

A inserção no final exige percorrer a lista até o último nó. Se a lista estiver vazia, basta definir head como o novo nó. Caso contrário, percorremos até encontrar um nó cujo next seja NULL e então o ligamos ao novo nó. A complexidade é O(n), pois precisamos percorrer a lista.

// Insere no final da lista
void insertAtEnd(Node** head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Erro: falha na alocação de memória.\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

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

A remoção também pode ser feita por valor ou por posição. Para remover o primeiro nó, basta atualizar head para o segundo nó e liberar a memória do antigo. Para remover um nó específico, precisamos localizá-lo e ajustar o ponteiro do nó anterior. Vamos implementar a remoção por valor:

// Remove o primeiro nó que contém o valor especificado
void removeByValue(Node** head, int value) {
    if (*head == NULL) return;

    Node* temp = *head;
    Node* prev = NULL;

    // Se o head for o nó a ser removido
    if (temp != NULL && temp->data == value) {
        *head = temp->next;
        free(temp);
        return;
    }

    // Procura o nó a ser removido
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Valor %d não encontrado.\n", value);
        return;
    }

    // Desencadeia o nó e libera memória
    prev->next = temp->next;
    free(temp);
}

É importante sempre liberar a memória do nó removido usando free() para evitar vazamento de memória. Além disso, devemos atualizar corretamente os ponteiros para manter a integridade da lista.

Travessia

Percorrer uma lista ligada é uma operação comum para imprimir, buscar ou modificar elementos. A travessia é feita com um ponteiro temporário que começa no head e avança nó a nó até encontrar NULL. Vejamos como imprimir todos os elementos:

// Imprime todos os elementos da lista
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Essa função recebe apenas o ponteiro head por valor, pois não precisa alterá-lo. A cada iteração, temp avança para o próximo nó. Essa é a maneira mais simples de percorrer uma lista ligada. A complexidade é O(n), onde n é o número de nós.

Além de imprimir, podemos usar a travessia para buscar um valor, contar nós, ou até mesmo liberar a lista (como veremos na próxima seção). A travessia é a base de muitas operações.

Liberando memória

Como as listas ligadas usam alocação dinâmica, é crucial liberar toda a memória quando a lista não for mais necessária. Se não fizermos isso, teremos vazamentos de memória, que podem causar problemas em programas longos. A liberação deve ser feita percorrendo a lista e liberando cada nó individualmente.

// Libera toda a memória da lista
void freeList(Node** head) {
    Node* temp = *head;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        free(temp);
        temp = next;
    }
    *head = NULL; // Opcional, mas evita ponteiro pendente
}

Na função acima, guardamos o próximo nó antes de liberar o atual, pois após free(temp) não podemos acessar temp->next (comportamento indefinido). Ao final, definimos *head como NULL para evitar que o ponteiro aponte para memória liberada.

É importante sempre chamar freeList() antes de o programa terminar, para garantir que toda a memória alocada seja devolvida ao sistema. Ferramentas como Valgrind podem ajudar a detectar vazamentos de memória em programas C.

Exemplo completo

Vamos juntar tudo em um programa completo que demonstra a criação, inserção, travessia e liberação de uma lista ligada:

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

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

// Funções definidas anteriormente...
void insertAtBeginning(Node** head, int value);
void insertAtEnd(Node** head, int value);
void removeByValue(Node** head, int value);
void printList(Node* head);
void freeList(Node** head);

int main() {
    Node* head = NULL;

    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    printf("Lista: ");
    printList(head);

    removeByValue(&head, 20);
    printf("Após remover 20: ");
    printList(head);

    freeList(&head);
    return 0;
}

Esse programa cria uma lista com os valores 20, 10, 30, 40 (na ordem de inserção), imprime, remove o 20 e imprime novamente. Ao final, libera toda a memória.

Boas práticas

  • Sempre verifique se malloc retornou NULL antes de usar o ponteiro.
  • Use ponteiro para ponteiro (Node**) em funções que modificam o head.
  • Nunca acesse um nó após liberá-lo com free.
  • Mantenha a lista sempre consistente: após cada operação, os ponteiros devem estar corretos.
  • Documente suas funções para facilitar a manutenção.

Referências

Exercícios

  1. Escreva uma função em C que conte o número de nós em uma lista ligada (recebe o head e retorna o total).

    ✓ Resposta:
    int countNodes(Node* head) {
    int count = 0;
    Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}
  2. Implemente uma função que insere um novo nó em uma posição específica (índice) da lista. Considere que o índice 0 é o início. Se o índice for inválido, não faça nada.

    ✓ Resposta:
    void insertAtPosition(Node** head, int value, int position) {
    if (position < 0) return;
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return;
    newNode->data = value;
    newNode->next = NULL;

    if (position == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* temp = *head;
    for (int i = 0; i < position - 1; i++) {
        if (temp == NULL) {
            free(newNode);
            return; // posição inválida
        }
        temp = temp->next;
    }
    if (temp == NULL) {
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}
  3. Crie uma função que remova o último nó da lista e retorne o valor removido (ou -1 se a lista estiver vazia).

    ✓ Resposta:
    int removeLast(Node** head) {
    if (*head == NULL) return -1;
    Node* temp = *head;
    Node* prev = NULL;
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    int value = temp->data;
    if (prev == NULL) {
        // só havia um nó
        free(temp);
        *head = NULL;
    } else {
        prev->next = NULL;
        free(temp);
    }
    return value;
}
  4. Escreva uma função que receba a cabeça da lista e inverta a ordem dos nós, retornando o novo head. (Dica: use três ponteiros).

    ✓ Resposta:
    Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
  5. Escreva uma função que verifique se uma lista ligada possui ciclo (ou seja, se algum nó aponta para um nó anterior). Use o algoritmo de detecção de ciclo de Floyd (tartaruga e lebre).

    ✓ Resposta:
    int hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

Observações finais

As listas ligadas são uma ferramenta poderosa, mas exigem cuidado com a memória e com os ponteiros. Pratique bastante implementando as operações básicas e depois avance para variações como listas duplamente ligadas e listas circulares. O entendimento profundo dessas estruturas é essencial para se tornar um programador C competente.