As listas duplamente ligadas são estruturas de dados lineares e dinâmicas, onde cada elemento (nó) contém um ponteiro para o próximo nó e outro para o nó anterior. Isso permite a navegação bidirecional, facilitando operações como inserção e remoção em ambas as extremidades com eficiência.

Nesta aula, vamos detalhar a estrutura de um nó, implementar operações essenciais (inserção, remoção, busca, impressão), discutir as vantagens dessa estrutura em relação a listas simplesmente ligadas e apontar cuidados que devemos ter, como o gerenciamento correto de memória e a atualização dos ponteiros.

Estrutura

Uma lista duplamente ligada é composta por nós que contêm três campos: um dado (por exemplo, um inteiro), um ponteiro para o nó seguinte e um ponteiro para o nó anterior. Em C, definimos uma estrutura (struct) para representar o nó e uma variável ponteiro para o primeiro nó (cabeça) e, opcionalmente, para o último nó (cauda).

A estrutura básica é a seguinte:

typedef struct Node {
    int data;               // dado armazenado
    struct Node* prev;      // ponteiro para o nó anterior
    struct Node* next;      // ponteiro para o próximo nó
} Node;

// Ponteiros para controlar a lista
Node* head = NULL;  // primeiro nó
Node* tail = NULL;  // último nó (opcional, mas útil)

Inicialmente, a lista está vazia, e tanto head quanto tail apontam para NULL. Cada novo nó é alocado dinamicamente com malloc e, ao ser inserido, devemos ajustar os ponteiros prev e next dos nós vizinhos para manter a integridade da lista.

Operações

As operações básicas em listas duplamente ligadas incluem: inserção (no início, no fim, em posição específica), remoção (por valor ou posição), busca, impressão em ambas as direções e liberação da memória. Cada operação requer cuidado especial com os ponteiros.

Inserção no início: Criamos um novo nó, ajustamos seu next para o antigo head, o prev do antigo head para o novo nó, e atualizamos head. Se a lista estava vazia, tail também deve ser atualizado.

void insertAtBeginning(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = head;
    if (head != NULL) {
        head->prev = newNode;
    } else {
        tail = newNode;  // se estava vazia, tail também é o novo nó
    }
    head = newNode;
}

Inserção no fim: Criamos um novo nó, ajustamos o prev para o antigo tail, o next para NULL, e atualizamos tail. Se a lista estiver vazia, head também deve ser atualizado.

void insertAtEnd(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = tail;
    if (tail != NULL) {
        tail->next = newNode;
    } else {
        head = newNode;  // se estava vazia, head também é o novo nó
    }
    tail = newNode;
}

Remoção de um nó específico: Precisamos localizar o nó (por valor ou posição) e ajustar os ponteiros dos vizinhos. Se o nó é o head, atualizamos head; se é o tail, atualizamos tail; e liberamos a memória com free.

void deleteNode(Node* node) {
    if (node == NULL) return;
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        head = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        tail = node->prev;
    }
    free(node);
}

Busca: Percorremos a lista a partir do head (ou tail) até encontrar o valor desejado, retornando o ponteiro para o nó ou NULL se não encontrado.

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

Impressão: Podemos imprimir do início ao fim ou do fim ao início, aproveitando os ponteiros next e prev.

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

void printBackward() {
    Node* current = tail;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

Vantagens

As listas duplamente ligadas oferecem várias vantagens sobre as listas simplesmente ligadas:

  • Navegação bidirecional: É possível percorrer a lista em ambas as direções, o que facilita operações como impressão reversa e busca em qualquer direção.
  • Inserção e remoção eficientes em ambas as extremidades: Com um ponteiro para a cauda (tail), podemos inserir ou remover no final com complexidade O(1), o que não é possível em listas simplesmente ligadas sem percorrer toda a lista.
  • Remoção de um nó conhecido sem percorrer a lista: Dado um ponteiro para o nó, podemos removê-lo em O(1), pois temos acesso ao nó anterior.
  • Facilidade em algoritmos que exigem retrocesso: Por exemplo, em editores de texto ou navegadores, onde precisamos percorrer histórico para frente e para trás.

Essas vantagens tornam as listas duplamente ligadas ideais para implementar estruturas como deques (filas duplas) e certos tipos de caches.

Cuidados

Apesar das vantagens, as listas duplamente ligadas exigem atenção em alguns pontos:

  • Gerenciamento de memória: Cada nó é alocado dinamicamente, então é imprescindível liberar a memória de todos os nós ao final, percorrendo a lista e usando free.
  • Atualização correta dos ponteiros: Erros ao ajustar prev e next podem corromper a lista. Sempre verifique os casos especiais (lista vazia, primeiro nó, último nó).
  • Não esquecer de inicializar os ponteiros: Ao criar um novo nó, defina prev e next para NULL antes de inserir.
  • Evitar acesso a ponteiros NULL: Antes de acessar prev ou next, verifique se o nó não é NULL.
  • Complexidade de implementação: O código tende a ser mais complexo que o de listas simplesmente ligadas, aumentando a chance de bugs. Teste cada operação isoladamente.

Uma boa prática é encapsular as operações em funções e manter a lista sempre consistente, mesmo em caso de erro.

Boas Práticas

Para evitar problemas, recomenda-se:

  • Sempre use funções para inserir, remover e buscar, em vez de manipular diretamente os ponteiros.
  • Ao remover um nó, guarde o ponteiro para o próximo antes de liberar a memória, se necessário.
  • Considere usar um nó sentinela (dummy) para simplificar a lógica de inserção e remoção nas extremidades.
  • Teste a lista com casos de borda: lista vazia, um único nó, inserção/remoção no início e no fim.
  • Libere toda a memória alocada antes de encerrar o programa, para evitar vazamentos.

Exercícios

  1. Implemente uma função insertAtPosition(int data, int pos) que insere um novo nó em uma posição específica (0-indexada). Considere que a posição pode ser 0 (início), o tamanho da lista (fim) ou qualquer posição válida. Teste com uma lista de exemplo.

    ✓ Resposta: 
    void insertAtPosition(int data, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if (pos == 0) {
        insertAtBeginning(data);
        free(newNode); // pois insertAtBeginning já alocou
        return;
    }
    // Percorrer até a posição
    Node* current = head;
    for (int i = 0; current != NULL && i < pos - 1; i++) {
        current = current->next;
    }
    if (current == NULL) {
        // posição maior que o tamanho, insere no fim
        insertAtEnd(data);
        free(newNode);
        return;
    }
    // Ajustar ponteiros
    newNode->next = current->next;
    newNode->prev = current;
    if (current->next != NULL) {
        current->next->prev = newNode;
    } else {
        tail = newNode;
    }
    current->next = newNode;
}

  2. Escreva uma função deleteByValue(int value) que remove o primeiro nó que contém o valor dado. Retorne 1 se removeu, 0 caso contrário.

    ✓ Resposta: 
    int deleteByValue(int value) {
    Node* node = search(value);
    if (node == NULL) return 0;
    deleteNode(node);
    return 1;
}

  3. Crie uma função countNodes() que retorna o número de nós na lista. Use um loop e retorne o total.

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

  4. Implemente uma função reverseList() que inverte a ordem dos nós da lista duplamente ligada, sem alocar novos nós. Dica: troque os ponteiros prev e next de cada nó e atualize head e tail.

    ✓ Resposta: 
    void reverseList() {
    Node* current = head;
    Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev; // move para o próximo original
    }
    // Atualizar head e tail
    if (temp != NULL) {
        head = temp->prev; // temp é o último nó processado, que agora é o primeiro
        tail = current;    // current é NULL, então usamos temp?
        // Na prática, após o loop, head deve ser o antigo tail.
        // Vamos corrigir: o antigo tail é o último nó processado.
        // Podemos guardar o antigo tail antes de começar.
    }
}
// Implementação correta:
void reverseList() {
    Node* current = head;
    Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev; // agora prev aponta para o próximo original
    }
    // Após o loop, temp aponta para o último nó processado (antigo tail)
    if (temp != NULL) {
        head = temp->prev; // temp->prev é o antigo head? Não, temp é o último nó, e temp->prev é o novo next (NULL?)
        // Melhor: trocar head e tail diretamente.
        temp = head;
        head = tail;
        tail = temp;
    }
}

  5. Escreva uma função freeList() que libera toda a memória alocada para a lista, percorrendo e dando free em cada nó. Após a liberação, ajuste head e tail para NULL.

    ✓ Resposta: 
    void freeList() {
    Node* current = head;
    while (current != NULL) {
        Node* next = current->next;
        free(current);
        current = next;
    }
    head = NULL;
    tail = NULL;
}

Referências