0Pricing
C Academy · 课时

插入与删除

修改链表

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

修改链表

链表的优势在于插入和删除的成本较低。您只需重新排列指针，而不必像操作数组那样移动元素。

本课将介绍如何在不同位置插入和删除节点。

#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(2);
    printf("start: %d\n", head->value);
    free(head);
    return 0;
}

在开头插入

在头部插入的复杂度是 O(1)。创建一个新节点，让它的 next 指向当前头指针，然后将头指针更新为这个新节点。

#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(2);
    struct Node *fresh = make(1);
    fresh->next = head;
    head = fresh;
    printf("%d -> %d\n", head->value, head->next->value);
    return 0;
}

为什么要传递二级指针

要在函数内部修改头指针，您必须传递它的地址：struct Node **。

否则，函数只能修改一个局部副本，调用者中的头指针不会改变。

#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;}

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

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

在末尾插入

追加元素需要遍历到最后一个节点，然后将新节点连接到它的 next 上。

如果链表为空，新节点就会成为头指针所指的节点。

#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;}

void append(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head) { *head = n; return; }
    struct Node *p = *head;
    while (p->next) p = p->next;
    p->next = n;
}

int main(void) {
    struct Node *head = NULL;
    append(&head, 1); append(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    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*n);n->value=v;n->next=NULL;return n;}

void insert_after(struct Node *node, int v) {
    struct Node *n = make(v);
    n->next = node->next;
    node->next = n;
}

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

操作顺序很重要

接入节点时，始终要在修改前一个节点的 next之前，先设置新节点的 next。

如果顺序相反，您就会丢失指向链表其余部分的引用。

#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 *a = make(1), *c = make(3);
    a->next = c;
    struct Node *b = make(2);
    b->next = a->next;
    a->next = b;
    printf("%d %d %d\n", a->value, b->value, c->value);
    return 0;
}

删除第一个节点

删除头节点时，需要先保存它，将头指针移到 head->next，然后释放旧的头节点。

#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;}

void pop(struct Node **head) {
    if (!*head) return;
    struct Node *old = *head;
    *head = old->next;
    free(old);
}

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

按值删除

要删除具有指定值的节点，请跟踪前一个节点，以便通过设置 prev->next = target->next 来跳过目标节点。

#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;}

void del(struct Node **head, int v) {
    struct Node *cur = *head, *prev = NULL;
    while (cur && cur->value != v) { prev = cur; cur = cur->next; }
    if (!cur) return;
    if (prev) prev->next = cur->next; else *head = cur->next;
    free(cur);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    del(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    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*n);n->value=v;n->next=NULL;return n;}

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

避免内存泄漏

从链表中删除的每个节点都必须通过 free 释放。删除节点却不释放它，会导致它占用的内存泄漏。

同样，切勿在节点仍与链表相连时释放它，否则会产生悬空指针。

#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 *n = make(7);
    free(n);
    printf("node freed, no leak\n");
    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*n);n->value=v;n->next=NULL;return n;}

void insert_sorted(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head || (*head)->value >= v) { n->next = *head; *head = n; return; }
    struct Node *p = *head;
    while (p->next && p->next->value < v) p = p->next;
    n->next = p->next; p->next = n;
}

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

快速检查

测试您对链表修改的理解。

回顾

您学习了如何插入和删除节点：

  • 在开头插入的复杂度是 O(1)；追加或按顺序插入则需要遍历链表。
  • 当头指针可能改变时，请使用二级指针。
  • 接入节点时要谨慎：先设置新节点的 next，再重新连接指针。
  • 删除时跟踪前一个节点，并始终对删除的节点调用 free。

常见问题解答

「插入与删除」课时是免费的吗？

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

「插入与删除」这节课中我会学到什么？

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

学习 C Academy 需要有经验吗？

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

「插入与删除」课时需要多长时间？

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

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

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

此课程中的所有课时

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