C 语言综合练习四：链表入门实现

更新时间：2026-08-26。本文是 languages/c/ 主题入门层第 75 篇。前面用数组存数据，这次用链表：节点靠指针串起来，插删只改指针、不搬数据。它是自引用结构体与动态内存的合体实战，也是数据结构课的第一道门槛。代码已入库 demos/c-beginner-practice/linked_list.c。

本文要回答的问题

• 链表的节点和链接关系怎么定义？
• 头插、尾插、按值删除怎么写？
• 链表和数组各自适合什么场景？

一、链表结构

typedef struct Node {
    int data;
    struct Node *next;    // 指向下一个节点（自引用）
} Node;

head → [10|·] → [20|·] → [30|NULL]

• head 指向第一个节点；
• 每个节点存数据 + 指向下一个的指针；
• 最后一个节点的 next 是 NULL（链表终点）。

二、完整代码

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* 头插：新节点成为新 head */
Node *push_front(Node *head, int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return head;
    n->data = value;
    n->next = head;        // 新节点指向旧 head
    return n;              // 返回新 head
}

/* 尾插：走到最后一个节点再挂上 */
Node *push_back(Node *head, int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return head;
    n->data = value;
    n->next = NULL;

    if (head == NULL) return n;      // 空表：新节点就是 head
    Node *p = head;
    while (p->next != NULL)          // 走到最后一个
        p = p->next;
    p->next = n;                     // 挂上
    return head;
}

/* 按值删除第一个匹配节点 */
Node *delete_value(Node *head, int value) {
    Node *p = head, *prev = NULL;
    while (p != NULL && p->data != value) {
        prev = p;
        p = p->next;
    }
    if (p == NULL) return head;      // 没找到
    if (prev == NULL)
        head = p->next;              // 删的是头节点
    else
        prev->next = p->next;        // 跳过 p
    free(p);
    return head;
}

void print_list(Node *head) {
    for (Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

void free_list(Node *head) {
    Node *p = head;
    while (p != NULL) {
        Node *next = p->next;
        free(p);                     // 先记下 next 再释放
        p = next;
    }
}

int main(void) {
    Node *head = NULL;
    head = push_front(head, 10);
    head = push_front(head, 20);     // 20 10
    head = push_back(head, 30);      // 20 10 30

    print_list(head);                // 20 10 30

    head = delete_value(head, 10);   // 20 30
    print_list(head);

    free_list(head);
    return 0;
}

三、关键设计点

1. 头插/尾插都要"改头指针"：

head = push_front(head, 10);   // 函数返回新 head

链表头可能变，所以函数返回 Node *，调用方必须用返回值更新 head。

2. 删除维护两个指针：prev 记前驱、p 记当前——断开时 prev->next = p->next，先判断删的是不是头节点。

3. 释放链表要"先记后放"：

Node *next = p->next;   // 先保存
free(p);                // 再释放
p = next;

先 free 再取 p->next 就是 use-after-free（内存错误 讲过）。

四、运行演示

$ make run
20 10 30
20 30

五、链表 vs 数组

操作	数组	链表
按下标访问	O(1)	O(n)
头部插入	O(n) 挪元素	O(1)
中间删除	O(n) 挪元素	O(1)（已定位）
空间	连续、有上限	分散、按需分配
缓存友好	好	差

经验：频繁"按下标访问"用数组；频繁"头部/中间插删"用链表。

六、扩展练习

• 实现按值查找、逆序输出（递归）；
• 双向链表、循环链表；
• 用链表做队列/栈。

七、一句话总结

/*
 * linked_list.c —— C 语言入门综合练习四：链表入门实现
 * 文档: languages/c/beginner/75-practice-linked-list.md
 * 编译: make && ./linked_list
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* 头插：新节点成为新 head */
Node *push_front(Node *head, int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return head;
    n->data = value;
    n->next = head;        /* 新节点指向旧 head */
    return n;              /* 返回新 head */
}

/* 尾插：走到最后一个节点再挂上 */
Node *push_back(Node *head, int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return head;
    n->data = value;
    n->next = NULL;

    if (head == NULL) return n;      /* 空表：新节点就是 head */
    Node *p = head;
    while (p->next != NULL)          /* 走到最后一个 */
        p = p->next;
    p->next = n;                     /* 挂上 */
    return head;
}

/* 按值删除第一个匹配节点 */
Node *delete_value(Node *head, int value) {
    Node *p = head, *prev = NULL;
    while (p != NULL && p->data != value) {
        prev = p;
        p = p->next;
    }
    if (p == NULL) return head;      /* 没找到 */
    if (prev == NULL)
        head = p->next;              /* 删的是头节点 */
    else
        prev->next = p->next;        /* 跳过 p */
    free(p);
    return head;
}

void print_list(Node *head) {
    for (Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

void free_list(Node *head) {
    Node *p = head;
    while (p != NULL) {
        Node *next = p->next;
        free(p);                     /* 先记下 next 再释放 */
        p = next;
    }
}

int main(void) {
    Node *head = NULL;
    head = push_front(head, 10);
    head = push_front(head, 20);     /* 20 10 */
    head = push_back(head, 30);      /* 20 10 30 */

    print_list(head);                /* 20 10 30 */

    head = delete_value(head, 10);   /* 20 30 */
    print_list(head);

    free_list(head);
    return 0;
}

与本站主线衔接

• 自引用结构体与箭头访问，见结构体指针；
• 动态内存三件套，见malloc 与 free、calloc 与 realloc；
• 更完整的容器实现（栈/队列/二叉树），见链表与二叉树实现。