5. 单链表操作：插入、删除、查找、修改与销毁

单链表，说白了就是一条用指针串起来的数据链。每个节点里存着数据，还存着下一个节点的地址。我刚开始学链表时，总觉得它不如数组直观——数组多好，下标一取就完事了。但后来做项目才发现，链表这东西，在动态内存管理、频繁插入删除的场景下，简直是神器。

今天咱们就把单链表的几个核心操作捋一遍。我会结合自己踩过的坑，给你讲明白。

5.1 单链表的插入操作

插入操作分三种情况：头插、尾插、中间插。每种情况我都遇到过实际应用。

5.1.1 头插法

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

// 头插法
Node* insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = head;  // 新节点指向原来的头
    return newNode;         // 新节点成为新的头
}

这里有个细节：一定要先让新节点的next指向旧头，再更新头指针。顺序反了，旧头就丢了。我曾经在调试一个通信协议栈时，就因为顺序写反，导致链表断链，排查了整整一下午。

5.1.2 尾插法

尾插法需要遍历到链表末尾，把新节点接上去。

// 尾插法
Node* insertAtTail(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return head;
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) return newNode;  // 空链表

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    return head;
}

嗯，这里要注意：如果链表为空，直接返回新节点作为头。我见过不少新手忘了处理空链表的情况，结果程序直接崩溃。

5.1.3 指定位置插入

在指定位置插入，需要先找到前一个节点。

// 在位置pos插入（从0开始计数）
Node* insertAtPos(Node* head, int data, int pos) {
    if (pos < 0) return head;
    if (pos == 0) return insertAtHead(head, data);

    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return head;
    newNode->data = data;

    Node* temp = head;
    for (int i = 0; i < pos - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("位置超出范围\n");
        free(newNode);
        return head;
    }

    newNode->next = temp->next;
    temp->next = newNode;
    return head;
}

5.2 单链表的删除操作

删除操作同样分头删、尾删、指定位置删。核心思想是：找到要删的节点，把它的前驱节点指向它的后继节点，然后释放它。

5.2.1 头删法

Node* deleteHead(Node* head) {
    if (head == NULL) return NULL;

    Node* temp = head;
    head = head->next;
    free(temp);
    return head;
}

头删最简单，但别忘了：先保存旧头指针，再移动头，最后释放。顺序错了，内存泄漏没跑。

5.2.2 尾删法

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

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

尾删要找到倒数第二个节点。为什么？因为你要把它的next置为NULL，同时释放最后一个节点。我习惯用temp->next->next来判断是否到了倒数第二个。

5.2.3 指定值删除

Node* deleteByValue(Node* head, int value) {
    if (head == NULL) return NULL;

    // 如果头节点就是要删的
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    Node* temp = head;
    while (temp->next != NULL && temp->next->data != value) {
        temp = temp->next;
    }

    if (temp->next == NULL) {
        printf("未找到值 %d\n", value);
        return head;
    }

    Node* toDelete = temp->next;
    temp->next = toDelete->next;
    free(toDelete);
    return head;
}

5.3 单链表的查找与修改

查找和修改相对简单，核心就是遍历。

5.3.1 按值查找

Node* searchByValue(Node* head, int value) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == value) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;  // 没找到
}

查找的时间复杂度是O(n)。为什么？因为链表不支持随机访问，只能从头一个个找。数组用下标是O(1)，但插入删除是O(n)。各有优劣，看场景选。

5.3.2 按位置查找

Node* searchByPos(Node* head, int pos) {
    Node* temp = head;
    int count = 0;
    while (temp != NULL && count < pos) {
        temp = temp->next;
        count++;
    }
    return temp;  // 如果pos超出范围，返回NULL
}

5.3.3 修改节点

int updateNode(Node* head, int oldVal, int newVal) {
    Node* node = searchByValue(head, oldVal);
    if (node == NULL) {
        return -1;  // 没找到
    }
    node->data = newVal;
    return 0;
}

修改其实就是查找+赋值。找到节点，改它的data字段就行。我在项目中经常用这个功能来做配置更新——比如修改设备参数，遍历链表找到对应节点，直接改值。

5.4 单链表的销毁

销毁链表，说白了就是把所有节点都释放掉，一个不留。

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

这里有个关键点：一定要先保存下一个节点的指针，再释放当前节点。顺序反了，你就找不到下一个节点了，造成内存泄漏。

5.5 知识体系总览

下面这张图，把单链表的操作串起来了。你一看就明白。

5.6 常见错误与避坑指南

错误类型	具体表现	解决方法
内存泄漏	删除节点后没free，或者销毁链表时遗漏节点	每次删除都检查free，销毁时用循环逐个释放
野指针	free后继续使用指针，或者头指针未更新	free后立即置NULL，操作后更新头指针
断链	插入/删除时指针顺序错误，导致链表断开	先连后断：先建立新连接，再断开旧连接
空指针访问	对NULL指针解引用，或者遍历时未检查NULL	每次访问指针前都检查是否为NULL

好了，单链表的操作就讲到这里。这些代码你最好自己敲一遍，跑一跑。光看是学不会的，动手才是硬道理。