PricingLoginStart free
C Academy · 课时

双向链表

双向链接

第 4 / 4 课13 个步骤

双向链表 是 CoddyKit 上的免费 C Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

双向链接

双向链表为每个节点提供两个指针：一个指向 next 节点，另一个指向 prev（前一个）节点。

这样，您可以沿两个方向遍历链表，也能更轻松地执行删除操作。

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

定义节点

该结构体在 next 旁边增加了一个 prev 指针。在链表的两端，这两个指针都是 NULL。

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

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

创建辅助函数

和之前一样，辅助函数将分配操作集中处理。它会将 prev 和 next 都设置为 NULL。

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

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

双向连接节点

连接两个节点时，必须更新两个方向：第一个节点的 next 和第二个节点的 prev。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

在开头插入

将节点插入开头时：新节点的 next 指向旧头节点，旧头节点的 prev 指向新节点，然后将头指针移到新节点。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    if (*head) (*head)->prev = n;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 2); push(&head, 1);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

向前遍历

向前遍历与单向链表完全相同：沿着 next 访问，直到遇到 NULL。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

向后遍历

双向链表的主要优势是：从任意节点出发，都可以沿着 prev 指针向后遍历，直到到达头节点。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

删除更加容易

由于每个节点都知道它的前驱节点，因此无需搜索前一个节点即可将其删除。

只需在两个方向上将 node->prev 与 node->next 连接起来。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next=b; b->prev=a; b->next=c; c->prev=b;
    struct Node *head = a;
    del(&head, b);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

更新两个相邻节点

删除节点时，始终要修复前一个节点的 next以及后一个节点的 prev。

请在每一端检查 NULL，避免对不存在的相邻节点进行解引用。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

保存尾指针

许多双向链表还会保存一个指向最后一个节点的尾指针，从而支持 O(1) 追加，以及从末尾向后遍历。

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1), *tail = head;
    struct Node *n = make(2);
    tail->next = n; n->prev = tail; tail = n;
    printf("tail = %d\n", tail->value);
    free(head); free(n);
    return 0;
}

权衡

双向链表会占用额外内存（每个节点多一个指针），并且每次修改都需要更新两个链接。

作为回报，您可以双向遍历，并以 O(1) 的复杂度删除已知节点。请根据需求进行选择。

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

快速检查

测试您对双向链表的理解。

在交互式课程中回答

回顾

您学习了双向链表：

  • 每个节点都同时拥有 prev 和 next 指针。
  • 连接节点时需要更新两个方向。
  • 您可以向前和向后遍历，并以 O(1) 的复杂度删除已知节点。
  • 代价是额外的内存和更多的指针更新；使用尾指针可以实现 O(1) 追加。
免费开始

用 AI 导师学习 C — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程
39
课程
144
免费开始学习查看完整课程

常见问题解答

「双向链表」课时是免费的吗？

是的 — 「双向链表」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「双向链表」这节课中我会学到什么？

双向链接 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「双向链表」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 单向链表
  2. 插入与删除
  3. 遍历与搜索
  4. 双向链表
← 返回 C Academy