单链表核心操作全实现：查找、插入与删除的深度解析

时间复杂度： O(n)

在指定位置之后插入

思路： 这个操作相对简单。已知 pos，只需创建新节点，让新节点的 next 指向 pos->next，然后修改 pos->next 指向新节点即可。

注意：当 pos 为尾结点时，pos->next 为 NULL，上述逻辑依然成立，无需特殊处理。

代码实现：

// 在指定位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

时间复杂度： O(1)

三、指定位置前后删除

在指定位置删除

思路： 同样需要找到待删节点 pos 的前驱节点 prev。执行 prev->next = pos->next，然后释放 pos。

边界情况： 如果 pos 是头结点，无法通过遍历找到前驱（因为没有前驱）。此时应复用头删逻辑。

代码实现：

// 在指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos);
    // 头结点删除，复用头删逻辑
    if (pos == *pphead)
        SLTPopFront(pphead);
    else {
        SLTNode* prev = *pphead;
        // 寻找前驱
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL; // 防止野指针
    }
}

时间复杂度： O(n)

在指定位置之后删除

思路： 直接操作 pos->next。设待删节点为 del，执行 pos->next = del->next，释放 del。

风险提示： 必须确保 pos->next 不为空，否则解引用空指针会导致崩溃。因此断言中需增加 pos->next 的检查。

代码实现：

// 在指定位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos && pos->next); // 关键：确保有后继节点
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

时间复杂度： O(1)

四、完整代码展现

为了保持工程规范，我们将接口声明放在头文件，实现在源文件中，并编写测试用例。

SList.h

#ifndef __SLIST_H__
#define __SLIST_H__

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

typedef int SLTDataType;

typedef struct SLTNode {
    SLTDataType data;
    struct SLTNode* next;
} SLTNode;

void SLTPrint(SLTNode* phead);
void SLTDestroy(SLTNode** pphead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);

#endif

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

// 打印链表
void SLTPrint(SLTNode* phead) {
    SLTNode* pcur = phead;
    while (pcur) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

// 节点申请
SLTNode* SLTBuyNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        printf("开辟失败！\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

// 销毁链表
void SLTDestroy(SLTNode** pphead) {
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    *pphead = NULL;
}

// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL)
        *pphead = newnode;
    else {
        SLTNode* pcur = *pphead;
        while (pcur->next != NULL)
            pcur = pcur->next;
        pcur->next = newnode;
    }
}

// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

// 尾删
void SLTPopBack(SLTNode** pphead) {
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } else {
        SLTNode* prev = NULL;
        SLTNode* pcur = *pphead;
        while (pcur->next != NULL) {
            prev = pcur;
            pcur = pcur->next;
        }
        free(pcur);
        prev->next = NULL;
    }
}

// 头删
void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x)
            return pcur;
        pcur = pcur->next;
    }
    return NULL;
}

// 在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    if (pos == *pphead)
        SLTPushFront(pphead, x);
    else {
        SLTNode* newnode = SLTBuyNode(x);
        SLTNode* prev = *pphead;
        while (prev->next != pos)
            prev = prev->next;
        newnode->next = pos;
        prev->next = newnode;
    }
}

// 在指定位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

// 在指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos);
    if (pos == *pphead)
        SLTPopFront(pphead);
    else {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

// 在指定位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

test.c

#include "SList.h"

int main() {
    SLTNode* head = NULL;
    
    // 初始化数据
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    
    printf("初始链表：\n");
    SLTPrint(head);
    
    // 测试查找
    SLTNode* find = SLTFind(head, 2);
    if (find)
        printf("查找成功：\n");
    
    // 测试插入
    SLTInsert(&head, find, 7);
    printf("插入后：\n");
    SLTPrint(head);
    
    // 测试删除
    SLTErase(&head, find);
    printf("删除后：\n");
    SLTPrint(head);
    
    // 清理内存
    SLTDestroy(&head);
    return 0;
}

五、顺序表和链表的区别

注：缓存利用率参考存储体系结构及局部性原理。

总结

单链表的学习没有捷径，每一个指针、每一次遍历、每一段接口实现，都是夯实功底的必经之路。保持耐心，多写多练多思考，把基础打牢，复杂的算法与项目自然水到渠成。