Listas duplamente ligadas

Nesta aula, você aprenderá sobre listas duplamente ligadas em C, uma estrutura de dados que permite percorrer a lista em ambas as direções. Abordaremos sua estrutura, operações básicas, vantagens e cuidados importantes, com exemplos práticos de código.

As listas duplamente ligadas são uma evolução das listas simplesmente ligadas, onde cada nó possui dois ponteiros: um para o próximo nó e outro para o nó anterior. Essa característica permite percorrer a lista em ambas as direções, facilitando operações como remoção de um nó conhecido sem precisar percorrer a lista para encontrar o anterior, e também permite implementar estruturas como deques (filas duplas). Nesta aula, vamos explorar como definir, manipular e usar listas duplamente ligadas em C, com foco em implementação prática e boas práticas.

Antes de começarmos, é importante que você já tenha familiaridade com ponteiros, alocação dinâmica de memória e listas simplesmente ligadas. Caso não se sinta confortável, revise esses tópicos antes de prosseguir. A compreensão sólida desses conceitos é essencial para aproveitar ao máximo esta aula.

Estrutura

Uma lista duplamente ligada é composta por nós, onde cada nó contém três campos: o dado (ou valor), um ponteiro para o nó seguinte (next) e um ponteiro para o nó anterior (prev). A lista em si é geralmente representada por um ponteiro para o primeiro nó (head) e, opcionalmente, um ponteiro para o último nó (tail) para facilitar operações no final.

Em C, definimos a estrutura do nó usando struct. Vamos criar um exemplo para armazenar números inteiros:

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

// Estrutura do nó
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Estrutura da lista (opcional, mas facilita o gerenciamento)
typedef struct {
    Node* head;
    Node* tail;
    int size;
} DoublyLinkedList;

Note que usamos typedef para simplificar a referência à estrutura. A lista em si contém ponteiros para o primeiro e último nó, além de um contador de tamanho, o que torna muitas operações mais eficientes. No entanto, é possível trabalhar apenas com o ponteiro para o head, como fazíamos nas listas simples, mas a presença do tail facilita inserções no final e remoções no final em tempo constante.

É importante inicializar a lista corretamente. Vamos criar uma função de inicialização:

// Inicializa a lista vazia
void initList(DoublyLinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

Com essa estrutura, podemos começar a implementar as operações.

Operações

As operações básicas em uma lista duplamente ligada incluem: inserção no início, no final e em uma posição específica; remoção de um nó por valor ou por posição; busca; e percurso em ambas as direções. Vamos implementar as principais.

Primeiro, vamos criar uma função para criar um novo nó:

// Cria um novo nó com o dado fornecido
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->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Agora, as funções de inserção:

// Inserção no início
void insertAtBeginning(DoublyLinkedList* list, int data) {
    Node* newNode = createNode(data);
    if (list->head == NULL) {
        // Lista vazia
        list->head = newNode;
        list->tail = newNode;
    } else {
        newNode->next = list->head;
        list->head->prev = newNode;
        list->head = newNode;
    }
    list->size++;
}

// Inserção no final
void insertAtEnd(DoublyLinkedList* list, int data) {
    Node* newNode = createNode(data);
    if (list->tail == NULL) {
        // Lista vazia
        list->head = newNode;
        list->tail = newNode;
    } else {
        newNode->prev = list->tail;
        list->tail->next = newNode;
        list->tail = newNode;
    }
    list->size++;
}

// Inserção em posição específica (índice baseado em 0)
void insertAtPosition(DoublyLinkedList* list, int data, int position) {
    if (position < 0 || position > list->size) {
        printf("Posição inválida\n");
        return;
    }
    if (position == 0) {
        insertAtBeginning(list, data);
        return;
    }
    if (position == list->size) {
        insertAtEnd(list, data);
        return;
    }
    // Percorrer até a posição
    Node* current = list->head;
    for (int i = 0; i < position; i++) {
        current = current->next;
    }
    Node* newNode = createNode(data);
    newNode->prev = current->prev;
    newNode->next = current;
    current->prev->next = newNode;
    current->prev = newNode;
    list->size++;
}

Para a remoção, temos que tomar cuidado para atualizar corretamente os ponteiros. Vamos implementar a remoção do primeiro nó, do último nó e de um nó com valor específico:

// Remove o primeiro nó
int removeFromBeginning(DoublyLinkedList* list) {
    if (list->head == NULL) {
        printf("Lista vazia\n");
        return -1;
    }
    Node* temp = list->head;
    int data = temp->data;
    list->head = list->head->next;
    if (list->head != NULL) {
        list->head->prev = NULL;
    } else {
        list->tail = NULL;
    }
    free(temp);
    list->size--;
    return data;
}

// Remove o último nó
int removeFromEnd(DoublyLinkedList* list) {
    if (list->tail == NULL) {
        printf("Lista vazia\n");
        return -1;
    }
    Node* temp = list->tail;
    int data = temp->data;
    list->tail = list->tail->prev;
    if (list->tail != NULL) {
        list->tail->next = NULL;
    } else {
        list->head = NULL;
    }
    free(temp);
    list->size--;
    return data;
}

// Remove um nó com valor específico (primeira ocorrência)
int removeByValue(DoublyLinkedList* list, int value) {
    Node* current = list->head;
    while (current != NULL) {
        if (current->data == value) {
            // Ajusta os ponteiros dos vizinhos
            if (current->prev != NULL) {
                current->prev->next = current->next;
            } else {
                list->head = current->next;
            }
            if (current->next != NULL) {
                current->next->prev = current->prev;
            } else {
                list->tail = current->prev;
            }
            int data = current->data;
            free(current);
            list->size--;
            return data;
        }
        current = current->next;
    }
    printf("Valor não encontrado\n");
    return -1;
}

Além disso, é comum implementar funções para percorrer a lista (imprimir) e para liberar a memória. Vamos ver:

// Imprime a lista do início ao fim
void printForward(DoublyLinkedList* list) {
    Node* current = list->head;
    printf("Lista (forward): ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// Imprime a lista do fim ao início
void printBackward(DoublyLinkedList* list) {
    Node* current = list->tail;
    printf("Lista (backward): ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

// Libera toda a memória alocada
void freeList(DoublyLinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

Um exemplo de uso dessas funções:

int main() {
    DoublyLinkedList list;
    initList(&list);
    
    insertAtEnd(&list, 10);
    insertAtEnd(&list, 20);
    insertAtBeginning(&list, 5);
    insertAtPosition(&list, 15, 2);
    
    printForward(&list);  // Lista (forward): 5 10 15 20
    printBackward(&list); // Lista (backward): 20 15 10 5
    
    removeByValue(&list, 15);
    printForward(&list);  // Lista (forward): 5 10 20
    
    freeList(&list);
    return 0;
}

Vantagens

As listas duplamente ligadas oferecem várias vantagens sobre as listas simplesmente ligadas. A principal é a capacidade de percorrer a lista em ambas as direções, o que facilita operações como remoção de um nó conhecido sem precisar percorrer a lista para encontrar o nó anterior. Isso reduz a complexidade de tempo para remoção de O(n) para O(1) quando já temos o ponteiro para o nó.

Outra vantagem é a possibilidade de implementar estruturas de dados como deques (filas duplas) com eficiência, onde inserções e remoções podem ser feitas tanto no início quanto no final em tempo constante. Além disso, a presença do ponteiro tail facilita operações no final da lista, como inserir ou remover no final, sem precisar percorrer toda a lista.

Em comparação com arrays, as listas duplamente ligadas permitem inserções e remoções em qualquer posição sem a necessidade de deslocar elementos, o que pode ser mais eficiente em cenários com muitas modificações. Elas também não têm um tamanho fixo, pois a memória é alocada dinamicamente por nó.

Cuidados

Apesar das vantagens, as listas duplamente ligadas exigem cuidados especiais na implementação para evitar erros comuns. Um dos principais cuidados é a atualização correta dos ponteiros prev e next ao inserir ou remover nós. Um erro comum é esquecer de atualizar o ponteiro prev do nó seguinte ou o ponteiro next do nó anterior, o que pode corromper a lista e causar falhas de segmentação.

Outro cuidado é com a alocação e liberação de memória. Sempre devemos liberar a memória dos nós removidos usando free() para evitar vazamentos de memória. Da mesma forma, ao liberar a lista inteira, devemos percorrer todos os nós e liberá-los individualmente, tomando cuidado para não acessar memória já liberada.

Também é importante verificar se a lista está vazia antes de tentar acessar o primeiro ou último nó. Em operações como removeFromBeginning ou removeFromEnd, devemos verificar se a lista não está vazia antes de acessar os ponteiros. Além disso, ao remover um nó que é o único elemento, devemos atualizar tanto head quanto tail para NULL.

Por fim, ao trabalhar com listas duplamente ligadas, é essencial manter a consistência do campo size, se estiver usando, para que as operações de inserção em posição específica funcionem corretamente. Sempre incrementamos ou decrementamos o tamanho após cada operação de inserção ou remoção.

Boas práticas

Para escrever código robusto, é recomendável encapsular todas as operações em funções que recebam a lista por ponteiro, como fizemos. Isso torna o código mais modular e fácil de testar. Além disso, sempre que possível, use typedef para simplificar os tipos e evite repetir struct em todo o código.

Outra boa prática é incluir verificações de erro, como verificar se a alocação de memória foi bem-sucedida e se as posições são válidas. Isso ajuda a identificar problemas precocemente e torna o código mais confiável.

Por fim, considere a possibilidade de usar listas duplamente ligadas apenas quando a necessidade de percorrer em ambas as direções for real. Se a aplicação só precisa percorrer em uma direção, uma lista simplesmente ligada pode ser mais econômica em termos de memória, pois cada nó ocupa menos espaço (apenas um ponteiro a menos).

Referências

Exercícios

Implemente uma função que receba uma lista duplamente ligada e retorne o número de nós (tamanho) sem usar o campo size. Compare com o campo size para verificar se estão consistentes.

✓ Resposta:

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

Escreva uma função que insira um novo nó em uma posição específica, mas sem usar o campo size. A função deve verificar se a posição é válida percorrendo a lista.

✓ Resposta:

void insertAtPositionNoSize(DoublyLinkedList* list, int data, int position) {
    if (position < 0) {
        printf("Posição inválida\n");
        return;
    }
    if (position == 0) {
        insertAtBeginning(list, data);
        return;
    }
    Node* current = list->head;
    int i = 0;
    while (current != NULL && i < position) {
        current = current->next;
        i++;
    }
    if (current == NULL && i < position) {
        printf("Posição inválida\n");
        return;
    }
    if (current == NULL) { // inserir no final
        insertAtEnd(list, data);
        return;
    }
    Node* newNode = createNode(data);
    newNode->prev = current->prev;
    newNode->next = current;
    if (current->prev != NULL) {
        current->prev->next = newNode;
    } else {
        list->head = newNode;
    }
    current->prev = newNode;
    list->size++; // mantemos size por consistência, mas não usamos para validar
}

Crie uma função que inverta a ordem dos nós de uma lista duplamente ligada, trocando os ponteiros prev e next de cada nó e atualizando head e tail.

✓ Resposta:

void reverseList(DoublyLinkedList* list) {
    Node* current = list->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 nó original (agora prev)
    }
    // Atualiza head e tail
    temp = list->head;
    list->head = list->tail;
    list->tail = temp;
}

Implemente uma função que concatene duas listas duplamente ligadas, ou seja, anexe a segunda lista ao final da primeira. A função deve modificar a primeira lista e esvaziar a segunda.

✓ Resposta:

void concatenateLists(DoublyLinkedList* list1, DoublyLinkedList* list2) {
    if (list2->head == NULL) return; // nada a concatenar
    if (list1->head == NULL) {
        // lista1 vazia, copia os ponteiros
        list1->head = list2->head;
        list1->tail = list2->tail;
    } else {
        // conecta o final da lista1 com o início da lista2
        list1->tail->next = list2->head;
        list2->head->prev = list1->tail;
        list1->tail = list2->tail;
    }
    list1->size += list2->size;
    // esvazia a lista2
    list2->head = NULL;
    list2->tail = NULL;
    list2->size = 0;
}

Escreva uma função que remova todos os nós que contêm um valor específico da lista duplamente ligada. A função deve retornar o número de nós removidos.

✓ Resposta:

int removeAllByValue(DoublyLinkedList* list, int value) {
    int count = 0;
    Node* current = list->head;
    while (current != NULL) {
        Node* next = current->next;
        if (current->data == value) {
            // remove o nó current
            if (current->prev != NULL) {
                current->prev->next = current->next;
            } else {
                list->head = current->next;
            }
            if (current->next != NULL) {
                current->next->prev = current->prev;
            } else {
                list->tail = current->prev;
            }
            free(current);
            list->size--;
            count++;
        }
        current = next;
    }
    return count;
}

Listas duplamente ligadas

Estrutura

Operações

Vantagens

Cuidados

Boas práticas

Referências

Exercícios

Mais desta categoria

Argumentos de linha de comando

Listas ligadas

Programação genérica com void*