Hoje na aula de Ciências da Computação, mergulhamos no mundo das listas encadeadas. Essa estrutura de dados é fundamental para quem deseja entender alocação dinâmica e manipulação eficiente de coleções de elementos.

O que é uma lista encadeada?

Uma lista encadeada é uma estrutura de dados linear, onde cada elemento (nó) contém um valor e uma referência (ponteiro) para o próximo elemento da sequência. Diferente dos arrays, que ocupam um bloco contínuo de memória, as listas encadeadas podem ter seus nós espalhados pela memória, conectados através dos ponteiros.

Existem vários tipos: listas simplesmente encadeadas, duplamente encadeadas e circulares. Hoje focamos na versão simplesmente encadeada.

Vantagens e desvantagens

As listas encadeadas oferecem vantagens como inserção e remoção eficientes no início ou após um nó conhecido, sem necessidade de deslocar elementos. Além disso, o tamanho é dinâmico: podemos adicionar quantos elementos quisermos, desde que haja memória disponível.

Por outro lado, o acesso a um elemento específico exige percorrer a lista a partir do início (acesso sequencial), tornando a busca menos eficiente que em arrays (acesso aleatório). Além disso, cada nó consome memória extra para armazenar o ponteiro.

Implementação básica em C

Para fixar, implementamos uma lista encadeada simples em C. Definimos uma struct Node com um inteiro e um ponteiro para o próximo nó:

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

Em seguida, criamos funções para inserir no início, remover um elemento e imprimir a lista. A função de inserção no início é simples: alocamos um novo nó, apontamos seu next para o head atual e atualizamos head para o novo nó.

Exemplo de inserção e remoção

Vimos na prática como implementar as funções que manipulam a lista. Abaixo estão exemplos completos de inserção no início, inserção no fim e remoção de um nó por valor:

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

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

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

Observamos que a inserção no início é O(1), enquanto a inserção no fim precisa percorrer toda a lista a menos que mantenhamos um ponteiro especial para o último nó (tail). A remoção também exige localizar o nó anterior, o que tem complexidade O(n) no pior caso.

Operações principais

As operações básicas são: inserção (no início, no fim ou após um nó), remoção (por valor ou posição) e busca. Cada uma tem complexidade O(1) para o início, O(n) para o fim se não tivermos referência ao último nó. Discutimos como manter um ponteiro para o último nó para tornar a inserção no fim O(1).

A remoção exige localizar o nó anterior ao que queremos remover, o que também é O(n) no pior caso. A busca sequencial percorre a lista até encontrar o valor desejado.

Busca em listas encadeadas

A busca em uma lista encadeada simples é sequencial: começamos pela cabeça e percorremos nó a nó até encontrar o valor procurado ou chegar ao fim. Sua complexidade é O(n) no pior caso. Implementamos uma função de busca que retorna o ponteiro para o nó encontrado ou NULL:

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

Se a lista estiver ordenada, podemos otimizar a busca interrompendo a varredura quando o valor ultrapassar o alvo, mas ainda assim será O(n). Para acesso aleatório rápido, arrays ou tabelas hash são mais adequados.

Listas duplamente encadeadas

Um aprimoramento é a lista duplamente encadeada, onde cada nó possui dois ponteiros: um para o próximo e outro para o anterior. Isso permite percorrer a lista em ambas as direções e facilita a remoção de um nó quando temos apenas seu ponteiro (desde que não seja o primeiro). Em contrapartida, o consumo de memória é maior e as operações de inserção/remoção exigem ajustar mais ponteiros.

Listas circulares

Outra variação é a lista circular, onde o último nó aponta de volta para o primeiro (ou para um nó cabeça). Não há um fim propriamente dito; a lista forma um ciclo. Isso é útil em aplicações como escalonamento circular (round-robin), onde cada processo ganha um tempo de CPU em rodízio. A implementação é similar à lista simples, mas devemos tomar cuidado para não entrar em loop infinito ao percorrer — normalmente usamos um contador ou paramos ao retornar ao nó inicial.

Aplicações práticas das listas encadeadas

As listas encadeadas aparecem em diversas áreas da computação:

  • Pilhas (stacks) e filas (queues) podem ser implementadas de forma eficiente com listas encadeadas, especialmente quando o tamanho máximo não é conhecido.
  • Tabelas hash com encadeamento separado — cada posição da tabela mantém uma lista encadeada de elementos que colidiram.
  • Sistemas de arquivos — algumas implementações usam listas encadeadas para gerenciar blocos de alocação.
  • Navegação “undo/redo” em editores: uma lista duplamente encadeada permite percorrer as versões anteriores e posteriores.
  • Cache LRU (Least Recently Used) — uma lista duplamente encadeada combinada com um dicionário permite remover o item menos usado em O(1).
  • Representação de polinômios — cada nó guarda um termo (coeficiente e expoente) e o próximo termo.

Pontos‑chave

  • Lista encadeada: estrutura linear dinâmica com nós conectados por ponteiros.
  • Inserção e remoção no início: O(1) — muito mais rápido que um array.
  • Acesso a um elemento exige percorrer desde o início: O(n) — acesso sequencial.
  • Listas duplamente encadeadas permitem navegação bidirecional, mas usam mais memória.
  • Listas circulares são úteis para aplicações que exigem repetição infinita ou escalonamento circular.
  • Cada nó ocupa espaço extra para o(s) ponteiro(s), o que pode ser relevante em listas muito grandes.
  • A alocação dinâmica (malloc/free) deve ser usada com cuidado para evitar vazamentos de memória.

Considerações finais

As listas encadeadas são uma ferramenta poderosa e aparecem em diversas aplicações, como implementação de filas, pilhas e tabelas hash. Dominar essa estrutura é essencial para qualquer programador. Na próxima aula, veremos como aplicar listas na resolução de problemas práticos.

Perguntas frequentes

Qual a diferença entre lista encadeada e array? Arrays ocupam espaço contínuo e têm tamanho fixo, enquanto listas encadeadas são dinâmicas e não contínuas, mas exigem mais memória por nó e acesso sequencial.

Quando usar lista encadeada? Quando você precisa de inserções/remoções frequentes no início ou não conhece o tamanho máximo da coleção. Se o acesso rápido por índice for importante, um array é mais adequado.

O que é um nó? É a unidade básica de uma lista encadeada, contendo o dado e o ponteiro para o próximo nó (ou para o anterior em listas duplamente encadeadas).

Como inverter uma lista encadeada? Podemos inverter iterativamente: percorremos a lista alterando o ponteiro next de cada nó para apontar para o nó anterior, guardando o próximo antes de modificar. Também é possível fazer recursivamente, invertendo o restante e depois ajustando a cabeça.

O que é um nó sentinela (dummy head)? É um nó extra colocado antes do primeiro elemento real. Ele simplifica operações de inserção e remoção, eliminando casos especiais para lista vazia. O nó sentinela não armazena dados relevantes e seu next aponta para o verdadeiro primeiro nó.

Lista encadeada tem tamanho máximo? Teoricamente não, pois a memória é alocada dinamicamente. Na prática, o limite é a memória disponível no sistema.