用 C 语言实现双向链表

简介

在这个项目中，你将学习如何在C语言中实现双向链表数据结构。双向链表是一种链表类型，其中每个节点都包含指向前驱节点和后继节点的指针，允许在两个方向上进行高效遍历。

👀 预览

$ gcc test_list.c list.c -o test
$./test
欢迎
来到
LabEx
在线

🎯 任务

在这个项目中，你将学习：

• 如何初始化双向链表
• 如何遍历双向链表并为每个节点执行回调函数
• 如何在双向链表中的给定节点之后插入新节点
• 如何在双向链表中的给定节点之前插入新节点
• 如何从双向链表中删除节点

🏆 成果

完成这个项目后，你将能够：

• 理解双向链表的基本结构和操作
• 实现管理双向链表所需的核心函数
• 展示在C语言中使用指针和动态内存分配的能力
• 应用你的知识来修复和改进提供的双向链表实现

Skills Graph

修复段错误

在这一步中，free_list 函数在释放节点后没有更新 current 指针，这将导致段错误。现在需要修复这个问题。

1. 在 list.c 文件中找到 free_list() 函数。
2. 以下是更新后的 free_list() 函数：

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

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

在给定节点之后插入节点

在这一步中，你将学习如何在双向链表的给定节点之后插入一个新节点。

1. 在 list.c 文件中找到 insert_after() 函数。
2. 该函数接受一个 struct List*、一个 struct Node*（要在其之后插入新节点的节点）以及新节点的 data。
3. 该函数应创建一个新的 struct Node 并使用提供的 data 初始化其 data 字段。
4. 然后，该函数应更新新节点以及前一个节点的 next 和 prev 指针，以正确插入新节点。
5. 最后，如果新节点是在链表末尾插入的，该函数应更新 tail 指针。

以下是更新后的 insert_after() 函数：

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) { // 更新
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // 更新
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // 更新
        list->head = newnode;
    }
}

6. 找到 insert_after (list, NULL, data); 并将其更改为以下代码：

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

在给定节点之前插入节点

在这一步中，你将学习如何在双向链表的给定节点之前插入一个新节点。

1. 在 list.c 文件中找到 insert_before() 函数。
2. 该函数接受一个 struct List*、一个 struct Node*（要在其之前插入新节点的节点）以及新节点的 data。
3. 该函数应创建一个新的 struct Node 并使用提供的 data 初始化其 data 字段。
4. 然后，该函数应更新新节点以及下一个节点的 next 和 prev 指针，以正确插入新节点。
5. 最后，如果新节点是在链表开头插入的，该函数应更新 head 指针。

以下是更新后的 insert_before() 函数：

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) { // 更新
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // 更新
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // 更新
        list->tail = newnode;
    }
}

6. 找到 insert_before (list, NULL, data); 并将其更改为以下代码：

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

从双向链表中删除节点

在这一步中，你将学习如何从双向链表中删除节点。

1. 在 list.c 文件中找到 delete_from() 函数。
2. 该函数接受一个 struct List* 和一个 struct Node*（要删除的节点）。
3. 该函数应更新相邻节点的 next 和 prev 指针，以便从链表中移除给定节点。
4. 如果被删除的节点是链表的 head 或 tail，该函数还应更新 head 和 tail 指针。
5. 最后，该函数应释放被删除节点占用的内存。

以下是更新后的 delete_from() 函数：

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

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

    free(node);
}

现在，list.c 文件中的双向链表实现应该可以正常工作了。你可以使用提供的 test_list.c 文件来测试双向链表的功能。测试结果如下：

$ gcc test_list.c list.c -o test
$./test
欢迎
来到
LabEx
在线

总结

恭喜你！你已经完成了这个项目。你可以在 LabEx 中练习更多实验来提升你的技能。