跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客GitHub 精选镜像工具UI配色美学隐私政策关于联系
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C算法

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

单链表通过指针连接节点，支持动态内存分配。详解查找、指定位置前后插入及删除的核心逻辑与 C 语言实现。重点解析指针操作细节，如头插尾删边界条件、空指针处理及内存释放，对比顺序表差异，帮助夯实底层数据结构基础。

292440837发布于 2026/3/26更新于 2026/6/325 浏览
单链表核心操作全实现与深度精讲

在这里插入图片描述

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

一、查找

遍历是查找的核心逻辑。我们让当前指针 pcur 指向头结点，进入循环判断。当 pcur 不为空时，检查其数据域是否等于目标值 x。如果相等，直接返回该节点；否则将 pcur 移动到下一个节点继续判断。若遍历结束仍未找到，则返回 NULL。

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 节点之前插入新节点，关键在于找到 pos 的前驱节点 prev。我们需要从头开始遍历，直到 prev->next 指向 pos。此时，将 newnode->next 指向 pos，prev->next 指向 newnode 即可完成插入。这里有个特殊情况：如果 pos 本身就是头结点，那么操作等同于头插，可以直接复用头插逻辑。

在这里插入图片描述

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

五、顺序表和链表的区别

在这里插入图片描述

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

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

目录

  1. 一、查找
  2. 二、指定位置之前或之后插入元素
  3. 2.1 在指定位置之前
  4. 2.2 在指定位置之后
  5. 三、指定位置删除或指定位置之后删除
  6. 3.1 在指定位置
  7. 3.2 指定位置之后
  8. 四、代码展现
  9. 4.1 SList.h
  10. 4.2 SList.c
  11. 4.3 test.c
  12. 五、顺序表和链表的区别
  • 💰 8折买阿里云服务器限时8折了解详情
  • Magick API 一键接入全球大模型注册送1000万token查看
  • 🤖 一键搭建Deepseek满血版了解详情
  • 一键打造专属AI 智能体了解详情
极客日志微信公众号二维码

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

微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog

更多推荐文章

查看全部
  • C++元编程进阶指南：构建可复用代码生成器
  • 本地知识库与 RAG 技术详解：大模型如何结合外部资料库
  • Github Copilot 使用异常排查与解决方案
  • 灵感画廊：基于 Stable Diffusion XL 的极简 AI 绘画体验
  • 基于 DeepSeek 和 Cursor 构建智能代码审查工具实战
  • WordPress 基础配置与 Spring Boot 接口开发实战记录
  • 路径类动态规划入门：3 道经典例题详解
  • 优化 LLM 落地成本与响应延迟的实用策略
  • 医疗 AI Agent 可信构建：不确定性治理与贝叶斯增强
  • Python 将 Markdown 文件转换为 Word（docx）完整实现
  • LLaMA-Factory 微调 Qwen3-VL 详细流程
  • LangChain-Chatchat Windows 本地部署指南
  • 企业微信视频号去水印解析机器人搭建指南
  • FPGA 数字运算与控制：浮点数实现与 PID 算法
  • Xinference 实测：Llama3-70B、Qwen2-VL 与 Whisper 并发
  • 前端数据可视化工具选型指南：如何匹配需求与性能
  • DeepSeek-OCR-WEBUI 高性能 OCR 文本识别部署全流程
  • 基于 DeepSeek 的 AI 对话系统构建：Spring Boot + 前端实战指南
  • 使用 Higress 将 REST API 转换为 MCP Server 工具
  • LangChain v1.0 中间件机制：AI Agent 上下文控制指南

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如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