【初阶数据结构与算法】线性表之链表的分类以及双链表的定义与实现
文章目录
- 一、链表的分类
- 二、双链表的实现
- 1.双链表结构的定义
- 2.双链表的初始化和销毁
- 初始化函数1
- 初始化函数2
- 销毁函数
- 3.双链表的打印以及节点的申请
- 打印函数
- 节点的申请
- 4.双链表的头插和尾插
- 头插函数
- 尾插函数
- 5.双链表的查找和判空
- 查找函数
- 判空函数
- 6.双链表的头删和尾删
- 头删函数
- 尾删函数
- 7.双链表指定节点位置的操作
- 删除指定的节点
- 在指定节点前插入数据
- 三、单链表和双链表的简单对比
一、链表的分类
在上一篇中,我们简单了解了单链表,但是我们没有仔细的对链表的分类进行分析,因为我们是第一次接触到链表这种结构,所以我们先简单了解一下单链表,实现一下,现在才能对我们链表的分类有清晰的认知
接下来我们来了解一下链表的具体分类,然后从分类中找出我们上节课实现的单链表,如下:
在上面的属性中,让它们进行组合一共就会有8种分类,比如带头单向循环链表,带头单向不循环链表,带头双向循环链表等等,这里就不一一列举了,我们主要来解释一下分类里面的每组名词是什么意思
- 带头和不带头:带头和不带头不是我们之前说的头结点,之前我们的头结点是链表中存储数据的第一个节点,这里的带头是我们在创建链表时会申请一个头结点,这个头结点不存放数据,它只代表链表的头,无论我们进行删除还是增加都让它指向链表的头,它也叫哨兵位
- 单向和双向:单向链表的意思就是它只有一个next指针指向后节点,前节点可以通过next指针找到后节点,但是后节点找不到前节点。双向链表的意思就是它不仅有一个next指针指向后节点,还有一个prev指针指向前节点,前后节点可以互相访问
- 循环和不循环:不循环链表就是它的尾结点指向空指针,不会产生循环。循环链表就是它的尾结点指向头结点,这样的话整个链表就形成了循环
根据上面的分类和各种名词的解释,我们现在来判断一下我们上节课讲的单链表属于哪个分类,首先我们没有创建一个不保存数据的头节点一直指向链表头不改变,之前说的头结点是要存放数据的,并且之前的头结点有可能被改变,所以并不属于带头的链表
我们实现单链表的结构时,只有一个next指针指向下一个节点,没有prev指针指向上一个节点,所以我们可以判断出单链表属于单向的链表
最后,由于我们实现的单链表的尾结点指向空,所以它是不循环链表,最后综合一下上面的分析,我们上一篇实现的单链表其实全称应该是单向不带头不循环链表
所以我们现在就知道了,通常说的单链表虽然只说了单,但是其实它完整的名字是单向不带头不循环链表,那么我们今天要学习的双链表属于哪个类别呢?
这里就不卖关子了,我们平常说的双链表跟单链表完全是两个反面,它属于双向带头循环链表,我们在实际应用中最常用的也是双向链表,因为它的每个方法的时间复杂度都基本达到了O(1),效率比较高,只是多了一点点空间的开销,接下来我们就来学习双链表的实现
二、双链表的实现
在上面我们已经说过了,平常所说的双链表就是双向带头循环链表,它的特点我们上面已经介绍过了,接下来我们就来实现它,它的实现和单链表的实现的思路差不多,如果吃透了单链表,双链表的实现就不难了
1.双链表结构的定义
我们在上面说过,双链表属于双向链表,不仅有一个指向下一个节点的next指针,还有一个指向上一个节点的prev指针,其余和单向链表的定义差不多,如下:
typedef int LTDateType;typedef struct ListNode
{LTDateType data;struct ListNode* prev;struct ListNode* next;
}LTNode;
2.双链表的初始化和销毁
我们之前写的单链表没有初始化,但是双链表是有初始化的,因为我们说过,双链表的是带头的,初始化的目的就是为了给我们的双链表申请一个不保存数据的哨兵位
初始化函数1
初始化函数就是为了帮我们申请一个哨兵位节点,所以它可以有两种方式,一种就是我们在主函数中创建好一个节点指针,默认置为空,然后我们通过传参的方式将这个指针传给初始化函数,由初始化函数给它申请哨兵位
在初始化的时候我们要注意一点,就是我们的双向链表属于循环链表,不能把它的prev和next指针置为空,要把它们都指向哨兵位自己,否则就不循环了,至于哨兵位的数据部分是什么都不重要,可以不管,最后由于我们会改变这个指针,所以我们要传二级指针,如下:
void LTInit1(LTNode** pphead)
{assert(pphead);*pphead = (LTNode*)malloc(sizeof(LTNode));if(*pphead == NULL){perror("malloc");return;}(*pphead)->next = (*pphead)->prev = *pphead;
}
初始化函数2
还有另一种方式就是,不用接收任何参数,直接在初始化函数中创建新节点,初始化后将其返回即可,在主函数中直接接收即可,我们也推荐使用这种方式,具体原因后面再说,代码如下:
LTNode* LTInit2()
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if(*pphead == NULL){perror("malloc");return;}newnode->prev = newnode->next = newnode;return newnode;
}
销毁函数
链表有初始化就有销毁,就是没有初始化也要销毁,因为链表中的所有节点都是动态申请的,如果不释放就会导致内存泄漏,在销毁时有一个细节要注意,就是双链表的尾结点不是指向空的,而是指向哨兵位
如果我们开始就从哨兵位开始释放,那么就找不到停止释放的条件了,所以我们可以从哨兵位的下一个节点开始释放,也就是存放数据的第一个节点,一直释放到它的next指针指向哨兵位,最后我们再释放哨兵位,如下:
void LTDestroy(LTNode** pphead)
{assert(pphead);LTNode* pcur = (*pphead)->next;while (pcur->next != *pphead){LTNode* del = pcur;pcur = pcur->next;free(del);del = NULL;}free(*pphead);*pphead = NULL;
}
3.双链表的打印以及节点的申请
打印函数
打印函数还是一样的简单,只是要根据双链表的特性来做,双链表有哨兵位,所以打印要从哨兵位的下一个节点开始打印,直到遇到的节点的next指针指向哨兵位,代码如下:
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}
}
节点的申请
节点的申请还是叫我们的BuyNode,形象生动,节点的申请跟单链表差不多,只是多了一个prev指针,把它一起置为空,如下:
LTNode* LTBuyNode(LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if(newnode == NULL){perror("malloc");return NULL;}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode;
}
4.双链表的头插和尾插
我们的双链表多增加了一个prev指针,可能在上面的方法中还没有发现它的作用,在后面的函数中就会发现它有大用,基本上可以把所有函数的时间复杂度降到O(1),但是相对于单链表而言双链表的方法实现就要难一点
头插函数
由于我们的双链表有哨兵位占位子,所以我们无论是插入还是删除节点都不会影响哨兵位,不会影响哨兵位我们就可以都传一级指针,这也是哨兵位最重要的功能之一
我们也可以想到,头插就是往哨兵位的后一个位置去插入,哨兵位一直都不修改,用来表示链表的开始,由于我们双链表的指针比较多,所以我们的第一步就是来梳理一下哪些节点会受到影响
首先我们对新节点的指向进行操作,这样不会影响原链表的结构,那么新节点的prev指针要指向哨兵位,新节点的next指针指向原链表中第一个存储数据的节点,如图:
接着我们就要对原链表的指向进行修改,哨兵位的next指针要指向新节点,原链表中第一个保存数据的节点的prev指针也指向新节点
但是我们要注意一个点,就是如果我们直接修改哨兵位的next指针,就找不到原链表中第一个保存数据的节点了,所以我们要先通过哨兵位找到那个节点,然后让它的prev指针指向新节点,最后让哨兵位的next指针指向新节点,如图:
有了以上的思路,我们现在直接来写代码,如下:
void LTPushFront(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
尾插函数
尾插函数的思想也和头插差不多,在单链表中,我们如果想要找到尾结点就必须遍历整个链表,直到遇到next指针为空的节点,导致我们的时间复杂度只能是O(N),但是在双链表中要找到尾结点就很简单了,因为哨兵位的prev指针就指向了尾结点
由于是尾插,所以我们要让新节点成为尾结点,那么新节点的prev指针就要指向原本的尾结点,next指针就要指向哨兵位,如图:
新节点的指向设置好之后我们就来修改原链表,首先就是尾结点的next指针要指向新节点,哨兵位的prev指针要指向新节点,如图:
有了上面的思路我们就来实现一下代码,如下:
void LTPushBack(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
当我们写完头插和尾插后,不知道大家感受到没有,我们的头插和尾插基本上只修改了指针的指向,没有其它的开销,执行起来非常快,这就是双向链表的优势
5.双链表的查找和判空
这里我们先把查找和判空方法写出来,后面的方法可能会用到,链表的查找和判空很简单,我们一起来分析
查找函数
我们在查找时肯定是查找有效的数据,所以我们查找是从哨兵位后一个节点开始的,查找方法也很简单,遍历整个双链表,看看能否找到相应的数据,找得到就返回对应节点,找不到就返回空,如下:
LTNode* LTFinde(LTNode* phead, LTDateType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
判空函数
双链表的判空很简单,如果哨兵位的next指针指向自己,不就说明链表中没有数据吗,也就是链表为空,返回真,否则返回假
我们可以用一个巧妙的方法用一步就可以将上面的要求实现,如下:
bool LTEmpty(LTNode* phead)
{return phead == phead->next;
}
当phead等于它的next指针时,这个等式为真,刚好说明链表为空,返回真,当不相等时,等式为假,说明链表不为空,返回假,最后提醒一点,要使用bool类型,要包含头文件stdbool.h
6.双链表的头删和尾删
这里的两个方法都是删除,但是我们要强调一点,在删除的时候,是不会删除哨兵位的,它没有保存数据,帮我们把链表头存储起来而已,如果删除了下次还要特殊申请,更加麻烦了,所以我们要删除的都是哨兵位以外的节点,直到链表销毁才删除哨兵位
在删除之前我们都要对链表进行判空,如果链表为空肯定就不能删除,要结束程序,如果链表不为空才可以进行删除操作,我们的判空函数就有用处了,可以在头删和尾删的前面断言一下,如下:
assert(!LTEmpty(phead));
头删函数
头删函数就是让哨兵位的next指针指向第二个数据节点,然后第二个数据节点的prev指针指向哨兵位,最后释放掉原先的第一个数据节点,只需要改变两个指针的指向,当然,为了防止找不到要删除的节点了,我们最好把它保存一下,代码如下:
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//要删除的节点LTNode* next = phead->next->next;//第二个数据节点phead->next = new;new->prev = phead;free(del);del = NULL;
}
尾删函数
尾删函数和头删函数的实现也差不多,要进行链表判空,尾删的本质就是让尾结点的前一个节点,也就是倒数第二个节点的next指针指向哨兵位,哨兵位的prev指针指向倒数第二个节点,然后把尾结点释放掉,如下:
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;LTNode* prev = phead->prev->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
7.双链表指定节点位置的操作
我们要对指定节点位置进行操作,有一个很关键的步骤就是怎么得到指定的节点,这个就可以使用我们之前写过的查找函数,通过查找函数找到指定的数据,然后返回值就是指定数据的节点,所以我们指定位置的操作是结合查找方法使用的
删除指定的节点
这个方法和头删尾删的方法其实查不了多少,我们通过拿到的指定节点就可以找到指定节点的前后节点,然后我们就让指定节点的前后节点连接起来,释放指定的节点即可,如下:
void LTErase(LTNode* phead, LTNode* pos)
{assert(!LTEmpty(phead));pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}
当然,出来删除指定节点,还要删除指定节点前的节点和删除指定节点后的节点,方法类似,这里就不多讲了,可以自己去实现一下
在指定节点前插入数据
在指定节点前插入数据其实不难,只是可能稍微要绕一点点,所以我们画个图来解释一下更好,如图:
那么有了上图的分析,我们就来实现一下代码,如下:
void LTInsert(LTNode* phead, LTNode* pos, LTDateType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);LTNode* prev = pos->prev;newnode->prev = prev;newnode->next = pos;prev->next = newnode;pos->prev = newnode;
}
当然,还可以在指定节点后插入一个节点,这里也不再不讲,方法类似,可以试着自己去实现一下
三、单链表和双链表的简单对比
虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构:单链表和双向带头循环链表
- ⽆头单向⾮循环链表:一般称为单链表,结构简单,⼀般不会单独⽤来存数据,实际中更多是作为其他数据结构的⼦结构,如哈希桶、图的邻接表等等,另外这种结构在笔试⾯试中出现很多
- 带头双向循环链表:一般称为双链表,结构最复杂,⼀般⽤在单独存储数据,实际中使⽤的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使⽤代码实现以后会发现结构会带来很多优势,在上面的实现我们也验证了这一点
那么链表的内容我们就介绍到这里,如果有什么问题欢迎私信我,接下来的文章我们也会对链表的知识做一个融汇贯通,刷一些题
那么今天就到这里,bye~
相关文章:

【初阶数据结构与算法】线性表之链表的分类以及双链表的定义与实现
文章目录 一、链表的分类二、双链表的实现1.双链表结构的定义2.双链表的初始化和销毁初始化函数1初始化函数2销毁函数 3.双链表的打印以及节点的申请打印函数节点的申请 4.双链表的头插和尾插头插函数尾插函数 5.双链表的查找和判空查找函数判空函数 6.双链表的头删和尾删头删函…...

219页华为供应链管理:市场预测SOP计划、销售预测与存货管理精要
一、华为ISC供应链管理 华为的集成供应链(ISC)领先实践和SISC(Siyuan Integrated Supply Chain)架构体现了其在供应链管理领域的深度和广度,以下是7点关键介绍: 全面的供应链视野:华为ISC涵盖…...
mac 安装指定的node和npm版本
mac 安装指定的node和npm版本 0.添加映像: export N_NODE_MIRRORhttps://npmmirror.com/mirrors/node 1、使用 npm 全局安装 n npm install -g n 如果报了sudo chown -R 502:20 "/Users/xxx/.npm" sudo npm install -g n 2、根据需求安装指定版本的 node …...

为什么分布式光伏规模是6MW为界点?
安科瑞 Acrel-Tu1990 最近,能源局颁布了一项规定,明确指出6兆瓦(MW)及以上的分布式光伏电站必须实现自发自用,自行消纳电力。多个省份的能源局进一步规定,规模超过6兆瓦的电站需按照集中式管理进行操作。此…...
arm64架构的linux 配置vm_page_prot方式
在 ARM64 架构上,通过 vm_page_prot 属性可以修改 UIO 映射内存的访问权限及缓存策略,常见的有非缓存(Non-cached)、写合并(Write Combine)等。下面是 ARM64 常用的 vm_page_prot 设置及其对应的操作方式。…...
vue3 + naive ui card header 和 title 冲突 bug
背景描述 最近发现一个 naive ui 上的问题,之前好好的,某一次升级后就出现了一个 bug,Modal 使用 card 布局后,Header Solt 下面的内容不见了,变成了 title,因为这个 solt 里面是有操作 action 的…...
Ubuntu 22.04.5 LTS配置 bond
本次纯实验,不会讲解bond功能,配置bond mode 1 和 mode 4 如何配置 确定内核模块是否加载 实验使用root用户权限,非root用户使用sudo 调用root权限 rootubuntu22:~# lsmod | grep bonding rootubuntu22:~# modprobe bonding rootubuntu22:~# …...
100种算法【Python版】第58篇——滤波算法之卡尔曼滤波
本文目录 1 算法步骤2 算法示例2.1 示例描述2.2 python代码3 算法应用:二维运动目标跟踪问题滤波算法是用于从信号中提取有用信息、去除噪声或估计系统状态的技术。在时间序列分析、信号处理和控制系统中,滤波算法起着关键作用。 1 算法步骤 卡尔曼滤波(Kalman Filter)的…...

关于几种卷积
1*1卷积 分组卷积&深度可分离卷积 空洞卷积、膨胀卷积 转置卷积 https://zhuanlan.zhihu.com/p/80041030 https://yinguobing.com/separable-convolution/#fn2 11的卷积可以理解为对通道进行加权,对于一个通道来说,每个像素点加权是一样的&am…...

51单片机教程(五)- LED灯闪烁
1 项目分析 让输入/输出口的P1.0或P1.0~P1.7连接的LED灯闪烁。 2 技术准备 1、C语言知识点 1 运算符 1 算术运算符 #include <stdio.h>int main(){// 算术运算符int a 13;int b 6;printf("%d\n", ab); printf("%d\n", a-b); printf("%…...

VUE3中Element table表头动态展示合计信息(不是表尾合计)
一、背景 原型上需要对两个字段动态合计,输出摘要信息 原先想到是的Element的 :summary-method,发现不是动态,所以换监听来实现 二、vue代码 <el-table v-model"loading" :data"itemList"><el-table-column la…...

git重置的四种类型(Git Reset)
git区域概念 1.工作区:IDEA中红色显示文件为工作区中的文件 (还未使用git add命令加入暂存区) 2.暂存区:IDEA中绿色(本次还未提交的新增的文件显示为绿色)或者蓝色(本次修改的之前版本提交的文件但本次还未提交的文件显示为蓝色)显示的文件为暂存区中的文件(使用了…...
【Java集合面试1】说说Java中的HashMap原理?
Java中的HashMap是一种基于哈希表的Map接口实现,它存储的内容是键值对(key-value)映射。HashMap允许空键(null)和空值(null),并且它的键值对没有顺序。以下是HashMap的一些关键工作原…...

万字长文解读机器学习——决策树
🌺历史文章列表🌺 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…...
内网环境,基于k8s docer 自动发包
背景:生产环境是内网,无法连接外部git环境,需要上传tar包打成镜像,然后发布。 简单写了个脚本,记录下方便复用。 将tar包和脚本拷贝到同一个目录下。 使用方式: tar 包名称格式:服务名-版本号…...

【HCIP园区网综合拓扑实验】配置步骤与详解(已施工完毕)
一、实验要求 实验拓扑图如上图所示 1、按照图示的VLAN及IP地址需求,完成相关配置 2、要求SW1为VLAN 2/3的主根及主网关 SW2为vlan 20/30的主根及主网关 SW1和SW2互为备份 3、可以使用super vlan(本实验未使用) 4、上层…...

Qt 编写插件plugin,支持接口定义信号
https://blog.csdn.net/u014213012/article/details/122434193?spm1001.2014.3001.5506 本教程基于该链接的内容进行升级,在编写插件的基础上,支持接口类定义信号。 环境:Qt5.12.12 MSVC2017 一、创建项目 新建一个子项目便于程序管理【…...

Qt中 QWidget 和 QMainWindow 区别
QWidget 用来构建简单窗口 QMainWindow 用来构建更复杂的窗口,QMainWindow 继承自QWidget,在QWidget 的基础上提供了菜单栏、工具栏、状态栏等功能 菜单栏(QMenuBar)工具栏(QToolBar)状态栏(Q…...

Kafka集群中数据的存储是按照什么方式存储的?
1)Topic 数据的存储机制 Topic是逻辑上的概念,而partition是物理上的概念,每个partition对应于一个log文件,该log文件中存储的就是Producer生产的数据。Producer生产的数据会被不断追加到该log文件末端,为防止log文件…...

中断的硬件框架
往期内容 本专栏往期内容,interrtupr子系统: 深入解析Linux内核中断管理:从IRQ描述符到irq domain的设计与实现Linux内核中IRQ Domain的结构、操作及映射机制详解中断描述符irq_desc成员详解Linux 内核中断描述符 (irq_desc) 的初始化与动态分…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...