当前位置： 首页 > news >正文

单链表专题（完整代码版）

news 2026/6/7 14:46:09

单链表专题（完整代码版）

文章目录

  • 单链表专题（完整代码版）
    • 一、链表的概念及结构
      • 1.1 什么是链表？
      • 1.2 链表的节点结构
    • 二、单链表的完整实现
      • 2.1 节点定义与函数声明
      • 2.2 打印链表
      • 2.3 尾插（在链表末尾插入节点）
      • 2.4 头插（在链表头部插入节点）
      • 2.5 尾删（删除最后一个节点）
      • 2.6 头删（删除第一个节点）
      • 2.7 查找节点（返回第一个值为x的节点指针）
      • 2.8 在指定位置之前插入
      • 2.9 在指定位置之后插入
      • 2.10 删除指定节点
      • 2.11 删除指定节点之后的节点
      • 2.12 销毁整个链表
    • 三、测试代码示例
    • 四、链表的分类
      • 4.1 单向 or 双向
      • 4.2 带头 or 不带头
      • 4.3 循环 or 不循环
      • 4.4 实际中最常用的两种结构
    • 五、总结

一、链表的概念及结构

1.1 什么是链表？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

![链表结构示意图](https://img-blog.csdnimg.cn/direct/8c8e8e8e8e8e8e8e8e8e8e8e8e8e8e8e.png

你可以把链表想象成火车车厢：

  • 淡季时车厢可以减少，旺季时可以增加，不影响其他车厢。
  • 每节车厢独立存在，且每节车厢里都放着下一节车厢的钥匙（指针）。

1.2 链表的节点结构

每个节点由两部分组成：

  • 数据域：存放实际数据
  • 指针域：存放下一个节点的地址
structSListNode{intdata;// 数据域structSListNode*next;// 指针域，指向下一个节点};

注意：链表中的节点是动态申请的（通常从堆上申请），因此物理地址可能不连续，但逻辑上是连续的。

二、单链表的完整实现

2.1 节点定义与函数声明

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintSLTDataType;// 方便修改数据类型// 节点结构typedefstructSListNode{SLTDataType data;structSListNode*next;}SLTNode;// 函数声明voidSLTPrint(SLTNode*phead);// 打印链表voidSLTPushBack(SLTNode**pphead,SLTDataType x);// 尾插voidSLTPushFront(SLTNode**pphead,SLTDataType x);// 头插voidSLTPopBack(SLTNode**pphead);// 尾删voidSLTPopFront(SLTNode**pphead);// 头删SLTNode*SLTFind(SLTNode*phead,SLTDataType x);// 查找voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);// 在pos之前插入voidSLTInsertAfter(SLTNode*pos,SLTDataType x);// 在pos之后插入voidSLTErase(SLTNode**pphead,SLTNode*pos);// 删除pos节点voidSLTEraseAfter(SLTNode*pos);// 删除pos之后的节点voidSLTDestroy(SLTNode**pphead);// 销毁链表

为什么很多函数需要二级指针？
因为我们要修改头指针本身（例如头插、头删、销毁等操作会改变链表的头节点地址），必须传二级指针才能改变实参。

2.2 打印链表

voidSLTPrint(SLTNode*phead){SLTNode*cur=phead;while(cur!=NULL){printf("%d -> ",cur->data);cur=cur->next;}printf("NULL\n");}

2.3 尾插（在链表末尾插入节点）

voidSLTPushBack(SLTNode**pphead,SLTDataType x){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=NULL;// 空链表特殊处理if(*pphead==NULL){*pphead=newnode;return;}// 找到尾节点SLTNode*tail=*pphead;while(tail->next!=NULL){tail=tail->next;}tail->next=newnode;}

2.4 头插（在链表头部插入节点）

voidSLTPushFront(SLTNode**pphead,SLTDataType x){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=*pphead;*pphead=newnode;}

2.5 尾删（删除最后一个节点）

voidSLTPopBack(SLTNode**pphead){// 空链表if(*pphead==NULL)return;// 只有一个节点if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;return;}// 多个节点SLTNode*prev=NULL;SLTNode*tail=*pphead;while(tail->next!=NULL){prev=tail;tail=tail->next;}prev->next=NULL;free(tail);}

2.6 头删（删除第一个节点）

voidSLTPopFront(SLTNode**pphead){if(*pphead==NULL)return;SLTNode*next=(*pphead)->next;free(*pphead);*pphead=next;}

2.7 查找节点（返回第一个值为x的节点指针）

SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*cur=phead;while(cur){if(cur->data==x)returncur;cur=cur->next;}returnNULL;}

2.8 在指定位置之前插入

voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){// 如果pos是头节点，相当于头插if(*pphead==pos){SLTPushFront(pphead,x);return;}// 找到pos的前一个节点SLTNode*prev=*pphead;while(prev&&prev->next!=pos){prev=prev->next;}if(prev==NULL)return;// pos不在链表中SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=pos;prev->next=newnode;}

2.9 在指定位置之后插入

voidSLTInsertAfter(SLTNode*pos,SLTDataType x){if(pos==NULL)return;SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=pos->next;pos->next=newnode;}

2.10 删除指定节点

voidSLTErase(SLTNode**pphead,SLTNode*pos){if(*pphead==NULL||pos==NULL)return;// 删除头节点if(*pphead==pos){*pphead=pos->next;free(pos);return;}// 找pos的前一个节点SLTNode*prev=*pphead;while(prev&&prev->next!=pos){prev=prev->next;}if(prev==NULL)return;// pos不在链表中prev->next=pos->next;free(pos);}

2.11 删除指定节点之后的节点

voidSLTEraseAfter(SLTNode*pos){if(pos==NULL||pos->next==NULL)return;SLTNode*del=pos->next;pos->next=del->next;free(del);}

2.12 销毁整个链表

voidSLTDestroy(SLTNode**pphead){SLTNode*cur=*pphead;while(cur){SLTNode*next=cur->next;free(cur);cur=next;}*pphead=NULL;}

三、测试代码示例

intmain(){SLTNode*plist=NULL;// 尾插SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPrint(plist);// 1 -> 2 -> 3 -> NULL// 头插SLTPushFront(&plist,0);SLTPrint(plist);// 0 -> 1 -> 2 -> 3 -> NULL// 查找SLTNode*pos=SLTFind(plist,2);if(pos){printf("找到了节点：%d\n",pos->data);// 在2之前插入99SLTInsert(&plist,pos,99);SLTPrint(plist);// 0 -> 1 -> 99 -> 2 -> 3 -> NULL// 在2之后插入100SLTInsertAfter(pos,100);SLTPrint(plist);// 0 -> 1 -> 99 -> 2 -> 100 -> 3 -> NULL// 删除2节点SLTErase(&plist,pos);SLTPrint(plist);// 0 -> 1 -> 99 -> 100 -> 3 -> NULL}// 头删SLTPopFront(&plist);SLTPrint(plist);// 1 -> 99 -> 100 -> 3 -> NULL// 尾删SLTPopBack(&plist);SLTPrint(plist);// 1 -> 99 -> 100 -> NULL// 销毁链表SLTDestroy(&plist);return0;}

四、链表的分类

链表的结构非常多样，以下情况组合起来共有8种：

分类维度类型
单向 / 双向单向链表、双向链表
带头 / 不带头带头结点、不带头结点
循环 / 不循环循环链表、非循环链表

4.1 单向 or 双向

  • 单向链表：每个节点只有一个指向下一个节点的指针。
    ![单向链表](https://img-blog.csdnimg.cn/direct/xxx
  • 双向链表：每个节点有指向前一个和后一个节点的两个指针，可以双向遍历。

4.2 带头 or 不带头

  • 带头链表：有一个哨兵位头节点（不存储有效数据），简化插入删除操作。
    ![带头链表](https://img-blog.csdnimg.cn/direct/xxx
  • 不带头链表：头指针直接指向第一个有效节点。

4.3 循环 or 不循环

  • 循环链表：尾节点的next指向头节点，形成一个环。
    ![循环链表](https://img-blog.csdnimg.cn/direct/xxx
  • 非循环链表：尾节点的next为NULL。

4.4 实际中最常用的两种结构

  1. 无头单向非循环链表

    • 结构简单，常用于其他数据结构的子结构（如哈希桶、图的邻接表）
    • 笔试面试中出现频率很高

  2. 带头双向循环链表

    • 结构最复杂，但实现起来反而简单（因为边界条件少）
    • 常用于实际存储数据（如C++ STL中的list）

五、总结

  • 链表是动态数据结构，插入删除不需要移动元素，但需要额外的指针存储空间。
  • 单链表实现简单，但只能单向遍历，删除节点时需要找到前驱。
  • 带头双向循环链表虽然结构复杂，但操作统一，实际开发中更常用。
  • 掌握单链表是理解更复杂链表的基础，也是面试中的高频考点。
http://www.jsqmd.com/news/624856/

相关文章：

  • python学习-05列表
  • “键盘鼠标”到“听懂人话”：如何用AI语音重构大屏交互新范式？
  • Bidili Generator开源大模型：基于Stable Diffusion XL 1.0的完全本地化方案
  • 告别音效制作烦恼：HunyuanVideo-Foley私有部署镜像实测，效果惊艳
  • STGCN实战：从骨架数据到动作识别的时空建模
  • 为什么你需要PS3GameUpdateDownloader？3步掌握索尼官方游戏更新下载
  • PKHeX自动合法性插件：轻松创建合规宝可梦的智能助手
  • FX3U_F407_V50 底层源码功能说明文档
  • ReadCat小说阅读器：打造纯净无干扰的完整阅读体验指南
  • 医疗图像降噪实战：用VS2026+QT6.9+OpenCV处理X光RAW图，从对齐到超分全流程避坑
  • Pixeval：为Pixiv用户打造的现代化内容管理解决方案
  • 技术人的产品思维培养
  • 收藏！行业寒冬下，程序员薪资翻倍的秘密的是大模型（小白必看）
  • ROS2机器人建模避坑：左右轮坐标轴搞反，Gazebo转向和RViz2建图全乱了
  • Python剪映自动化实战：基于JianYingApi的第三方剪映API深度架构指南
  • 低成本Wi-Fi/蓝牙天线DIY实战：用FR4板与HFSS设计2.45GHz侧馈微带天线
  • 深度学习驱动的超构表面设计进展及其在全息成像中的应用
  • WenDoraAi官网NextJS实战03:项目插件与Header组件
  • D3KeyHelper：暗黑破坏神3玩家的终极智能助手，5分钟解放双手！
  • 告别Hough和LSD：用Python+OpenCV实战EDLines直线检测，速度提升10倍
  • Cadence Padstack实战：贴片焊盘制作避坑指南（附钢网层设置技巧）
  • VASTBASE G100 在Docker环境下的高效部署与优化实践
  • TPFanCtrl2：ThinkPad双风扇控制终极指南与完整配置方案
  • 如何完全掌控你的数字记忆？留痕项目终极指南
  • Kiro CLI Skills 实战：6 个效率工具 Skill 的设计与使用指南
  • 从拓扑地图到A*算法：深入解析Carla全局路径规划的实现原理
  • cmake之旅（12）
  • Qwen2.5-VL-Chord生产环境：7×24小时稳定运行30天故障率为0实录
  • 智能车竞赛极速越野组：从GPS导航到多线程控制的实战经验分享
  • 2025届毕业生推荐的五大AI论文网站横评