单链表核心操作全实现与深度解析

时间复杂度： O(n)

2.2 在指定位置之后插入

实现思路： 此操作只需知道 pos 即可，无需遍历找前驱。直接将 newnode->next 指向 pos->next，再让 pos->next 指向 newnode。即使 pos 为尾结点，逻辑依然成立（newnode->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)

三、指定位置删除或指定位置之后删除

3.1 在指定位置删除

实现思路： 同样需要找到 pos 的前一个节点 prev。令 prev->next = pos->next，然后释放 pos。 若 pos 为头结点，无法通过遍历找到前驱，此时应调用头删函数 SLTPopFront。 注意：删除后需将 pos 置为 NULL，避免野指针。

代码实现：

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)

3.2 指定位置之后删除

实现思路： 直接操作 pos->next。需注意断言条件，当 pos 为尾结点时，pos->next 为 NULL，解引用会报错。因此断言中需增加 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)

四、完整代码展现

4.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 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

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

4.3 test.c

#include "SList.h"

int main() {
    SLTNode* head = NULL;
    
    // 初始化
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    
    SLTPrint(head);
    
    // 查找并插入
    SLTNode* find = SLTFind(head, 2);
    if (find)
        SLTInsertAfter(&head, find, 7);
    
    SLTPrint(head);
    
    // 删除
    find = SLTFind(head, 7);
    if (find)
        SLTErase(&head, find);
    
    SLTPrint(head);
    
    SLTDestory(&head);
    return 0;
}

五、顺序表和链表的区别

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

总结

单链表的操作看似简单，实则对指针的把控要求极高。每一个 next 的赋值、每一次 free 的时机，都关系到程序的稳定性。建议在实际编码中多画图辅助思考，理清指针指向关系后再动手写代码。基础扎实了，后续面对更复杂的树、图结构时才能游刃有余。