单链表核心操作实现与详解 | 极客日志

C算法

单链表核心操作实现与详解

综述由AI生成单链表作为线性表的基础结构，其核心操作包括查找、插入与删除。文章详细拆解了指定位置前后插入及删除节点的指针逻辑，涵盖头插、尾插、头删、尾删等接口实现。通过代码示例展示内存管理细节，并对比顺序表与链表特性，帮助读者掌握指针操作与数据结构底层原理。

Pythonist发布于 2026/3/26更新于 2026/5/1610 浏览

前言

单链表是数据结构中最基础也最核心的线性表之一，熟练掌握其查找、指定位置插入与删除等操作，是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口，详细拆解每一步思路与代码细节，帮助大家真正理解指针操作与链表结构，夯实编程基础。

一、查找

思路： 遍历：pcur 指向头结点，循环，当 pcur 不为空进入循环，pcur 里面指向的数据为要查找的值的时候就返回 pcur，否则将 pcur 下一个结点的地址赋值给 pcur 然后继续判断，直到找到值。如果为空直接返回。

代码：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x)
            return pcur;
        pcur = pcur->next;
    }
    return NULL;
}

测试：

// 测试查找
void test1() {
    SLTNode* head = NULL;
    SLTPushFront(&head, 1);
    SLTPushFront(&head, 2);
    SLTPushFront(&head, 3);
    SLTNode* find = SLTFind(head, 1);
    if (find)
        printf("找到了！\n");
    else
        printf("未找到\n");
}

运行结果：

查找结果

时间复杂度： O(n)

二、指定位置之前或之后插入元素

2.1 在指定位置之前

思路： 头文件不能为空，也不能在空之前插入结点，首先要找到 pos 位置的前一个结点让它的 next 指针指向 newnode，然后让 newnode 的 next 指针指向 pos。如何找到 pos 的前一个结点？那就是遍历，从头结点开始，向后遍历，直到 prev 的 next 指针指向 pos 则就是 pos 的前一个结点。这里要注意，当 pos 为头结点的时候，执行的操作就变为了头插。

插入前示意图

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。在线工具，Gemini 图片去水印在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

// 在指定位置之前插入
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); // 打印
}

// 在指定位置之后插入
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); // 打印
}

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); // 打印
}

// 在指定位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos);
    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); // 打印
}

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

#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);
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

#include "SList.h"

int main() {
    test1();
    return 0;
}

单链表核心操作实现与详解

前言

一、查找

二、指定位置之前或之后插入元素

2.1 在指定位置之前

更多推荐文章

相关免费在线工具

2.2 在指定位置之后

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

3.1 在指定位置

3.2 指定位置之后

四、代码展现

4.1 SList.h

4.2 SList.c

4.3 test.c

五、顺序表和链表的区别

总结

更多推荐文章

相关免费在线工具

单链表核心操作实现与详解

前言

一、查找

二、指定位置之前或之后插入元素

2.1 在指定位置之前

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

2.2 在指定位置之后

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

3.1 在指定位置

3.2 指定位置之后

四、代码展现

4.1 SList.h

4.2 SList.c

4.3 test.c

五、顺序表和链表的区别

总结

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具