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

数据结构：单链表

news 2026/5/24 23:30:02

本专栏的上一篇文章讲的是线性表的顺序存储结构，存在着一些弊端，比如在在中间位置或者头部位置插入删除的时候，时间复杂度是O(n),每次扩容都是以二倍的形式来扩容的，很有可能会导致，空间大了用不完的情况

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，意味着数据可以存储到内存未被占用的任意位置。在顺序存储结构中只需要存储数据元素的信息就可以，但是在链式存储结构中除了存储数据元素的信息外，还是需要存储它后继元素的存储地址

一、线性表的链式存储结构的特点

1. 定义

链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储具体的数据，指针域则存储指向下一个节点的地址（引用）。通过这种指针的连接，各个节点得以串连起来形成链表。指向链表第一个节点的指针叫做头指针，链表的第一个节点通常被称作头节点，而最后一个节点的指针域一般会指向空(NULL)。单链表是逻辑上相邻，物理上不一定相邻的链式存储结构

2. 特点

优点：

（1）链表可以动态的添加和删除节点，不需要提前确定申请的大小，不用担心内存浪费的情况

（2）插入删除操作高效，只需要修改结点的指针域，时间复杂度为O(1)【只是插入删除的过程，不包括遍历，如果是加上遍历的话，尾插尾删O(n),头插头删O(1)】

缺点：

（1）由于链表的结点在内存中不是连续存储的，所以要访问其中一个元素，就必须从开始遍历，直到找到目标节点，因此链表随机访问的时间复杂度是O(n),就跟顺序表的按值查找的时间复杂度一样

（2）额外的内存开销，除了需要开辟内存空间，还需要开辟额外的空间来存储指针域

二、单链表的实现

1. 结构体定义

//类型重命名 typedef int Elemtype; //结构体定义 typedef struct Node { Elemtype data;//数据域 struct Node* next;//指针域，指向下一个同类型链表结点 }Node;

2. 初始化函数

plist是指向头结点的头指针，plist->next=nullptr,代表当前链表没有其他结点

//初始化 void Init_Node(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.对辅助结点初始化 //数据域浪费掉 // plist->data //指针域指向空 plist->next = nullptr; }

3. 购买新节点

//购买新节点，同类型结点 Node* buyNode(Elemtype val) { //1.购买新节点 Node* pnewnode = (Node*)malloc(sizeof(Node)); //2.判断结点是否购买成功 if (pnewnode == nullptr) exit(EXIT_FAILURE); //3.将数据域和指针域更新 pnewnode->data = val; pnewnode->next = nullptr; //4.购买成功返回新节点的地址 return pnewnode; }

首先需要用malloc在堆区申请一个新节点

然后判断节点是否购买成功

然后将需要插入的数据放入新节点

新节点的指针域置空

然后返回新购买节点的地址

4. 获取有效长度

//获取有效长度 int get_length(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.循环遍历 int len = 0; for (Node* p = plist->next; p != nullptr; p = p->next) len++; return len; }

5. 判空

如果辅助节点的指针域指向空就证明链表空了

bool IsEmpty(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.如果辅助节点的指针域指向空就证明链表空了 return plist->next = nullptr; }

6. 插入数据

6.1 头插

bool Insert_head(Node* plist,Elemtype val) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.购买新结点 Node* pnewnode = buyNode(val); //3.将新节点插入链表 //先将新节点接上后继结点 pnewnode->next = plist->next; plist->next = pnewnode; return true; }

首先需要进行安全判断

然后调用购买新节点的函数购买新节点

将新节点插入链表，首先需要新节点需要先保存后继节点的地址，然后辅助节点再连接新节点

6.2 尾插

//尾插 bool Insert_back(Node* plist, Elemtype val) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.申请新结点 Node* pnewnode = buyNode(val); //3.遍历到链表结尾，将新节点接入链表 Node* p = plist; for (; p->next != nullptr; p = p->next); p->next = pnewnode; return true; }

首先是安全判断

然后申请新节点

然后申请一个Node* 类型的指针，指向辅助节点，然后循环遍历的条件是指向的下一个指针域不为空，遍历到最后

然后将新节点插入

6.3 任意位置插入

//任意位置插入 bool Insert_pos(Node* plist, Elemtype val, int pos) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.边界判断 if (pos<1 || pos>get_length(plist) + 1) return false; //2.申请新结点 Node* pnewnode = buyNode(val); //3.遍历到pos Node* p = plist; for (int i = 0; i < pos - 1; i++) p = p->next; //4.将新节点插入链表 pnewnode->next = p->next; p->next = pnewnode; return true; }

首先安全判断

然后进行pos的边界条件判断，pos的合法范围是1<=pos<=get_length+1,因为是从第一个有效节点开始算的

申请一个新节点

然后遍历到要插入位置的前一位，进行新节点的插入

7. 删除数据

7.1 头删

//头删 bool delete_head(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点 Node* q = plist->next; //3.用辅助节点接上待删除结点的后继 plist->next = q->next; free(q); q = NULL; return true; }

首先进行安全判断

然后判空，如果链表已空，结束

找到待删除结点

先用辅助节点连接待删除节点的后继结点

然后再释放待删除节点,将堆空间释放，然后再将待删除置节点置空，防止二次释放

7.2 尾删

//尾删 bool delete_back(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点 Node* q = plist; //4.待删除节点的前驱结点 Node* p = plist; //5.找到待删除节点 for (; q->next != nullptr; q = q->next); //6.找到待删除节点的前驱 for (; p->next != q; p = p->next); //7.跨越指向 p->next = q->next; free(q); q = NULL; return true; }

首先安全性处理，并判断当前链表是否为空链表，如果是空链表，则结束当前进程。

若不是，定义一个Node* 类型的指针p ，让其指向头节点，通过循环遍历使 p 指向待删除节点的前一个节点位置，再定义一个辅助节点q ，使其指向待删除节点（即 p->next），然后跨越待删除结点(修改辅助结点的指针域)。

最后free(q)，将堆空间释放，然后再将待删除置节点置空，防止二次释放

7.3 按位置删

//按位置删 bool delete_pos(Node* plist, int pos) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //2.5 边界判断 if (pos < 1 || pos>get_length(plist) + 1); //3.定义待删除节点的前驱节点 Node* p = plist; //4.定义待删除节点 Node* q = plist; //5.找到待删除节点的前驱 for (int i = 0; i < pos - 1; i++) p = p->next; //6.找到待删除结点 q = p->next; //7.跨越指向 p->next = q->next; free(q); q = NULL; return true; }

首先安全判断

边界值判断，1<pos<get_length()+1

定义待删除节点的前驱结点和待删除节点

遍历到待删除节点的前驱，直接得到待删除节点，然后跨越指向，释放待删除节点

将待删除节点置空，防止二次释放

7.4 按值删（只删除这个值出现的第一次）

和按位置删除很相似，就是把给的pos换成了search(plist,val)返回地址

//按值删（只删除这个值出现的第一次） bool Del_Val_First(Node* plist, Elemtype val) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.查找这个值的地址(就是待删除节点的地址) Node* q = search(plist, val); //4.找到待删除的前驱结点 Node* p = plist; for (; p->next != q; p = p->next); //5.跨越指向 p->next = q->next; free(q); q = NULL; return true; }

7.4 按值删（删除这个值出现的所有）

//按值删（只删除这个值出现的所有位置） bool Del_Val_ALL(Node* plist, Elemtype val) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点的前驱和待删除节点 Node* p = plist; Node* q = plist->next; //4.进入while,条件是q!=nullptr while (q->next != nullptr) { //5.如果是要删的值，跨越指向，然后q等于前驱的下一个节点 if (q->data == val) { p->next = q->next; free(q); q = p->next; } //如果不等两指针均后移一个 else { p = p->next; q = q->next; } } }

首先安全判断

然后判空，若为空，返回

然后申请待删除结点和待删除节点的前驱节点

然后判断q的数据域是否为val,是的话跨越执向，然后释放q，然后给q移到p的下一个

不是的话两个指针均后移一个

8.元素查找

//有效元素查找 Node* search(Node* plist, Elemtype val) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) exit(EXIT_FAILURE); //2.返回有效元素地址 for (Node* p = plist->next; p != nullptr; p = p->next) { if (p->data == val) { return p; } } return NULL; }

9. 销毁

//销毁 void destory(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) exit(EXIT_FAILURE); //2.无限头删 while (delete_head(plist)); }

10. 打印

//打印 void show(Node* plist) { //1.安全判断 assert(plist != nullptr); if (plist == nullptr) exit(EXIT_FAILURE); //2.循环遍历 printf("当前链表元素有："); for (Node* p = plist->next; p!=nullptr; p = p->next) { printf("%d ", p->data); } printf("\n"); }

11. 测试

int main() { Node s; Init_Node(&s); Insert_head(&s, 3); show(&s); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 5); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 3); show(&s); printf("%d\n", get_length(&s)); printf("%d\n", IsEmpty(&s)); Insert_pos(&s, 5, 2); show(&s); delete_head(&s); show(&s); delete_back(&s); show(&s); delete_pos(&s, 2); show(&s); printf("%p\n", search(&s, 3)); Del_Val_First(&s, 3); show(&s); Del_Val_ALL(&s, 3); show(&s); destory(&s); return 0; }
http://www.jsqmd.com/news/880146/

相关文章：

  • Fiddler HTTPS抓包失败根源：证书信任链与客户端TLS栈适配
  • Linux渗透测试实战命令指南：从信息收集到横向移动
  • Python算法基础篇之深度优先搜索（DFS）
  • CSS伪类详解：从基础到高级应用
  • Python算法基础篇之广度优先搜索（BFS）
  • MinIO CVE-2023-28432权限绕过漏洞深度解析与加固实践
  • 国内主流HR系统供应商盘点：聚焦数智化落地能力 - 互联网科技品牌测评
  • 【Sora 2视频后期处理黄金法则】：20年AI影像专家亲授5大不可绕过的帧级调优技巧
  • Kubernetes事件驱动架构设计：构建响应式微服务系统
  • Flutter Widgets组件详解：从基础到高级
  • Gemini SQL生成准确率暴跌87%？揭秘模型幻觉的4个致命诱因及实时校验方案
  • 网络技术05-TCP拥塞控制算法——从CUBIC到BBR的性能进化
  • 量子机器学习模型安全：反向工程威胁与防御策略解析
  • Kubernetes成本优化与资源管理：降低云原生基础设施成本
  • Hugging Face下载私有数据集报错？三步搞定Token认证与本地路径配置（附Python代码）
  • 独立开发者如何选择与接入适合自己预算的模型API
  • 保姆级教程：用Python+OpenCV玩转CULane车道线数据集（附完整可视化代码）
  • 上位机知识篇---安装包文件名各部分的含义
  • phpMyAdmin CVE-2014-8959文件包含漏洞实战解析（Windows平台）
  • 掌握AI技能配置技巧 大幅提升日常办公开发效率
  • 【限时解密】DeepSeek未开源的缓存冷热分离算法：基于访问熵+时间衰减双因子动态权重模型
  • 中小企业AI落地成本杀手！DeepSeek计费冷知识曝光（含4个可立即启用的免费优化开关）
  • 信创中间件深度解析：东方通TongWeb vs 金蝶天燕 vs 宝兰德，企业级选型指南
  • Gemini模型迭代、推理成本、合规折旧、业务适配率——四大价值损耗源深度拆解，附可落地的季度健康度自检表
  • 深度剖析Claude Code实操逻辑，解锁AI编程高效开发方式
  • Taotoken 模型广场在项目技术选型阶段提供的便利体验
  • 【linux学习】进程的概念和在linux系统下的基本实现情况01
  • 2026 四川建筑钢材怎么选？西南 TOP 经销商维度拆解：行情、价格与采购指南 - 四川盛世钢联营销中心
  • HexStrike AI v6.0：面向红队实战的可审计智能体渗透框架
  • 《当下的力量》7-10章终章解读：从临在到臣服，活出生命的终极自由