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

说实话，很多初学者一听到「链表」两个字就头大。我当年也是这样，觉得指针绕来绕去，不如数组来得直接。但后来在项目中做动态内存管理时，才发现链表这东西，真香。

数组有个硬伤——长度固定。你定义了一个100个元素的数组，结果数据只有20个，浪费；如果来了120个，又装不下。链表就不一样了，它像一串珠子，想加一颗就加一颗，想取一颗就取一颗，灵活得很。

什么是单向链表

单向链表，说白了就是一组节点，每个节点里存着数据，还存着一个指针，指向下一个节点。最后一个节点的指针指向NULL，表示到头了。

每个节点长这样：

struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个节点
};

你想想看，这个结构体里有个指向自身类型的指针，是不是有点递归的味道？嗯，这就是链表的精髓。

链表的定义与创建

先定义节点类型：

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

我个人习惯把 LinkedList 定义成指向头节点的指针，这样函数传参时更直观。

创建链表，一般从创建头节点开始。头节点不存有效数据，只用来标记链表的起点。

LinkedList createList() {
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    if (head == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    head->next = NULL;
    return head;
}

我在项目中遇到过一个问题：malloc之后忘了检查返回值，结果在嵌入式设备上跑着跑着就崩了。从那以后，我每次malloc都必做判空处理，成了肌肉记忆。

链表的遍历

遍历链表，就是从头节点开始，顺着next指针一路往下走，直到遇见NULL。

void traverseList(LinkedList head) {
    Node *p = head->next;  // 跳过头节点
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

这里有个小细节：遍历时不要直接移动头指针，否则链表就丢了。一定要用一个临时指针p来走。

链表的插入操作

插入分三种情况：头插、尾插、中间插。我重点讲中间插入，因为这是最容易出bug的地方。

// 在指定位置之后插入新节点
int insertAfter(Node *prev, int data) {
    if (prev == NULL) return -1;

    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return -1;

    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;

    return 0;
}

注意顺序：先让新节点指向后一个节点，再让前一个节点指向新节点。顺序反了，后面的节点就找不到了。

我曾经在调试一个通信协议栈时，就因为把这两行代码写反了，导致链表断链，数据包全部丢失。查了整整一个下午才找到原因……嗯，这种坑踩过一次就记住了。

链表的删除操作

删除节点，核心思路是：找到要删节点的前一个节点，让它跳过要删的节点，直接指向下一个。

int deleteNode(LinkedList head, int target) {
    Node *prev = head;
    Node *curr = head->next;

    while (curr != NULL) {
        if (curr->data == target) {
            prev->next = curr->next;
            free(curr);
            return 0;
        }
        prev = curr;
        curr = curr->next;
    }
    return -1;  // 没找到
}

删除后一定要free掉节点内存，否则内存泄漏。在嵌入式环境里，内存泄漏是慢性毒药，跑几天就崩了。

知识体系图

下面这张图帮你理清单向链表的整体脉络：

完整示例代码

把上面这些操作串起来，写一个完整的例子：

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

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

LinkedList createList() {
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    if (!head) return NULL;
    head->next = NULL;
    return head;
}

void traverseList(LinkedList head) {
    Node *p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int insertAfter(Node *prev, int data) {
    if (!prev) return -1;
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return -1;
    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;
    return 0;
}

int deleteNode(LinkedList head, int target) {
    Node *prev = head;
    Node *curr = head->next;
    while (curr) {
        if (curr->data == target) {
            prev->next = curr->next;
            free(curr);
            return 0;
        }
        prev = curr;
        curr = curr->next;
    }
    return -1;
}

void freeList(LinkedList head) {
    Node *p = head;
    while (p) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
}

int main() {
    LinkedList list = createList();

    insertAfter(list, 10);
    insertAfter(list, 20);
    insertAfter(list, 30);

    printf("链表内容：");
    traverseList(list);

    deleteNode(list, 20);
    printf("删除20后：");
    traverseList(list);

    freeList(list);
    return 0;
}

常见问题与避坑指南

• 忘记判空：malloc可能失败，尤其是嵌入式设备内存紧张时。不判空，后续操作就是野指针。
• 插入顺序搞反：先连后断，这个口诀记牢。
• 删除后没free：内存泄漏的根源。我见过一个项目，链表频繁增删但不free，跑了三天后系统直接挂掉。
• 遍历时移动了头指针：链表丢了，找不回来。一定要用临时指针。

单向链表是链表家族的基础。搞懂了它，双向链表、循环链表、甚至内核链表都不在话下。你想想看，是不是这个理？