31、动态数据结构（二）：单向链表的插入与删除

链表这东西，说白了就是一根绳子串起一堆珠子。

每个珠子（节点）里存着数据，还记着下一个珠子在哪。跟数组不一样，数组是一排连续的座位，链表则是散落在内存各处的碎片，靠指针串起来。

我刚开始学链表时，总觉得它不如数组直观。直到有一次做项目，需要频繁插入删除数据，数组搬来搬去效率太低了，我才真正体会到链表的妙处。

31.1 链表节点的定义

先看看节点长什么样。每个节点包含两部分：数据域和指针域。

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

嗯，这里要注意：next 是指向自身结构体的指针。这种自引用的定义方式，是链表的基石。

31.2 创建新节点

插入操作之前，得先会创建节点。我习惯写一个辅助函数：

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;
}

31.3 头插法

头插法，就是把新节点插到链表最前面。新节点成为新的头节点。

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

为什么传二级指针？因为要修改头指针本身。如果你传一级指针，函数里改的是副本，外面根本不知道。

头插法的特点是：插入顺序和链表顺序相反。你插 1、2、3，链表里存的是 3、2、1。我刚开始觉得这很奇怪，后来发现有些场景正好需要这种逆序效果。

31.4 尾插法

尾插法，就是把新节点挂在链表末尾。这样插入顺序和链表顺序一致。

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

你想想看，每次尾插都要遍历到链表末尾。如果链表很长，这个操作就很慢。我做过一个日志系统，每秒要插入上千条记录，用尾插法性能完全扛不住。后来改成了头插法，再在读取时反转，才解决了问题。

31.5 中间插法

中间插法，就是在指定位置插入。比如在第 k 个节点后面插入。

void insertAtPosition(Node **head, int data, int position) {
    if (position < 0) return;
    if (position == 0) {
        insertAtHead(head, data);
        return;
    }
    Node *newNode = createNode(data);
    Node *temp = *head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("位置超出范围\n");
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

31.6 删除节点

删除节点分三种情况：删头节点、删中间节点、删尾节点。

void deleteNode(Node **head, int key) {
    if (*head == NULL) return;

    Node *temp = *head, *prev = NULL;

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

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

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

    // 断开链接
    prev->next = temp->next;
    free(temp);
}

删除操作最怕什么？最怕内存泄漏。free 掉节点后，那个内存就还给系统了。如果你忘了 free，程序跑久了内存会越占越多。

31.7 释放整个链表

链表用完了，要记得释放。不然内存泄漏等着你。

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

释放链表时，一定要先保存下一个节点的地址，再释放当前节点。不然释放完当前节点，你就找不到下一个节点了。

31.8 核心逻辑流程图

下面这张图，把链表的插入、删除、释放串起来了。你看一遍就能理解整体流程。

31.9 总结一下

链表操作其实就几个核心点：

• 插入：先连后断，顺序不能乱
• 删除：找到节点，跳过它，释放它
• 释放：先存后删，循环到底

我个人觉得，链表是理解指针最好的练习。你把这些操作写熟了，指针这块基本就通了。