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

此操作时间复杂度为 O(1)。即使 pos 是尾结点，代码依然有效，因为 pos->next 为 NULL，新节点自然成为新的尾结点。

指定位置前后删除元素

在指定位置删除

删除 pos 节点同样需要找到其前驱节点 prev。修改 prev->next 指向 pos->next，然后释放 pos 内存。注意处理 pos 为空的情况（虽然断言已覆盖），以及 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; // 防止野指针
    }
}

在指定位置之后删除

删除 pos 的下一个节点时，需确保 pos->next 不为空。如果 pos 是尾结点，其后继不存在，此时不应进行删除操作，需在断言中增加检查。

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

完整代码实现

以下是完整的单链表头文件与源文件实现，包含了节点定义、内存分配及所有核心接口的封装。

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 SLTDestory(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 SLTDestory(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);
        pcur = NULL;
        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;
    
    // 构建链表：1 -> 2 -> 3
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    
    SLTPrint(head);
    
    // 查找并插入测试
    SLTNode* find = SLTFind(head, 2);
    if (find) {
        SLTInsertAfter(&head, find, 7);
        SLTPrint(head); // 输出：1->2->7->3->NULL
    }
    
    // 清理资源
    SLTDestory(&head);
    return 0;
}

顺序表和链表的区别

顺序表和链表是两种最常见的线性表存储方式。顺序表在内存中连续存储，支持随机访问，缓存利用率高，但插入删除效率低且扩容成本高。链表通过指针链接节点，内存不连续，不支持随机访问，但插入删除效率高，空间利用灵活。

在实际开发中，选择哪种结构取决于具体的使用场景：频繁查询选顺序表，频繁增删选链表。

总结

单链表的操作看似简单，实则对指针的理解要求很高。每一个 next 的赋值、每一次 free 的时机，都关系到程序的稳定性。建议读者多动手画图模拟指针变化，结合调试器观察内存状态，才能真正掌握链表思维。