链表基础：单向链表的创建、插入、删除、遍历，头节点与头指针

说到链表，我脑子里立刻浮现出刚入行时被它折磨的画面。那时候总觉得数组多好用啊，干嘛要搞个这么麻烦的东西？直到后来做嵌入式项目，需要动态管理内存，才真正体会到链表的妙处。

说白了，链表就是一组节点串起来的结构。每个节点存着数据，还带着一个指向下一个节点的指针。跟数组不一样，链表不需要一整块连续的内存，可以零散地分布在内存各处。这在嵌入式系统里特别实用——你想想看，有时候内存碎片化严重，数组根本分配不到连续空间，但链表就能灵活应对。

头节点 vs 头指针

这两个概念我当年搞混过好几次，后来才彻底明白。头指针就是指向链表第一个节点的指针，它必须存在，否则你就找不到链表了。头节点呢？它是一个可选的节点，放在第一个有效数据节点之前，本身不存有效数据。

我个人习惯在链表里加个头节点。为什么？因为这样插入和删除操作就不用特殊处理第一个节点了，代码写起来统一很多。我在项目中遇到过好几次因为没带头节点，导致边界条件处理出bug的情况。

对比项	头指针	头节点
是否必须	必须存在	可选
存储内容	地址值	不存有效数据
作用	标识链表起点	简化操作逻辑
内存分配	栈或全局区	堆上动态分配

单向链表的创建

创建链表其实就是分配头节点（如果有的话），然后把头指针指向它。来看代码：

// 定义节点结构
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

// 创建链表（带头节点）
Node* createList() {
    Node *head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    head->next = NULL;  // 头节点不存数据，next指向空
    return head;
}

嗯，这里要注意：malloc之后一定要检查返回值。嵌入式系统内存有限，分配失败是常有的事。我曾经在一个项目中因为没检查返回值，结果程序跑着跑着就莫名其妙崩溃了，查了两天才发现是内存分配失败导致的野指针问题。

插入操作

插入节点有三种情况：头插、尾插、中间插。带头节点的情况下，头插和中间插的逻辑其实是一样的。

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

// 尾插法
void insertTail(Node *head, int data) {
    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    insertAfter(p, data);
}

你想想看，插入操作的核心就两步：先让新节点指向后继，再让前驱指向新节点。顺序不能搞反，否则链表就断了。我刚开始学的时候老犯这个错，先改了前驱的指针，结果后面的节点全丢了。

删除操作

删除节点比插入稍微麻烦一点，因为你要找到待删除节点的前驱。带头节点的话，删除第一个有效节点和删除中间节点也是一样的逻辑。

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

// 按值删除第一个匹配的节点
int deleteByValue(Node *head, int value) {
    Node *p = head;
    while (p->next != NULL) {
        if (p->next->data == value) {
            deleteAfter(p);
            return 0;
        }
        p = p->next;
    }
    return -1;  // 没找到
}

遍历操作

遍历是最简单的，从头节点开始，一路往后走，直到遇到空指针。

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

这里有个小细节：遍历时不要修改头指针的值。我见过有人写head = head->next来遍历，结果遍历完头指针丢了，整个链表都找不到了。正确的做法是用一个临时指针p来移动。

知识体系总览

下面这张图把单向链表的整体结构画出来了，你看一眼就能明白各个操作之间的关系：

完整示例：综合运用

最后给一个完整的例子，把创建、插入、删除、遍历串起来：

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

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

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

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 deleteAfter(Node *prev) {
    if (prev == NULL || prev->next == NULL) return -1;
    Node *temp = prev->next;
    prev->next = temp->next;
    free(temp);
    return 0;
}

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

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

int main() {
    Node *list = createList();
    
    // 插入数据
    insertAfter(list, 10);
    insertAfter(list, 20);
    insertAfter(list, 30);
    
    printf("初始链表: ");
    traverse(list);  // 输出: 10 20 30
    
    // 删除节点
    deleteAfter(list);  // 删除第一个节点
    printf("删除后: ");
    traverse(list);  // 输出: 20 30
    
    destroyList(list);
    return 0;
}

这段代码我实际跑过很多次，在嵌入式开发板上也验证过。你拿去用的时候注意一点：destroyList一定要在程序结束前调用，否则会有内存泄漏。我曾经在一个长期运行的项目里忘了释放链表，结果系统跑了三天后内存耗尽，直接死机了。

单向链表是链表家族的基础，搞懂了它，双向链表、循环链表学起来就轻松多了。核心就三点：指针怎么指、内存怎么管、边界怎么处理。把这三点吃透，链表这块就算拿下了。

---

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