17、指针与链表：单向链表的定义、链表的创建与遍历、链表的插入与删除

指针学到这个阶段，很多同学会问：“指针到底有什么用？”

嗯，前面我们讲了指针和数组、指针和函数，但说实话，那些都只是开胃菜。指针真正的用武之地，是动态数据结构——比如链表。

我个人做嵌入式开发这么多年，链表几乎无处不在。任务队列、内存池管理、缓冲区调度……底层系统里到处都有它的影子。你想想看，如果不用链表，用数组去管理一个动态变化的任务列表，那得多痛苦？

17.1 单向链表的定义

先看结构体定义。单向链表的每个节点，至少包含两部分：

• 数据域：存储实际数据
• 指针域：指向下一个节点

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

这里有个细节：struct Node* next 是一个指向自身结构体的指针。这种写法叫自引用结构体。我在项目中第一次写这个的时候，还愣了一下——结构体里怎么能包含自己？其实它包含的是指针，不是结构体本身，所以没问题。

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

17.2 链表的创建

创建链表，说白了就是动态分配节点，然后把它们串起来。

我常用的方式是头插法和尾插法。先看头插法：

// 头插法创建链表
Node* createList_head(int arr[], int n) {
    Node* head = NULL;  // 头指针初始为空
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点指向原来的头
        head = newNode;        // 更新头指针
    }
    return head;
}

头插法的特点是：新节点永远插在最前面。所以最后遍历的时候，数据顺序是反的。如果你希望顺序和数组一致，那就用尾插法：

// 尾插法创建链表
Node* createList_tail(int arr[], int n) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;   // 第一个节点
            tail = newNode;
        } else {
            tail->next = newNode;  // 尾节点指向新节点
            tail = newNode;        // 更新尾指针
        }
    }
    return head;
}

17.3 链表的遍历

遍历链表很简单，就是从头节点开始，顺着 next 指针一路走到底。

void traverseList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;  // 移动到下一个节点
    }
    printf("\n");
}

这里有个关键点：遍历时不要修改 head 指针。我见过有人直接拿 head 去遍历，结果遍历完 head 变成 NULL 了，链表丢了。正确的做法是用一个临时指针 p 去走。

17.4 链表的插入

插入操作分三种情况：头插、尾插、中间插。核心逻辑都一样：先找到插入位置，然后调整指针。

// 在指定位置之后插入节点
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;
}

你看，插入的核心就两行代码：newNode->next = prev->next 和 prev->next = newNode。顺序不能错。如果先把 prev->next 指向 newNode，那后面的节点就找不到了。

17.5 链表的删除

删除操作比插入稍微麻烦一点，因为要处理被删除节点的内存释放。

// 删除指定节点的后继节点
int deleteAfter(Node* prev) {
    if (prev == NULL || prev->next == NULL) {
        return -1;  // 没有可删除的节点
    }
    Node* temp = prev->next;       // 暂存要删除的节点
    prev->next = temp->next;       // 跳过该节点
    free(temp);                    // 释放内存
    return 0;
}

删除的关键步骤：

1. 用临时指针保存要删除的节点
2. 调整前驱节点的 next 指针，跳过该节点
3. 调用 free() 释放内存

17.6 知识体系图

下面这张图总结了单向链表的完整知识结构，从定义到操作，一目了然：

17.7 总结与经验

单向链表，说白了就是用指针把零散的内存块串成一条链。它的优点是插入和删除快（O(1)），缺点是查找慢（O(n)）。

我在实际项目中，链表用得最多的地方是：

• 任务调度队列：RTOS 里的就绪队列、延时队列
• 内存池管理：空闲块链表
• 缓冲区管理：环形缓冲区的链表实现

嗯，链表的内容就到这里。记住一句话：指针是链表的灵魂，链表是指针的舞台。