Implementando Lista Duplamente Encadeada em C

Introdução

Neste projeto, você aprenderá como implementar uma estrutura de dados de lista duplamente encadeada em C. Uma lista duplamente encadeada é um tipo de lista encadeada onde cada nó contém ponteiros para seus nós predecessores e sucessores, permitindo uma travessia eficiente em ambas as direções, para frente e para trás.

👀 Pré-visualização

$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online

🎯 Tarefas

Neste projeto, você aprenderá:

• Como inicializar uma lista duplamente encadeada
• Como percorrer a lista duplamente encadeada e executar uma função de callback para cada nó
• Como inserir um novo nó após um determinado nó na lista duplamente encadeada
• Como inserir um novo nó antes de um determinado nó na lista duplamente encadeada
• Como deletar um nó da lista duplamente encadeada

🏆 Conquistas

Após concluir este projeto, você será capaz de:

• Compreender a estrutura básica e as operações de uma lista duplamente encadeada
• Implementar as funções principais necessárias para gerenciar uma lista duplamente encadeada
• Demonstrar a capacidade de trabalhar com ponteiros e alocação dinâmica de memória em C
• Aplicar seu conhecimento para corrigir e aprimorar a implementação da lista duplamente encadeada fornecida

Corrigindo Falhas de Segmentação

Nesta etapa, a função free_list não atualiza o ponteiro current após liberar um nó, o que resultará em uma falha de segmentação. O problema precisa ser corrigido agora.

1. Localize a função free_list() no arquivo list.c.
2. Aqui está a função free_list() atualizada:

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // Atualizado
    }
    free(list);
}

Inserir um Nó Após um Nó Dado

Nesta etapa, você aprenderá como inserir um novo nó após um nó dado na lista duplamente encadeada.

1. Localize a função insert_after() no arquivo list.c.
2. Esta função recebe um struct List*, um struct Node* (o nó após o qual inserir o novo nó) e os dados para o novo nó.
3. A função deve criar um novo struct Node e inicializar seu campo data com os dados fornecidos.
4. A função deve então atualizar os ponteiros next e prev do novo nó e do nó prev para inserir o novo nó corretamente.
5. Finalmente, a função deve atualizar o ponteiro tail se o novo nó estiver sendo inserido no final da lista.

Aqui está a função insert_after() atualizada:

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // Atualizado
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Atualizado
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Atualizado
        list->head = newnode;
    }
}

6. Localize insert_after (list, NULL, data); e altere para o seguinte código:

insert_after (list, list->tail, data);

Inserir um Nó Antes de um Nó Dado

Nesta etapa, você aprenderá como inserir um novo nó antes de um nó dado na lista duplamente encadeada.

1. Localize a função insert_before() no arquivo list.c.
2. Esta função recebe um struct List*, um struct Node* (o nó antes do qual inserir o novo nó) e os dados para o novo nó.
3. A função deve criar um novo struct Node e inicializar seu campo data com os dados fornecidos.
4. A função deve então atualizar os ponteiros next e prev do novo nó e do nó next para inserir o novo nó corretamente.
5. Finalmente, a função deve atualizar o ponteiro head se o novo nó estiver sendo inserido no início da lista.

Aqui está a função insert_before() atualizada:

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // Atualizado
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Atualizado
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Atualizado
        list->tail = newnode;
    }
}

6. Localize insert_before (list, NULL, data); e altere para o seguinte código:

insert_before (list, list->head, data);

Remover um Nó da Lista Duplamente Ligada

Nesta etapa, você aprenderá como excluir um nó da lista duplamente encadeada.

1. Localize a função delete_from() no arquivo list.c.
2. Esta função recebe um struct List* e um struct Node* (o nó a ser excluído).
3. A função deve atualizar os ponteiros next e prev dos nós vizinhos para remover o nó dado da lista.
4. A função também deve atualizar os ponteiros head e tail se o nó excluído era o head ou tail da lista.
5. Finalmente, a função deve liberar a memória ocupada pelo nó excluído.

Aqui está a função delete_from() atualizada:

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // Atualizado

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Atualizado

    free(node);
}

Agora, a implementação da lista duplamente encadeada no arquivo list.c deve estar funcionando corretamente. Você pode usar o arquivo test_list.c fornecido para testar a funcionalidade da lista duplamente encadeada. Os resultados do teste são os seguintes:

$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online

Resumo

Parabéns! Você concluiu este projeto. Você pode praticar mais laboratórios no LabEx para aprimorar suas habilidades.