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

链表这东西，说实话，是我当年从“C语言新手”变成“敢说自己会C”的一道分水岭。数组你肯定用过，连续内存，随机访问，方便得很。但数组有个硬伤——你必须在编译时就定好大小，或者用malloc搞个动态数组，可一旦要频繁插入删除，那效率简直惨不忍睹。

链表就不一样了。它不要求内存连续，每个节点都是“散装”的，靠指针串在一起。插入和删除只需要改改指针，时间复杂度O(1)。代价是什么？不能随机访问，你要找第n个元素，得从头一个个数过去。嗯，这就是典型的“空间换时间”或者“灵活性换便利性”。

14.1 单向链表的定义

单向链表，也叫单链表，是最简单的一种链表。每个节点只有一个指针，指向下一个节点。最后一个节点的指针指向NULL，表示链表结束。

定义节点结构体，我习惯这样写：

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

注意这里struct Node *next不能写成Node *next，因为typedef还没生效。这个坑我见过不少人踩过。

有了节点类型，我们还需要一个头指针。头指针指向链表的第一个节点。如果链表为空，头指针就是NULL。

Node *head = NULL;  // 空链表

14.2 创建节点

创建节点就是动态分配一块内存，填上数据，把next置为NULL。

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

这里有个细节：malloc之后一定要检查返回值。我在项目中遇到过，嵌入式设备内存紧张，malloc返回NULL是常有的事。不检查的话，后面直接访问newNode->data就是野指针操作，程序崩溃是轻的，数据被写坏才要命。

14.3 遍历链表

遍历链表很简单，从头指针开始，一路顺着next走到NULL。

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

你想想看，为什么这里要用一个临时变量current，而不是直接移动head？因为head是链表的入口，一旦你把它改了，整个链表就丢了。嗯，这就是指针的“副作用”——你修改了指针本身，而不是指针指向的内容。

14.4 插入节点

插入节点有三种情况：头部插入、尾部插入、中间插入。我们一个个来看。

14.4.1 头部插入

void insertAtHead(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

这里用了二级指针，因为我们要修改头指针本身。如果你用一级指针，函数内部修改的是指针的副本，外部头指针不会变。这个道理我当年花了整整一个下午才想明白。

14.4.2 尾部插入

void insertAtTail(Node **head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

尾部插入需要先遍历到最后一个节点。如果链表为空，直接让头指针指向新节点。这里要注意，遍历时判断条件是current->next != NULL，而不是current != NULL。为什么？因为我们要停在最后一个节点上，而不是越过它。

14.4.3 中间插入（在指定位置之后）

void insertAfter(Node *prevNode, int data) {
    if (prevNode == NULL) {
        printf("前驱节点不能为NULL\n");
        return;
    }
    Node *newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

这个操作的时间复杂度是O(1)，因为不需要遍历。但前提是你已经拿到了prevNode的指针。如果你只有数据值，那还是得先遍历找到这个节点，遍历本身是O(n)。

14.5 删除节点

删除节点同样有三种情况：删除头节点、删除尾节点、删除中间节点。删除操作比插入稍微麻烦一点，因为你要释放内存。

14.5.1 删除头节点

void deleteHead(Node **head) {
    if (*head == NULL) return;
    Node *temp = *head;
    *head = (*head)->next;
    free(temp);
}

先保存要删除的节点，然后移动头指针，最后释放内存。顺序很重要——如果你先释放了*head，那(*head)->next就访问不到了。

14.5.2 删除指定值的节点

void deleteNode(Node **head, int key) {
    Node *current = *head;
    Node *prev = NULL;

    // 如果要删除的是头节点
    if (current != NULL && current->data == key) {
        *head = current->next;
        free(current);
        return;
    }

    // 查找要删除的节点
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }

    // 没找到
    if (current == NULL) return;

    // 删除节点
    prev->next = current->next;
    free(current);
}

这里需要维护一个prev指针，记录当前节点的前一个节点。因为单向链表只有向后的指针，没有向前的指针，所以你必须手动记住前一个节点是谁。

14.6 知识体系图

下面这张图展示了单向链表的核心操作和它们之间的关系。你可以看到，所有操作都围绕着“节点”和“指针”展开。

14.7 总结与避坑

单向链表的核心就两件事：指针操作和内存管理。指针操作要小心顺序，内存管理要记得释放。

我总结几个常见的坑：

• 野指针：节点释放后，没有把指针置为NULL，后面又去访问它。解决办法：free之后立即ptr = NULL。
• 内存泄漏：只删除了节点，没有free。尤其是在循环删除时，容易漏掉。
• 断链：插入或删除时，指针操作顺序搞反了，导致链表断成两截。记住“先接后断”四个字。
• 头指针丢失：函数内部修改了头指针，但外部不知道。解决办法：用二级指针，或者返回新的头指针。

单向链表是链表家族的基础。搞懂了它，双向链表、循环链表、甚至内核链表都不在话下。指针这东西，说白了就是“你指向我，我指向你”，别把它想得太玄乎。

---

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