单链表核心操作全实现与指针思维精讲

如何找到 prev？从头结点开始向后遍历，直到 prev->next 指向 pos 为止。这里要注意，当 pos 为头结点的时候，执行的操作就变为了头插。

代码：

// 在指定位置之前插入
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 test1() {
    SLTNode* head = NULL;
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    SLTNode* find = SLTFind(head, 2);
    if (find)
        SLTInsert(&head, find, 7);
    SLTPrint(head); // 打印
}

运行结果：

时间复杂度： O(1)

2.2 在指定位置之后

思路： 当 pos->next = newnode 后，newnode->next = pos->next 就变成了 newnode->next = newnode，这显然是不对的。正确的逻辑是先保存 pos->next，再修改指针。

因为仅仅根据 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;
}

测试：

void test1() {
    SLTNode* head = NULL;
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    SLTNode* find = SLTFind(head, 2);
    if (find)
        SLTInsertAfter(&head, find, 7);
    SLTPrint(head); // 打印
}

运行结果：

时间复杂度： 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;
    }
}

测试：

void test1() {
    SLTNode* head = NULL;
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    SLTNode* find = SLTFind(head, 2);
    if (find)
        SLTErase(&head, find);
    SLTPrint(head); // 打印
}

运行结果：

时间复杂度： O(1)

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

测试：

void test1() {
    SLTNode* head = NULL;
    SLTPushBack(&head, 1);
    SLTPushBack(&head, 2);
    SLTPushBack(&head, 3);
    SLTNode* find = SLTFind(head, 2);
    if (find)
        SLTEraseAfter(&head, find);
    SLTPrint(head); // 打印
}

运行结果：

时间复杂度： 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); // 在指定位置之后删除
SLTNode* SLTBuyNode(SLTDataType x);                 // 节点申请

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

五、顺序表和链表的区别

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

总结

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