【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）

2024-06-17 09:52
文章标签 链表 数据结构 逻辑 深入 初阶 解析 底层 探索 循环 单链 单向 无头

本文主要是介绍【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

请添加图片描述

🔥引言

本篇将深入解析单链表:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。

请添加图片描述
Alt

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
请添加图片描述

文章目录

  • 一、链表的概念
  • 二、链表的分类
  • 四、实现无头单向非循环链表的相关接口(SLTlist.h)
  • 五、知识铺垫
  • 六、正式开始模拟实现单链表
    • 6.1 创建链表中的节点
    • 6.2 单链表的插入节点
      • 6.2.1 单链表的尾插
      • 6.2.2 单链表的头插
    • 6.3 单链表的删除
      • 6.3.1 单链表的尾删
      • 6.3.2 单链表的头删
    • 6.4 查找单链表中数据
    • 6.5 关于单链表的任意位置插入和删除
      • 6.5.1 单链表的pos指定前插入
      • 6.5.2 单链表的删除pos当前结点
      • 6.5.3 单链表的pos之后插入
      • 6.5.4 单链表的pos之后删除
    • 6.6 单链表的打印
  • 七、顺序表和链表的区别

一、链表的概念

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

二、链表的分类

在这里插入图片描述

我们重点需要关注以下两个链表:

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。虽然结构复杂，但是使用代码实现，以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

链表是通过一个个结点链接起来的数据结构，多个结点链接形成下列结构(箭头是不存在，是为了方便理解)
在这里插入图片描述

下列图片会简化结点间的链接过程：

在这里插入图片描述

【注意】:

  1. 从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

  2. 现实中的节点一般都是从堆上申请出来的

  3. 从堆上申请的空间。是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

四、实现无头单向非循环链表的相关接口(SLTlist.h)

在这里插入图片描述

五、知识铺垫

1.实现部分接口需要通过二级指针接受实参

原因在于我们需要可以修改实参，而是实参为一级指针时(同样是传递地址)，需要使用二级指针进行接受，否则获得临时拷贝，不会影响到实参。修改实参的情况，比如一开始为空，在插入时需将头指针存储在有效结点的的地址上，需要改变实参的值

2.单链表的初始化

这里实现链表，没有必要进行初始化，初始化对于一开始就要开辟的空间有初始化的需求，表是多个节点通过地址链接在一起，那么只需要开辟新节点的时候，初始化下就行了(有哨兵位需要初始化)

3.二级指针断言

二级指针存放的是头节点的地址，头节点的地址为空，那么还有什么意义呢?

当我们有所了解链表的结构，接下来是实现链表的相关接口，比如增删查改

六、正式开始模拟实现单链表

6.1 创建链表中的节点

在插入中需要先创建一块结点空间，再通过上一个结点通过当前结点的地址指向当前结点的位置。这是因为结点是通过地址访问的，结点里面存储着下一个节点的地址，理解为当前结点(通过下一个结点地址)指向下一个结点

SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode==NULL){perror("malloc fail!!!");return (-1);}newnode->next = NULL;newnode->val = x;return newnode;
}

这里需要注意的是:申请到的空间交给什么类型去维护，为结点(结构体)申请空间，就需要交给结构体指针维护，同时需要注意开辟空间可能会失败，比如开辟空间多大，无法提供空间。对新结点设置了指向下一个结点为空

6.2 单链表的插入节点

插入分为三类:头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)

6.2.1 单链表的尾插

void SLTPushBack(SLNode** phead,SLNDataType x)
{assert(phead);SLNode* newnode = CreateNode(x);//值已经有了,创建一个新节点if (*phead == NULL)//这里需要二级指针去改变了，外的头了{*phead = newnode;}else{//找尾SLNode* cur =*phead;//拷贝一份while (cur->next != NULL){cur = cur->next;}cur->next = newnode;//newnode已经搞下一次是空了	}	
}

这里需要注意的是:while语句cur需要到达尾，再进行尾插的操作。同时需要考虑到特殊情况，这里我们通过if判断语句对于* pphead为空的情况，将*pphead存储在第一个结点地址。
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

6.2.2 单链表的头插

void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* cur = *pphead;*pphead = newnode;newnode->next = cur;}
}

这里需要注意的是:将*pphead移动到新节点的位置，再 * pphead指向cur(在原来的头节点位置)。同样的需要考虑到特殊情况，这里使用if判断语句对于* pphead为空的情况，将*pphead设为存储第一个结点地址。
在这里插入图片描述

6.3 单链表的删除

删除分为三类：头删\尾删\任意位置删除(其中任意位置删除，在实现查找功能先放着)

提前说明:空链表无法进行删除数据，需要在删除操作之前进行断言检查assert(*pphead)

6.3.1 单链表的尾删

void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//空的时候//一个节点和多个节点//这里不创建一个cur变量，当只有一个节点的时候，直接ppheadSLNode* cur = *pphead;if (cur->next == NULL){*pphead = NULL;free(cur);cur = NULL;}else{while (cur->next->next!= NULL){cur = cur->next;//上一个节点}free(cur->next);cur->next = NULL;}
}

这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。需要利用while循环找到删除节点的上一个节点，将上一个节点指向空，最后不要忘记free(cur->next)，释放当前节点空间。
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

6.3.2 单链表的头删

void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* cur = *pphead;if (cur->next == NULL){*pphead = NULL;free(cur);cur = NULL;}else{*pphead = cur->next;free(cur);cur = NULL;}
}

这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。cur保存当头节点位置，*pphead移动到下一个节点的位置，再free(cur)
在这里插入图片描述

6.4 查找单链表中数据

SLNode* SLTFind(SLNode* pphead, SLNDataType x)
{SLNode* cur = pphead;while (cur!=NULL){if (cur->val == x)return cur;elsecur = cur->next;}return NULL;
}

这里需要注意的是:遍历链表，找到返回当前节点，没有找到继续向下遍历

6.5 关于单链表的任意位置插入和删除

6.5.1 单链表的pos指定前插入

void SLTInsert(SLNode** pphead,SLNode *pos,SLNDataType x)//pos指定之前插入
{assert(pphead);assert(*pphead);if (pos == NULL)//没有节点{SLTPushFront(pphead, x);}if (*pphead == pos)//一个节点{SLTPushFront(pphead, x);}else//多个节点{SLNode* newnode = CreateNode(x);SLNode* cur = *pphead;while (cur->next != pos)//上面避免了pos等于cur{cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}

这里需要注意的是:需要分为三种情况，空节点，一个节点，多个节点就行处理。空节点调用尾插或者头插都可以，一个节点(在pos前插入)那么可以调用头插
在这里插入图片描述

6.5.2 单链表的删除pos当前结点

void SLTEeara(SLNode** pphead, SLNode* pos)
{assert(pphead);//防止用户传个空指针assert(*pphead);assert(pos);SLNode* next = pos->next;SLNode* cur = *pphead;if (cur==pos)*pphead = NULL;free(cur);cur = NULL;else{while (cur->next != pos){cur = cur->next;}cur->next = next;free(pos);pos = NULL;}
}

这里需要注意的是：分为两种情况，存在一个节点和多个节点的处理。如果使用三个变量，需要使用到的地址不会丢失，就不需要担心先后顺序问题。结点是一块块的独立空间，其链接方式也是较灵活的，这里跟上面方法是类似的。
在这里插入图片描述

如果不想在pos之前插入\删除，可以改动逻辑在pos之后进行插入、删除。

6.5.3 单链表的pos之后插入

void SLTInsertAfter(SLNode **pphead,SLNode* pos, SLNDataType x)
{assert(pphead);assert(*pphead);if (pos == NULL)//没有节点{SLTPushFront(pphead, x);}if (*pphead == pos)//一个节点{SLTPushBack(pphead, x);}else//多个节点{SLNode* newnode = CreateNode(x);SLNode* back = pos->next;newnode->next = back;pos->next = newnode;}
}

6.5.4 单链表的pos之后删除

void SLTEearaAfter(SLNode **pphead,SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);SLNode* cur = *pphead;SLNode* back = pos->next;if (cur == pos)//只有一个结点SLTPopBack(pphead);if(back->next==NULL){free(back);back = NULL;pos->next = NULL;}else{pos->next = back->next;free(back);back = NULL;}
}

上面的两个接口实现过程跟SLTInsert、SLTEeara实现类似的，看看代码就能理解

在完成了单链表的核心接口，我们需要继续完善剩下的接口，使实现的单链表功能更加丰富起来。

6.6 单链表的打印

void SLTPrint(SLNode** pphead)//二级指针改变外的结构体指针类型
{assert(pphead);SLNode* cur = *pphead;while (cur!= NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}

这里需要注意的是：当cur==NULL时，没有进去循环，需要额外打印NULL，最后不要忘记单链表的销毁

void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);//这里cur不要赋空，还需要使用的cur = next;
}*pphead = NULL;
}

这里需要注意的是：链表是通过多个节点链接而成的，同时也是一块块独立空间，通过cur去访问每一个空间和释放每一块空间。其中free指针跟指针变身是没有关系的，释放的是指针所指向的那一块动态空间

七、顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定 连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除 元素可能需要搬移元素，效率低 O(N)只需修改指针指向
插入动态顺序表，空间不够时需要 扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。

请添加图片描述

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！

这篇关于【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1069120。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2