用 C 语言实现双向链表

CCBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

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

👀 预览

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

🎯 任务

在这个项目中,你将学习:

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

🏆 成果

完成这个项目后,你将能够:

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

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL c(("C")) -.-> c/CompoundTypesGroup(["Compound Types"]) c(("C")) -.-> c/PointersandMemoryGroup(["Pointers and Memory"]) c(("C")) -.-> c/ControlFlowGroup(["Control Flow"]) c/ControlFlowGroup -.-> c/while_loop("While Loop") c/CompoundTypesGroup -.-> c/structures("Structures") c/PointersandMemoryGroup -.-> c/pointers("Pointers") c/PointersandMemoryGroup -.-> c/memory_address("Memory Address") subgraph Lab Skills c/while_loop -.-> lab-301499{{"用 C 语言实现双向链表"}} c/structures -.-> lab-301499{{"用 C 语言实现双向链表"}} c/pointers -.-> lab-301499{{"用 C 语言实现双向链表"}} c/memory_address -.-> lab-301499{{"用 C 语言实现双向链表"}} end

修复段错误

在这一步中,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. 然后,该函数应更新新节点以及前一个节点的 nextprev 指针,以正确插入新节点。
  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;
    }
}
  1. 找到 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. 然后,该函数应更新新节点以及下一个节点的 nextprev 指针,以正确插入新节点。
  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;
    }
}
  1. 找到 insert_before (list, NULL, data); 并将其更改为以下代码:
insert_before (list, list->head, data);

从双向链表中删除节点

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

  1. list.c 文件中找到 delete_from() 函数。
  2. 该函数接受一个 struct List* 和一个 struct Node*(要删除的节点)。
  3. 该函数应更新相邻节点的 nextprev 指针,以便从链表中移除给定节点。
  4. 如果被删除的节点是链表的 headtail,该函数还应更新 headtail 指针。
  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 中练习更多实验来提升你的技能。