0Pricing
C Academy · 课时

单向链表

节点与指针

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

什么是链表

链表是一串称为节点的小型结构体。每个节点保存一个值和一个指向下一个节点的指针。

与数组不同，链表元素不必在内存中连续存放，而且链表可以轻松增长或缩小。

#include <stdio.h>

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

int main(void) {
    printf("A node holds a value and a next pointer\n");
    return 0;
}

定义节点

节点结构体包含数据，以及一个指向后续节点的 struct Node *next。

该指针类型引用同一个结构体，这正是链条能够连接起来的方式。

#include <stdio.h>

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

int main(void) {
    struct Node n;
    n.value = 42;
    n.next = NULL;
    printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
    return 0;
}

头指针

链表由一个指向第一个节点的指针标识，这个节点称为头节点。

空链表就是头指针等于 NULL。

#include <stdio.h>

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

int main(void) {
    struct Node *head = NULL;
    printf("List is empty: %d\n", head == NULL);
    return 0;
}

分配节点

节点通常使用 malloc 在堆上创建，这样它们的生命周期就能超出创建它们的函数。

请始终检查返回值，并记得稍后释放节点。

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

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

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

箭头运算符

当您拥有一个指向结构体的指针时，请使用 -> 访问成员。n->value 与 (*n).value 含义相同。

使用链表时，您会经常使用箭头运算符。

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

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

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

连接两个节点

要连接节点，请将第一个节点的 next 设置为指向第二个节点。最后一个节点的 next 保持为 NULL，以标记结尾。

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

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

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

创建节点的辅助函数

反复分配内存很繁琐，因此可以将它封装到一个辅助函数中，由该函数分配、初始化并返回新节点。

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

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

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

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

构建一个小型链表

使用辅助函数，通过链接 next 指针构建一个包含三个节点的链表 1 -> 2 -> 3。

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

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

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

打印链表

要打印每个值，请从头节点开始，沿着 next 指针前进，直到到达 NULL。

这种遍历模式是几乎所有链表操作的基础。

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

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

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

数组与链表

数组支持快速的索引访问，但大小固定。链表便于插入和删除，但访问速度较慢（必须遍历才能到达某个元素）。

请根据程序中占主导地位的操作来选择数据结构。

#include <stdio.h>

int main(void) {
    printf("Array: O(1) index, costly resize\n");
    printf("List:  O(n) index, cheap insert/delete\n");
    return 0;
}

释放整个链表

每个通过 malloc 分配的节点都必须释放。遍历链表时，请在释放每个节点之前保存下一个指针，否则链表的其余部分就会丢失。

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

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

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) {
        struct Node *nxt = p->next;
        free(p);
        p = nxt;
    }
    printf("freed all nodes\n");
    return 0;
}

快速检查

测试您对链表结构的理解。

回顾

您学习了单向链表的基础知识：

  • 节点保存一个值和一个 next 指针；头指针指向第一个节点。
  • 使用 malloc 分配节点，并通过 -> 访问成员。
  • 最后一个节点的 next 是 NULL；通过跟随指针遍历链表。
  • 始终释放每个节点，并在释放前保存 next。

常见问题解答

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

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

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

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

学习 C Academy 需要有经验吗？

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

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

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

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

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

此课程中的所有课时

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