链表基础：单向链表的定义、创建节点、遍历链表、插入节点、删除节点

说到链表，我脑子里第一个蹦出来的场景是十年前做嵌入式通信协议栈时的经历。那时候用数组管理数据包缓冲区，增删一个节点就得搬动一大片内存，效率低得让人抓狂。后来换成链表，整个世界清静了。说白了，链表就是解决「动态数据管理」问题的最朴素方案。

单向链表长什么样？

单向链表，你可以把它想象成一串手拉手的小朋友。每个小朋友（节点）只知道自己后面是谁，但不知道前面是谁。每个节点由两部分组成：

• 数据域：存放实际数据，可以是 int、char、结构体等
• 指针域：指向下一个节点的地址

链表的尽头是最后一个节点，它的指针指向 NULL，表示「后面没人了」。另外我们还需要一个头指针 head，它指向链表的第一个节点。如果 head == NULL，说明这是个空链表。

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

嗯，这里要注意：struct Node* next 是一个指向自身类型的指针，这种「自引用结构体」是链表实现的基础。我第一次写的时候老忘记加 struct 关键字，编译报错半天没反应过来。

创建节点：从堆上申请内存

链表的节点不是静态分配的，而是在程序运行时动态申请。C 语言里我们用 malloc 函数从堆上要一块内存。

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

为什么用 sizeof(struct Node) 而不是直接写数字？因为不同平台下结构体的大小可能不同，用 sizeof 可以保证代码的可移植性。我习惯在写嵌入式代码时特别注意这一点。

遍历链表：从头走到尾

遍历链表就像沿着一条绳子摸下去，从 head 开始，一个一个往后走，直到遇到 NULL 为止。

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

这里有个小细节：我习惯用一个临时指针 current 来遍历，而不是直接移动 head。因为 head 是链表的入口，一旦丢失就再也找不回来了。你想想看，如果直接把 head 往后移，那前面的节点就全丢了，内存泄漏就是这么来的。

插入节点：头插法与尾插法

插入节点是链表操作中最常用的功能。我个人习惯把插入分为两种场景：

头插法（在链表头部插入）

// 在链表头部插入新节点
struct Node* insertAtHead(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    if (newNode == NULL) return head;
    
    newNode->next = head;  // 新节点指向原来的头节点
    head = newNode;         // 更新头指针
    return head;
}

头插法的逻辑很简单：新节点的 next 指向原来的 head，然后 head 指向新节点。顺序不能搞反，否则会丢失链表。我记得刚学的时候老是把这两行写反，结果链表越插越短。

尾插法（在链表尾部插入）

// 在链表尾部插入新节点
struct Node* insertAtTail(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    if (newNode == NULL) return head;
    
    if (head == NULL) {
        // 空链表，新节点就是头节点
        return newNode;
    }
    
    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

尾插法需要先遍历到链表末尾，找到最后一个节点，然后把它的 next 指向新节点。这里要注意处理空链表的特殊情况——如果 head 是 NULL，新节点直接成为头节点。

删除节点：小心断链

删除节点是链表操作中最容易出问题的环节。核心思路是：找到要删除的节点，让它的前一个节点跳过它，直接指向它的下一个节点，然后释放它占用的内存。

// 删除第一个值为 data 的节点
struct Node* deleteNode(struct Node* head, int data) {
    if (head == NULL) return NULL;
    
    struct Node* current = head;
    struct Node* prev = NULL;
    
    // 查找要删除的节点
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }
    
    if (current == NULL) {
        // 没找到
        printf("未找到值为 %d 的节点\n", data);
        return head;
    }
    
    if (prev == NULL) {
        // 删除的是头节点
        head = current->next;
    } else {
        // 删除的是中间或尾部节点
        prev->next = current->next;
    }
    
    free(current);  // 释放内存
    return head;
}

删除操作的关键在于维护好前驱节点 prev。如果删除的是头节点，prev 为 NULL，直接更新 head。否则让 prev->next 跳过 current，指向 current->next。最后别忘了 free 掉 current。

知识体系总览

下面这张图把单向链表的操作流程梳理了一下，我画图时习惯把关键路径标出来，方便快速回顾。

总结一下

单向链表是动态数据结构的入门砖，也是理解指针和内存管理的最佳实践。说白了，它就是用指针把零散的内存块串起来，实现灵活的数据管理。我个人觉得，链表学好了，后面学树、图这些复杂结构就会轻松很多。

在实际项目中，链表的应用场景非常广泛：任务队列、消息缓冲区、内存池管理……几乎每个嵌入式系统里都能看到它的身影。我建议你亲手把上面这些代码敲一遍，调试一遍，感受一下指针在内存中游走的感觉。嗯，只有亲手写过，才能真正理解。

---

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