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

手撕无头单链表

news 来源：原创 2024/5/9 16:51:43
  • 💓 博客主页：江池俊的博客
  • ⏩ 收录专栏：数据结构探索
  • 👉专栏推荐：✅C语言初阶之路 ✅C语言进阶之路
  • 💻代码仓库：江池俊的代码仓库
  • 🔥编译环境：Visual Studio 2022
  • 🎉欢迎大家点赞👍评论📝收藏⭐

在这里插入图片描述

文章目录

  • 🚨一、什么是链表
    • 1.1 链表的概念
    • 1.2 链表的分类
  • 🚨二、单链表的结构
  • 🚨三、单链表的创建
    • 3.1 单链表的存储结构
    • 3.2 单链表的接口
  • 🚨四、接口实现（增、删、查、改）
    • 4.1 单链表的插入
      • 🔥前提：向内存申请节点空间
      • 📌尾插
      • 📌头插
      • 📌在pos节点之前插入x
      • 📌在pos节点以后插入x
    • 4.2 单链表的删除
      • ♨️尾删
      • ♨️头删
      • ♨️删除pos节点
      • ♨️删除pos的后一个节点
    • 4.3 单链表的其他接口实现
      • 🌟打印单链表
      • 🌟查找
      • 🌟单链表的销毁
  • 🚨五、源码
    • 5.1 `SList.h` 文件
    • 5.2 `SList.c` 文件
    • 5.3 `Test.h` 文件

🚨一、什么是链表

1.1 链表的概念

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

1.2 链表的分类

链表主要有单向、双向、带头节点、不带头节点、循环和非循环这些特点，再经过它们的互相组合就形成了 2 × \times × 2 × \times × 2 = 8种链表的结构。

此处我要讲解的是 不带头单向非循环 链表。

🚨二、单链表的结构

单向链表（又名单链表、线性链表） 是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

在这里插入图片描述

前面我们学习了顺序表，这里我们先来分析一下顺序表和单链表的优缺点：

顺序表：

优点：

  1. 访问元素时，顺序表可以在常数时间内完成（O(1)），无论数据量多大。
  2. 顺序表可以利用缓存和预读取技术进行优化，以提高访问速度。
  3. 对于随机访问和快速查找操作，顺序表通常比单链表更高效。

缺点：

  1. 顺序表在插入和删除操作上较慢，因为可能需要移动大量的元素来保持数据的连续性。这些操作的平均时间复杂度为O(n)，其中n是元素的数量。
  2. 顺序表通常需要连续的内存空间，因此当数据量非常大时，可能会面临内存分配的问题。
  3. 在顺序表中查找特定元素可能需要遍历整个数组，这在处理大量数据时可能会变得很慢。

单链表：

优点：

  1. 插入和删除操作在链表的前端和后端相对较快，时间复杂度为O(1)。
  2. 内存使用效率较高，因为每个节点只存储一个指向下一个节点的引用。
  3. 对于一些特定的问题，如反转链表或找到链表中倒数第k个元素等，单链表有较好的解决方案。

缺点：

  1. 访问链表的中间元素需要从头部开始遍历，时间复杂度为O(n)，其中n是链表的长度。
  2. 在大规模数据中，查找操作可能比其他数据结构（如数组或哈希表）慢。
  3. 由于需要额外的空间来存储指针，所以内存使用量比顺序表大。

🚨三、单链表的创建

3.1 单链表的存储结构

typedef int SLTDataType;//定义数据类型的别名，方便后续存储元素类型改变的修改//定义结点类型 
typedef struct SListNode
{SLTDataType data;//每个节点存放一个数据元素struct SListNode* next;//结构体指针，指向下一个节点
}SLTNode;

3.2 单链表的接口

// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//打印单链表
void SLTPrint(SLTNode* phead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos节点之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos节点以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个节点
void SLTEraseAfter(SLTNode* pos);
//单链表的销毁
void SLTDestroy(SLTNode** pphead);

🚨四、接口实现（增、删、查、改）

4.1 单链表的插入

  • 在插入节点之前我们首先需要动态申请一个节点来保存要插入的数据，并将此节点放在相应的位置。
  • 而申请节点的操作在所有插入函数中都需要进行，故我们可以将这个操作写成一个申请节点的函数，方便各种插入函数的调用。

🔥前提：向内存申请节点空间

// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x; newnode->next = NULL;return newnode;
}

在这里插入图片描述

📌尾插

注意：

  1. 特殊情况，当链表为空时，则需要更改链表的头指针的地址，使得它的指向不再是 NULL，而是插入的新的节点的地址。
  2. 这里需要修改链表的头指针的地址，所以在传参的时候需要传入链表头指针的地址，即接收它的形式参数为二级指针。
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL) {*pphead = newnode;//改变了结构体指针，所以传二级指针}else{SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; }tail->next = newnode;//改变的结构体，用结构体的指针即可}
}

📌头插

头插的算法比较简单，只需要将新节点的next指向链表的头，然后修改链表的头为新节点即可。即使链表为空时此算法依然成立。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead; *pphead = newnode; 
}

📌在pos节点之前插入x

这里我们需要保存 pos 节点之前那个节点的位置，所有使用一个临时结构体指针变量 prev来保存前一个节点的位置，然后将新的节点插入其中即可。

注意：

  • 特殊情况，当 pos 节点等于链表的头节点时，就需要进行头插的操作，将新的节点插入到链表的头节点之前，然后将新节点置为链表的头。
// 在pos节点之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);//要么都是空，要么都不是空 --- 当链表不为空时，pos不能为空//当链表为空，则pos必须为空//总结;pos一定要为有效节点，NULL不是有效节点//assert((!pos && !(*pphead)) || (pos && *pphead));assert(pos);//pos不为空assert(*pphead);//链表不为空SLTNode* newnode = BuySListNode(x); if (*pphead == pos){//头插newnode->next = *pphead;  *pphead = newnode; }else{SLTNode* prev = *pphead;//用来保存pos前面的那个节点while (prev->next != pos) {prev = prev->next; }prev->next = newnode; newnode->next = pos;  }
}

📌在pos节点以后插入x

因为是在 pos 之后插入，所以自动的 pos 极为插入位置的前一个节点，于是只要把新的节点插入到 pos 节点之后即可。

注意：

  • pos 不能为 NULL，因为 NULL 后面无法再插入节点
// 在pos节点以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode;
}

4.2 单链表的删除

♨️尾删

删除节点操作，首先要确保链表不为空。其次，就是当链表中只有一个节点时，删除链表后，链表变成空，此时链表的头需要置为空。

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead&&*pphead);//没有节点不需要删除//1.一个节点的删除if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else//2.多个节点的删除{//第一种删除方式//SLTNode* prev = NULL; //SLTNode* tail = *pphead; //while (tail->next != NULL)//{//	prev = tail;//	tail = tail->next;//}//free(tail);//tail = NULL;//tail是局部变量，不置空也可以，因为出了作用域tail就销毁了//prev->next = NULL;//第二种删除方式	SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next; }free(tail->next);tail->next = NULL; }
}

♨️头删

头删也需要确保链表不为空，其次就是正常的删除节点的操作，当只有一个节点时，仍然满足逻辑。

//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* cur = (*pphead)->next; free(*pphead); *pphead = cur; 
}

♨️删除pos节点

  1. 首先，确保链表不为空
  2. 其次，判断链表的头节点是否为要删除的节点：
    • 如果是，则将链表的头节点置为此时头节点的 next。
    • 如果不是，则用一个 prev 节点来保存 pos 节点的前一个节点的位置，通过 while 循环找到此节点。
// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头删*pphead = pos->next;free(pos);pos = NULL;}else{SLTNode* prev = *pphead;//用来保存pos节点之前的节点地址while (prev->next != pos) {prev = prev->next; }prev->next = pos->next; free(pos); pos = NULL; }
}

♨️删除pos的后一个节点

这

个操作比较简单，因为要删除的节点的位置的前一个节点即为 pos，所以在进行删除的时候只需要保存要删除的节点，再让 pos 的
next 指向 pos 的next 的 next ，最后 free 掉保存的这个要删除的节点即可。

注意：

  • 这里需要确保 pos 节点不为空且 pos 的 next 也不为空。
// 删除pos的后一个节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* cur = pos->next;pos->next = cur->next;free(cur);
}

4.3 单链表的其他接口实现

🌟打印单链表

此算法只需要遍历一遍单链表，并将每个节点中存储的值打印出来即可，在循环外最好加上打印 NULL 的语句，便于直观的看出链表的结构。

//打印单链表
void SLTPrint(SLTNode* phead)
{while (phead){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");
}

🌟查找

同理，只需要遍历链表即可。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//空链表可以查找while (phead){if (phead->data == x){return phead; }phead = phead->next; }return NULL;//链表为空找不到
}

🌟单链表的销毁

  1. 首先，通过assert(pphead);确认传入的链表头指针不为空，如果为空则程序会中断。
  2. 然后，定义两个指针prev和cur，其中prev指向当前节点的前一个节点，cur指向当前节点。初始时，prev为空，cur指向链表的头节点。
  3. 使用一个循环遍历链表。在循环中，首先将prev指向当前节点，然后将cur指向下一个节点。然后释放prev指向的节点的内存空间，并将prev置为空。
  4. 循环直到cur为空，即遍历完整个链表。此时，prev将会指向链表的最后一个节点。
  5. 最后，将链表的头指针设置为空，即*pphead = NULL;，表示链表已经销毁。然后输出"单链表销毁成功"。

整个过程就是从链表的头部开始，逐个释放节点的内存空间，直到链表的尾部，完成整个链表的销毁。

//单链表的销毁
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* prev = NULL;SLTNode* cur = *pphead;while (cur){prev = cur;cur = cur->next;free(prev);prev = NULL;}*pphead = NULL;printf("单链表销毁成功\n");
}

🚨五、源码

5.1 SList.h 文件

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;//定义数据类型的别名，方便后续存储元素类型改变的修改//定义结点类型 
typedef struct SListNode
{SLTDataType data;//每个节点存放一个数据元素struct SListNode* next;//结构体指针，指向下一个节点
}SLTNode;// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//打印单链表
void SLTPrint(SLTNode* phead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos节点之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 在pos节点以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个节点
void SLTEraseAfter(SLTNode* pos);//单链表的销毁
void SLTDestroy(SLTNode** pphead);

5.2 SList.c 文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"// 动态申请一个节点空间
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x; newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL) {*pphead = newnode;//改变了结构体指针，所以传二级指针}else{SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; }tail->next = newnode;//改变的结构体，用结构体的指针即可}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead; *pphead = newnode; 
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead&&*pphead);//没有节点不需要删除//1.一个节点的删除if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else//2.多个节点的删除{//第一种删除方式//SLTNode* prev = NULL; //SLTNode* tail = *pphead; //while (tail->next != NULL)//{//	prev = tail;//	tail = tail->next;//}//free(tail);//tail = NULL;//tail是局部变量，不置空也可以，因为出了作用域tail就销毁了//prev->next = NULL;//第二种删除方式SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next; }free(tail->next);tail->next = NULL; }
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* cur = (*pphead)->next; free(*pphead); *pphead = cur; 
}//打印单链表
void SLTPrint(SLTNode* phead)
{while (phead){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//空链表可以查找while (phead){if (phead->data == x){return phead; }phead = phead->next; }return NULL;//链表为空找不到
}// 在pos节点之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);//要么都是空，要么都不是空 --- 当链表不为空时，pos不能为空//当链表为空，则pos必须为空//总结;pos一定要为有效节点，NULL不是有效节点//assert((!pos && !(*pphead)) || (pos && *pphead));assert(pos);//pos不为空assert(*pphead);//链表不为空SLTNode* newnode = BuySListNode(x); if (*pphead == pos){//头插newnode->next = *pphead;   *pphead = newnode;}else{SLTNode* prev = *pphead;//用来保存pos前面的那个节点while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;  }
}// 在pos节点以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode;
}// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头删*pphead = pos->next;free(pos);pos = NULL;}else{SLTNode* prev = *pphead;//用来保存pos节点之前的节点地址while (prev->next != pos) {prev = prev->next; }prev->next = pos->next; free(pos); pos = NULL; }
}// 删除pos的后一个节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* cur = pos->next;pos->next = cur->next;free(cur);
}//单链表的销毁
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* prev = NULL;SLTNode* cur = *pphead;while (cur){prev = cur;cur = cur->next;free(prev);prev = NULL;}*pphead = NULL;printf("单链表销毁成功\n");
}

5.3 Test.h 文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"void TestSLT1()
{SLTNode* plist = NULL; SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushFront(&plist, 1); SLTPrint(plist);SLTNode* pos = SLTFind(plist, 3);//找到3的节点并返回其地址 SLTInsert(&plist, pos, 30);//在3前面插入30 SLTPrint(plist); SLTInsertAfter(pos, 40);//在3后面插入40 SLTPrint(plist); SLTPopBack(&plist);//尾删 SLTPrint(plist);  SLTPopFront(&plist);//头删 SLTPrint(plist); SLTEraseAfter(pos);//删除3后面的那个节点 SLTPrint(plist);  SLTErase(&plist, pos);//删除节点3 SLTPrint(plist); SLTDestroy(&plist);//销毁单链表 SLTPrint(plist); 
}int main()
{TestSLT1();return 0;
}

在这里插入图片描述

今天的内容就到这里了，后续我会给大家带来一些链表的 oj 题目，大家敬请期待👏

相关文章：

  • YOLOv5项目实战（3）— 如何批量命名数据集中的图片
  • 代码随想录算法训练营Day 53 || 1143.最长公共子序列、1035.不相交的线、53. 最大子序和
  • 【T690 之十一】基于方寸EVB2开发板，结合 Eclipse+gdb+gdbserver 调试 CCAT 的流程总结
  • 场景图形管理-多视图多窗口渲染示例（4）
  • redis高级案列case
  • 二十七、W5100S/W5500+RP2040树莓派Pico＜iperf 测速示例＞
  • 【数据处理】Python：实现求条件分布函数 | 求平均值方差和协方差 | 求函数函数期望值的函数 | 概率论
  • 相机通用类之LMI激光三角相机（3D），软触发硬触发（飞拍），并输出halcon格式对象
  • Linux命令--重启系统的方法
  • 电源电压范 围宽、功耗小、抗干扰能力强的国产芯片GS069适用于电动工具等产品中，采用SOP8的封装形式封装
  • Redis缓存穿透、击穿、雪崩
  • 阿里云国际站：密钥管理服务
  • 【Vue原理解析】之异步与优化
  • python接口自动化-参数关联
  • Ladybug 全景相机， 360°球形成像，带来全方位的视觉体验
  • (三)从jvm层面了解线程的启动和停止
  • angular2 简述
  • create-react-app做的留言板
  • CSS 专业技巧
  • HTML5新特性总结
  • Java 11 发布计划来了，已确定 3个 新特性！！
  • Java，console输出实时的转向GUI textbox
  • JavaScript工作原理（五）：深入了解WebSockets，HTTP/2和SSE，以及如何选择
  • java取消线程实例
  • Linux快速配置 VIM 实现语法高亮 补全 缩进等功能
  • mac修复ab及siege安装
  • spring security oauth2 password授权模式
  • 阿里云爬虫风险管理产品商业化，为云端流量保驾护航
  • 大主子表关联的性能优化方法
  • 第13期 DApp 榜单 ：来，吃我这波安利
  • 通过几道题目学习二叉搜索树
  • 网络应用优化——时延与带宽
  • 问:在指定的JSON数据中（最外层是数组）根据指定条件拿到匹配到的结果
  • 一个完整Java Web项目背后的密码
  • 策略 ： 一文教你成为人工智能（AI）领域专家
  • ​如何在iOS手机上查看应用日志
  • $$$$GB2312-80区位编码表$$$$
  • （2）nginx 安装、启停
  • (Python第六天)文件处理
  • （附源码）ssm经济信息门户网站 毕业设计 141634
  • （论文阅读30/100）Convolutional Pose Machines
  • （十） 初识 Docker file
  • （小白学Java）Java简介和基本配置
  • （一）UDP基本编程步骤
  • (转)Linux整合apache和tomcat构建Web服务器
  • （状压dp）uva 10817 Headmaster's Headache
  • ***利用Ms05002溢出找“肉鸡
  • . NET自动找可写目录
  • .net core 微服务_.NET Core 3.0中用 Code-First 方式创建 gRPC 服务与客户端
  • .net oracle 连接超时_Mysql连接数据库异常汇总【必收藏】
  • .NET 动态调用WebService + WSE + UsernameToken
  • .net 前台table如何加一列下拉框_如何用Word编辑参考文献
  • .net/c# memcached 获取所有缓存键(keys)
  • .NET/C# 判断某个类是否是泛型类型或泛型接口的子类型
  • @FeignClient注解，fallback和fallbackFactory