目录
前言:
1.先看结构:
2.创建节点
3.初始化链表
4.打印链表
5.判空
6.尾插
7.头插
8.尾删
9.头删
10.查找与修改
修改:
11.插入---在pos之前插入
12.删除---删除pos
13.销毁
总结:
前言:
继上一章的单链表,再介绍一个更加方便的链表---双向带头循环链表:
带头即哨兵位的头节点,双向即前后节点间建立了联系,循环即尾节点可以回到头节点即循环。
1.先看结构:
由图中可以看出,每个节点被分为了三部分,比单链表多了一个什么呢?肯定也是指针啦,如果中间部分存储数据,那我们就让前后部分分别称为prev指针和next指针吧:
2.创建节点
与单链表不同的是,这次我们等下再说遍历,原因下面再讲:
一样需要注意要返回新的节点就要动态开辟出来,因为节点是一个局部的指针,开辟出来就让它放在堆区了,就可以直接返回了(后面c++有了传引用返回与new会更方便)
3.初始化链表
1.首先,由于不像单链表一样,最后指向NULL,我们就要初始化链表,我们只需要创建一个头节点,让它的头尾指针都指向它自己即可。
2.这里哨兵位的数据可以是链表的长度,是链表的长度的话再添加数据的时候就要phead->data++一下,但是如果存储的是char类型的数据,就会面临着如果超过128就会溢出的风险,所以这里使用的是一个无效的数据。
3.记得最后返回哨兵位的头节点。
4.打印链表
1.断言phead是因为后面要解引用(这里说明一下,循环链表没有使用二级指针是因为二级指针在这里显的有些麻烦,有两个指针,并且前后节点和头尾节点都有了联系,不需要再用二级找指向再修改了,直接有了一个或者头都能找到其他的),并且从意义上说phead是空,那哨兵位就干没了。
2.注意循环条件cur与单链表不同了,直到走到与头节点相同才算遍历了一遍。
5.判空
由于后面要删除数据,而只有哨兵位是不能删的,所以认为只有哨兵位是空的。
6.尾插
1.先找到尾节点,尾节点是什么呢?这就用到了循环链表的特性了,单链表此时还需遍历一遍链表,而循环链表的头节点即哨兵位的prev不就是尾节点吗?
2.接下来就让尾节点的next指向newnode,让newnode的prev指向为节点,再建立尾节点与头节点的关系即可,前后顺序其实可以改变(前提是要定义了尾指针tail,避免头节点的prev产生改变而找不到尾节点了,其实只要保证链表不会断的原则怎么写都行)。
3.只有一个哨兵位这样写能不能行呢?带进去,答案是可以,这就是双向循环链表的好处,不用考虑只有一节点的情况了,因为头节点转了一圈还是指向自己,再加一个新节点找尾节点不还是头节点吗?新节点再建立与头节点的联系不还是与它建立联系吗?说着可能有点绕,建议代入一下即可体会到,下面的函数都是如此。
7.头插
1.这里同样有很多写法,还是只要保证链表不断即可。
2.这里就要先找头(这里可不是哨兵位了,头节点是哨兵位的下一个,头插也是在哨兵位的下一个插入)start,再建立哨兵位,新节点,start的关系即可。
3.这里可以发现,只有哨兵位,这样写也是可以插入的。
8.尾删
1.只有头节点不能删,所以断言链表不是空。
2.也可以再记录一个尾指针的前一个指针。
3.注意要记录尾节点,不让phead的prev改变指向后就找不到尾节点了,释放的时候就找不到了。
9.头删
与尾删要注意的内容一样。
10.查找与修改
1.这里不用断言空链表,就算只有哨兵位,也是可以找,找不到直接返回NULL嘛。
修改:
11.插入---在pos之前插入
1.在pos位置插入不就是在pos之前插入然后往后挪到数据嘛(但是链表就不用挪到数据了)。
12.删除---删除pos
1.也可以定义pos的前后节点,那样更清晰。
13.销毁
1.注意最后要释放哨兵位,并再外面置空。文章来源:https://www.toymoban.com/news/detail-827054.html
文章来源地址https://www.toymoban.com/news/detail-827054.html
总结:
双向带头循环链表只要注意好不让链表断的前提,再加上单链表的基础,基本3遍之内结合图就可以转换成代码,当然有很多写法,还是那句话,数据结构是很灵活的,本人在很长时间没复习且第一次复习链表的前提下大概1遍都能写成,相信仔细阅读后都能有所收获!
到了这里,关于“车裂”链表---双向带头循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!