10. 结构体综合实战：链表节点的定义、创建、遍历与销毁

链表这东西，说实话，是C语言里绕不开的一道坎。我当年刚学的时候也觉得挺玄乎，什么节点、指针、动态分配，一堆概念搅在一起。但后来在项目里真正用上了，才发现它其实没那么复杂——说白了，就是一组结构体手拉手排成一串。

今天咱们就把链表这层窗户纸捅破。从节点定义开始，一步步把创建、遍历、销毁全走一遍。你跟着我敲一遍代码，保证能搞明白。

10.1 链表节点长什么样？

链表的基本单位叫「节点」。每个节点存两样东西：一是数据，二是指向下一个节点的指针。用结构体来表达，就是：

// 定义一个单向链表节点
struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
};

你看，这个结构体里有个struct Node*类型的成员。它指向的是和自己同类型的结构体。这种「自己指自己」的写法，就是链表的精髓。

核心理解：节点就像一节火车车厢。车厢里装着货物（data），车厢后面有个挂钩（next），可以挂上下一节车厢。最后一节车厢的挂钩是空的（NULL），表示到头了。

我个人习惯给节点类型起个别名，省得每次写struct Node那么长：

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

这样后面用Node*就清爽多了。

10.2 创建节点——动态分配内存

链表节点不是静态变量，而是在程序运行时动态申请的。用malloc在堆上分配内存，然后初始化数据。

// 创建一个新节点，返回节点指针
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

这里有个坑，我曾经踩过——一定要检查malloc的返回值。嵌入式环境里内存本来就紧张，分配失败是常有的事。不检查就直接用，程序崩了都不知道怎么死的。

注意：malloc返回的是void*，需要强制转换成Node*。另外，sizeof(Node)计算的是整个结构体的大小，包括可能的对齐填充字节。

10.3 链表的创建——头插法与尾插法

有了节点，怎么把它们串起来？两种常用方式：头插法和尾插法。

10.3.1 头插法

每次新节点都插在链表头部。新节点的next指向原来的头节点，然后更新头指针。

// 头插法：新节点成为新的头
void insertAtHead(Node** head, int value) {
    Node* newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = *head;
    *head = newNode;
}

为什么传Node**？因为要修改头指针本身。如果只传Node*，你改的是形参，外面的头指针不会变。这个细节我当年也迷糊过一阵子。

10.3.2 尾插法

新节点加在链表末尾。需要先找到最后一个节点，然后把它的next指向新节点。

// 尾插法：新节点成为新的尾
void insertAtTail(Node** head, int value) {
    Node* newNode = createNode(value);
    if (newNode == NULL) return;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

尾插法保持了数据的插入顺序，但每次都要遍历到末尾，效率比头插法低。你想想看，如果链表有1000个节点，每次插入都要走1000步。所以实际项目中，如果对顺序没要求，我一般用头插法。

10.4 遍历链表——把数据走一遍

遍历就是从头节点开始，沿着next指针一路走下去，直到遇到NULL。

// 遍历链表，打印每个节点的数据
void traverseList(Node* head) {
    Node* current = head;
    int count = 0;
    while (current != NULL) {
        printf("节点 %d: %d\n", count++, current->data);
        current = current->next;
    }
    printf("共 %d 个节点\n", count);
}

这里有个小技巧：用current指针来遍历，不要直接移动head。因为head是链表的入口，丢了就找不回来了。我见过有人直接head = head->next，遍历完链表头也没了，后面想再操作就抓瞎了。

小提示：遍历时如果只需要读数据，用const Node*更安全，能防止不小心修改了链表结构。

10.5 销毁链表——别忘了释放内存

链表用完了，必须把每个节点都free掉。否则就会造成内存泄漏。嵌入式系统内存有限，泄漏一点可能就出大问题。

// 销毁整个链表，释放所有节点内存
void destroyList(Node** head) {
    Node* current = *head;
    Node* nextNode;

    while (current != NULL) {
        nextNode = current->next;  // 先保存下一个节点
        free(current);              // 释放当前节点
        current = nextNode;         // 移动到下一个
    }

    *head = NULL;  // 头指针置空，防止野指针
}

注意顺序：先保存下一个节点，再释放当前节点。如果先free(current)再取current->next，那就是访问已释放的内存，行为未定义。我曾经在项目里犯过这个错，排查了好久才发现是释放顺序搞反了。

警告：销毁后一定要把头指针置为NULL。否则这个指针就成了野指针，后面不小心用了它，程序崩溃是轻的，数据被破坏才真要命。

10.6 完整示例——把上面串起来

咱们写个完整的例子，从创建到销毁走一遍：

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

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

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void insertAtHead(Node** head, int value) {
    Node* newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = *head;
    *head = newNode;
}

void traverseList(Node* head) {
    Node* current = head;
    int count = 0;
    while (current != NULL) {
        printf("节点 %d: %d\n", count++, current->data);
        current = current->next;
    }
}

void destroyList(Node** head) {
    Node* current = *head;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *head = NULL;
}

int main() {
    Node* head = NULL;

    // 头插法创建链表：5 -> 10 -> 15 -> 20
    insertAtHead(&head, 20);
    insertAtHead(&head, 15);
    insertAtHead(&head, 10);
    insertAtHead(&head, 5);

    printf("链表内容：\n");
    traverseList(head);

    // 销毁链表
    destroyList(&head);
    printf("链表已销毁，head = %p\n", (void*)head);

    return 0;
}

运行结果：

链表内容：
节点 0: 5
节点 1: 10
节点 2: 15
节点 3: 20
链表已销毁，head = (nil)

10.7 链表的核心逻辑图

下面这张图把链表的核心操作串起来了，你看一遍就能记住：

单向链表核心操作流程图 节点定义 struct Node { data; next; } 使用 创建节点 malloc + 初始化 选择 头插法 尾插法 遍历 读数据 销毁链表 逐个 free + 头置 NULL 内存释放完毕

10.8 避坑指南——我踩过的那些坑

链表这东西，代码看着简单，真写起来容易出各种问题。我把自己踩过的坑列出来，你写的时候多留个心眼：

常见错误 后果 正确做法
忘记检查malloc返回值 空指针访问，程序崩溃 每次malloc后都判断是否为NULL
遍历时直接移动头指针 丢失链表入口 用临时指针遍历，不动head
释放节点后继续访问 未定义行为，可能崩溃 先保存next，再free当前节点
销毁后头指针不置NULL 野指针，后续误用 *head = NULL
传参时只传Node*却想修改头指针 修改无效 传Node**，即指针的指针

我曾经在一个项目里，因为忘了把销毁后的头指针置NULL，结果后面代码里又用这个指针去遍历，读出来的全是垃圾数据。排查了整整一个下午才发现问题。嗯，从那以后我每次销毁链表都会顺手把头指针清掉，已经成肌肉记忆了。

个人建议：写链表操作时，养成「先检查、后使用」的习惯。检查指针是否NULL，检查malloc是否成功，检查边界条件。这些检查看起来啰嗦，但能帮你省下大量调试时间。

链表是很多复杂数据结构的基础。栈、队列、图，底层都可以用链表实现。你把今天这几个操作练熟了，后面学什么数据结构都轻松。

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

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