单链表核心操作实现与指针思维解析

时间复杂度

O(n)（需遍历寻找前驱）

2.2 在指定位置之后

思路

当 pos->next = newnode 后，newnode->next = pos->next 就变成了 newnode->next = newnode，因为仅仅根据 pos 就能够找到下一个结点，不需要遍历，所以只用传两个数据就可，而且当 pos 为尾结点时插入数据，这个代码也没问题，不需要像 pos 在头结点前插入时一样重新调用一下头插函数。

代码

// 在指定位置之后插入
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 在指定位置

思路

这里还是通过遍历找到 prev 就是 pos 的前一个结点，然后让 prev->next = pos->next，然后释放掉需要删除的那个结点。当 pos 为头结点的时候，通过遍历 prev->next 并不能找不到 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)

3.2 指定位置之后

思路

但是当 pos 为尾结点的时候，pos->next 为 NULL，所以 del->next 是对空指针解引用就会报错，所以在 assert 里面再加入一个条件 assert(pos && 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

#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);      // 在指定位置之后删除

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() {
    test1();
    return 0;
}

五、顺序表和链表的区别

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

总结

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