单链表核心操作全实现与深度精讲

// 在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    // 只有一个节点或者 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 之后插入相对简单，不需要遍历前驱。只要修改两个指针：newnode->next 指向 pos->next，然后 pos->next 指向 newnode。即使 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;
}

测试代码：

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 在指定位置

删除 pos 节点同样需要找到它的前驱 prev。逻辑是 prev->next = pos->next，然后释放 pos。但要注意，如果 pos 是头结点，无法通过 prev->next 找到它（因为 prev 不存在），此时应直接调用头删函数。

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 不为空，否则解引用会报错。因此断言中要增加 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); // 在指定位置之后删除

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

五、顺序表和链表的区别

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

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