Listas ligadas

Nesta aula, você aprenderá a implementar listas ligadas em C, desde a definição de nós com ponteiros até operações de inserção, remoção, travessia e liberação de memória. Com exemplos práticos, você entenderá como gerenciar memória dinamicamente e construir estruturas de dados flexíveis.

As listas ligadas são estruturas de dados fundamentais na programação em C, permitindo armazenar coleções de elementos de forma dinâmica, sem a necessidade de conhecer o tamanho máximo antecipadamente. Diferentemente dos arrays, que exigem um bloco contíguo de memória, as listas ligadas utilizam nós que contêm dados e um ponteiro para o próximo nó, proporcionando inserções e remoções eficientes em qualquer posição (desde que se tenha acesso ao nó anterior).

Nesta aula, vamos explorar os conceitos essenciais para dominar listas ligadas: a estrutura de um nó com ponteiros, as operações de inserção e remoção, a travessia para percorrer a lista e, crucialmente, a liberação correta da memória para evitar vazamentos. Ao final, você terá uma base sólida para implementar listas simplesmente encadeadas e estender o conhecimento para variações como listas duplamente encadeadas ou circulares.

Nós com ponteiros

O coração de uma lista ligada é o nó. Em C, definimos um nó como uma estrutura (struct) que contém um campo de dados (que pode ser de qualquer tipo, mas aqui usaremos int para simplificar) e um ponteiro para o próximo nó. Esse ponteiro é o que conecta os nós, formando uma sequência.

Vejamos como definir um nó e uma lista ligada básica:

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

// Definição do nó
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Função para criar um novo nó
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Erro de alocação de memória\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    Node* head = NULL;  // Lista vazia
    head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    // ...
    return 0;
}

No código acima, createNode aloca memória para um novo nó usando malloc e inicializa seus campos. O ponteiro next é crucial: ele aponta para o próximo nó da lista. O primeiro nó é chamado de cabeça (head) e marca o início da lista. Se head for NULL, a lista está vazia.

É importante entender que cada nó é alocado dinamicamente, ou seja, a lista cresce conforme necessário. Isso contrasta com arrays estáticos, que têm tamanho fixo. A manipulação de ponteiros exige cuidado: ao atribuir head->next a outro nó, estamos ligando os nós. Perder a referência para um nó (por exemplo, sobrescrever head sem guardar o antigo) pode causar vazamento de memória.

Inserção e remoção

Uma das grandes vantagens das listas ligadas é a facilidade de inserir e remover elementos, desde que você tenha acesso ao nó anterior. Vamos implementar funções para inserir no início, no fim e em posição específica, além de remover um nó pelo valor.

Inserção no início: Cria-se um novo nó e faz-se o ponteiro next apontar para o antigo head, atualizando head para o novo nó. Complexidade O(1).

void insertAtBeginning(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

Inserção no fim: Percorre-se a lista até o último nó (onde next é NULL) e liga-se o novo nó. Complexidade O(n), pois precisa percorrer.

void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Inserção após um nó específico: Suponha que você tenha um ponteiro para o nó anterior (prevNode). Basta ajustar os ponteiros:

void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("O nó anterior não pode ser NULL\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Remoção: Para remover um nó com um valor específico, precisamos percorrer a lista mantendo o nó anterior. Se o nó a remover for o primeiro, atualizamos head. Caso contrário, ajustamos o ponteiro next do nó anterior para pular o nó removido. Finalmente, liberamos a memória do nó com free().

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;
    // Se o nó a remover é o primeiro
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    // Procura o nó a remover, guardando o anterior
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Elemento não encontrado\n");
        return;
    }
    prev->next = temp->next;
    free(temp);
}

Note que passamos Node** head para permitir modificar o ponteiro head dentro da função. Essa é uma prática comum em C para alterar o ponteiro original.

Travessia

Travessia significa percorrer a lista, visitando cada nó. É essencial para operações como impressão, busca e soma de elementos. A travessia é feita com um ponteiro temporário que começa em head e avança para next até chegar a NULL.

Vejamos uma função para imprimir a lista:

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

Também podemos implementar uma busca:

Node* search(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

A travessia tem complexidade O(n) no pior caso. É importante não modificar head durante a travessia, pois perderíamos o início da lista. Por isso usamos um ponteiro auxiliar.

Liberando memória

Como cada nó é alocado dinamicamente com malloc, é responsabilidade do programador liberar essa memória quando não for mais necessária, usando free. Se não o fizermos, ocorrerá vazamento de memória, especialmente em programas longos.

Para liberar uma lista inteira, precisamos percorrer todos os nós e liberar um por um, mas cuidado: se liberarmos o nó atual antes de guardar o próximo, perderemos o acesso ao restante da lista. Portanto, guardamos o próximo nó em uma variável temporária antes de liberar.

void freeList(Node** head) {
    Node* current = *head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;  // Evita ponteiro pendente
}

É crucial definir *head = NULL após liberar para evitar que o ponteiro aponte para memória já liberada (ponteiro pendente). Isso também permite reutilizar a variável head para criar uma nova lista.

Vale lembrar que em C, a memória alocada com malloc não é liberada automaticamente. Portanto, sempre que você terminar de usar a lista, chame freeList. Uma boa prática é fazer isso antes de o programa terminar ou quando a lista não for mais necessária.

Boas práticas e observações

Ao trabalhar com listas ligadas, alguns cuidados são essenciais:

Sempre verifique se a alocação de memória foi bem-sucedida (malloc retorna NULL em caso de falha).
Ao modificar ponteiros, especialmente head, use ponteiro para ponteiro (Node**) para que as alterações reflitam fora da função.
Evite vazamentos de memória: libere cada nó alocado e nunca perca a referência para o início da lista.
Considere o uso de listas duplamente encadeadas se precisar percorrer em ambas as direções ou remover nós sem conhecer o anterior.
Pense na complexidade: inserções no início são O(1), enquanto no fim são O(n). Se precisar de inserções no fim frequentes, mantenha um ponteiro para o último nó.

Referências

Exercícios

Implemente uma função que conte o número de nós em uma lista ligada (retorne o tamanho). Use a seguinte assinatura: int listLength(Node* head);

✓ Resposta:

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

Escreva uma função para inserir um nó em uma posição específica (índice baseado em 0). Se a posição for inválida, não faça nada. Assinatura: void insertAtPosition(Node** head, int data, int position);

✓ Resposta:

void insertAtPosition(Node** head, int data, int position) {
    if (position < 0) return;
    if (position == 0) {
        insertAtBeginning(head, data);
        return;
    }
    Node* current = *head;
    int i = 0;
    while (current != NULL && i < position - 1) {
        current = current->next;
        i++;
    }
    if (current == NULL) {
        printf("Posição inválida\n");
        return;
    }
    insertAfter(current, data);
}

Crie uma função que remove o nó do final da lista. Assinatura: void removeLast(Node** head); Lembre-se de liberar a memória.

✓ Resposta:

void removeLast(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

Implemente uma função que inverte a lista ligada. Assinatura: void reverseList(Node** head); Dica: use três ponteiros para percorrer e inverter os links.

✓ Resposta:

void 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;
    }
    *head = prev;
}

Escreva uma função que verifica se uma lista ligada é um palíndromo (os valores são os mesmos de frente para trás). Assinatura: int isPalindrome(Node* head); Retorne 1 se for palíndromo, 0 caso contrário. Você pode usar uma pilha ou inverter a segunda metade.

✓ Resposta:

// Abordagem: copiar para um array e comparar (simples)
int isPalindrome(Node* head) {
    int len = listLength(head);
    int* arr = (int*)malloc(len * sizeof(int));
    if (arr == NULL) return 0;
    Node* temp = head;
    for (int i = 0; i < len; i++) {
        arr[i] = temp->data;
        temp = temp->next;
    }
    for (int i = 0; i < len / 2; i++) {
        if (arr[i] != arr[len - 1 - i]) {
            free(arr);
            return 0;
        }
    }
    free(arr);
    return 1;
}

Nós com ponteiros

Inserção e remoção

Travessia

Liberando memória

Boas práticas e observações

Referências

Exercícios

Mais desta categoria

Listas duplamente ligadas

Argumentos de linha de comando

Programação genérica com void*