Implementar Lista Duplamente Encadeada em C | Tutorial de Programação

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.

Localize a função free_list() no arquivo list.c.
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.

Localize a função insert_after() no arquivo list.c.
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ó.
A função deve criar um novo struct Node e inicializar seu campo data com os dados fornecidos.
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.
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;
    }
}

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.

Localize a função insert_before() no arquivo list.c.
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ó.
A função deve criar um novo struct Node e inicializar seu campo data com os dados fornecidos.
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.
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;
    }
}

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.

Localize a função delete_from() no arquivo list.c.
Esta função recebe um struct List* e um struct Node* (o nó a ser excluído).
A função deve atualizar os ponteiros next e prev dos nós vizinhos para remover o nó dado da lista.
A função também deve atualizar os ponteiros head e tail se o nó excluído era o head ou tail da lista.
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.

Implementando Lista Duplamente Encadeada em C