线性表之单链表：从节点到内存的完整旅程

单链表，说白了就是一组「手拉手」的节点。每个节点只管两件事：存自己的数据，记住下一个兄弟在哪。我刚开始学的时候觉得这玩意儿比数组麻烦多了，后来在嵌入式项目里才发现——当你需要频繁插入删除、又不知道数据量多大时，链表简直是救命稻草。

1. 节点定义——链表的砖瓦

每个节点长什么样？很简单：

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node, *LinkedList;

这里有个细节我提一下：struct Node *next 不能写成 Node *next，因为 typedef 还没生效。嗯，这是 C 语言的老规矩了。

我的习惯：我喜欢把 LinkedList 定义成指针类型。这样写函数参数时更直观——LinkedList L 一看就知道是个链表头。

2. 头插法与尾插法——两种构建思路

构建链表，无非两种方式：从头部插，或者从尾部插。各有各的脾气。

头插法

每次新节点都塞到最前面。我当年做学生管理系统时用过这个——因为数据录入顺序不重要，头插法代码简单，跑得也快。

void headInsert(LinkedList *L, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *L;  // 新节点指向原来的头
    *L = newNode;         // 头指针更新
}

注意看：头插法得到的数据顺序是反的。你输入 1、2、3，链表里存的是 3、2、1。为什么会这样？因为每次新来的都插在最前面嘛。

尾插法

这个就老实多了，新节点乖乖跟在最后面。需要维护一个尾指针，不然每次都要遍历到尾部——那就太慢了。

void tailInsert(LinkedList *L, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*L == NULL) {
        *L = newNode;  // 空链表，新节点就是头
        return;
    }

    Node *p = *L;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}
我曾经踩过的坑：尾插法里忘记把 newNode->next 置为 NULL。结果最后一个节点指向了随机地址，遍历时直接段错误。malloc 出来的内存不会自动清零，这个教训我记了好几年。

3. 按位查找与按值查找——两种找法

链表不像数组，不能直接下标访问。想找第 i 个节点？老老实实从头走。

按位查找

Node *getByIndex(LinkedList L, int index) {
    if (index < 1) return NULL;
    Node *p = L;
    int j = 1;
    while (p != NULL && j < index) {
        p = p->next;
        j++;
    }
    return p;  // 没找到就返回 NULL
}

这里 index 从 1 开始，是我个人的编码习惯。你想想看，如果从 0 开始，边界条件处理起来反而容易乱。

按值查找

Node *getByValue(LinkedList L, int value) {
    Node *p = L;
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

按值查找返回的是第一个匹配的节点。如果链表里有重复值，后面的就找不到了。我在项目中遇到过这种情况——后来改成了返回所有匹配节点的链表。

4. 删除节点与释放内存——善后工作

删除节点，说白了就是「跳过」它，然后把它的内存还回去。这里有个顺序问题：先改指针，再 free，顺序不能反。

int deleteNode(LinkedList *L, int index) {
    if (*L == NULL || index < 1) return 0;

    Node *p = *L;
    if (index == 1) {
        *L = p->next;  // 删除头节点
        free(p);
        return 1;
    }

    Node *prev = NULL;
    int j = 1;
    while (p != NULL && j < index) {
        prev = p;
        p = p->next;
        j++;
    }
    if (p == NULL) return 0;  // 索引越界

    prev->next = p->next;  // 跳过 p
    free(p);
    return 1;
}
核心要点：删除头节点时，头指针要更新。删除中间节点时，前驱节点的 next 要指向后继节点。free 之后，p 指针变成野指针，不要再使用。

释放整个链表呢？我建议用循环，不要用递归——嵌入式环境栈空间有限，递归容易爆栈。

void freeList(LinkedList *L) {
    Node *p = *L;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    *L = NULL;  // 别忘了把头指针置空
}

嗯，这里有个细节：free(temp) 之后，temp 指向的内存已经归还系统了，但 p 还在用 temp->next 吗？不会，因为我们在 free 之前已经把 p 移到下一个节点了。顺序很重要。

知识体系总览

下面这张图把单链表的几个核心操作串起来了。我画图时习惯把「内存管理」单独拎出来——很多初学者只关注增删改查，忘了 free，结果内存泄漏得一塌糊涂。

单链表核心操作 节点定义 data + next 指针 构建方式 头插法 / 尾插法 查找操作 按位 / 按值 删除与释放 改指针 → free → 置空 内存管理 malloc / free / 野指针 操作顺序：先定义节点 → 选择构建方式 → 实现查找 → 最后删除并释放内存 内存管理贯穿始终：有 malloc 就必须有 free

避坑指南

  • malloc 后一定要检查返回值。嵌入式系统内存紧张，malloc 可能返回 NULL。我见过线上设备因为 malloc 失败直接跑飞——加个 if 判断能省很多事。
  • free 后记得把指针置 NULL。不然就成了野指针。你想想看，万一后面不小心又用这个指针赋值，那就是写入了已经释放的内存——这种 bug 极难排查。
  • 头插法和尾插法不要混用。除非你很清楚自己在做什么。混用会导致节点顺序混乱，调试时头大。
  • 删除节点时，先保存下一个节点的地址。不然 free 之后你就找不到下一个节点了。
我的一个小技巧：写链表操作时，先在纸上画一遍指针变化。画清楚了再写代码，bug 能少一半。尤其是删除和插入，指针绕来绕去，画图最直观。

单链表看起来简单，但指针操作稍不留神就出问题。我当年第一次写链表删除，忘了更新前驱节点的 next，结果链表断成了两截——遍历到一半就崩了。嗯，这些坑踩过一次就记住了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →