带头的循环双向链表的简单介绍

 

目录

带头的循环双向链表：

1、带头：

2、循环：

3、双向：

图例： 

带头的双向循环链表的创建：

头文件部分：

主函数部分：

最终调试效果：

 使用一级指针传参的原因：

开辟空间函数：

尾插操作： 

头文件部分：

源文件部分：

主函数部分：

打印函数： 

源文件部分： 

主函数部分：

打印效果：

 头插：

源文件部分：

头文件部分：

主函数部分：

 尾删：

源文件：

头文件：

主函数部分：

 头删：

源文件部分：

头文件部分： 

主函数部分：

查找位置函数：

源文件部分：

主函数部分：

 在指定位置之后插入数据：

指定位置之后插入数据分为两种情况：

情况1：

情况2：

源文件：

主函数部分：

删除指定位置的节点：

 源文件部分：

主函数部分：

 销毁链表：

销毁链表的本质：

同时销毁链表也分为两种传参形式：

传一级指针：

源文件部分：

主函数部分：

头文件：

传二级指针：

源文件部分：

头文件部分：

 主函数部分：

传一级指针和二级指针的区别：

顺序表和双向链表的区别：

---

带头的循环双向链表：

1、带头：

• 带头顾名思义，在链表的最前方有一个存储着无效数据的节点，这个节点是该链表的头节点。
• 且该节点的地址是不允许修改的，除非是将整个链表进行销毁释放。
• 一般，对于这种节点，我们称之为"哨兵位"

2、循环：

• 在先前的约瑟夫问题中，我们遇到了环形结构的链表，循环也是如此。

环形链表的约瑟夫问题-CSDN博客https://blog.csdn.net/2301_76445610/article/details/133930944?spm=1001.2014.3001.5501

• 循环链表的关键就在于，节点的最后一个节点，它内部的指针指向的是节点的第一个节点，以此造成环状形态，也是循环形态，当我们在遍历链表的时候，会因此进入循环。

3、双向：

• 关于双向，在之前的单链表中，我们得知了，节点和节点之前只有一个指针来进行维系，但是在双向链表中，节点内部不止拥有指向下一个节点的指针，还拥有了指向上一个节点的指针，这就是双向链表。

链表——单链表的简单介绍-CSDN博客https://blog.csdn.net/2301_76445610/article/details/133811446?spm=1001.2014.3001.5501

---

图例： 

如图所示：

一个节点被分为了三个部分，分别是前驱指针 prev  、后继指针 next  、存储在节点中的有效数据data

图中的前驱指针 指向前方的节点，后继指针指向后方的节点。

图中，head表示的是“哨兵位” ，哨兵位的前驱指针指向链表的最后一个节点，哨兵位的后继指针指向链表的第一个有效数据节点（后称有效节点），哨兵位自身存储的数据是无效的。

---

带头的双向循环链表的创建：

对于带头的双向循环链表的创建，其实和单链表的创建并无太大的区别。

基本的步骤一致：1、创建节点结构体 2、开辟节点需要的空间 3、对节点内的指针进行指向的调试、4、使用多个节点构成链表 

不同之处：

1. 由于是带头的链表，所以第一个构建的节点其实是哨兵位。
2. 由于是循环的，所以第一个节点的前驱指针和后继指针的指向都是它自己。

头文件部分：

• prev 前驱指针，指向前一个节点
• next 后继指针，指向后一个节点

主函数部分：

最终调试效果：

---

 使用一级指针传参的原因：

在之前的介绍中，我们在进行单链表的操作中，多数使用的是传二级指针，而在这里，在带头的双向链表中，我们使用的是传递一级指针。

• 在之前的单链表中，我们传递的二级指针是头指针，也就是将头节点的指针进行传递。
• 并且在单链表中，我们的某一些操作，比如头插、头删、尾插的某一种情况等，都需要将头指针进行修改。
• 例如头插是需要将头指针中的地址进行更新，头删需要将头指针的地址更改成第二个节点。
• 所以我们需要从内存空间进行修改，把头指针内的地址修改。

而在这里，因为带头的原因，哨兵位是不允许改变的，且我们的头插操作和外插操作，以及其他操作，都是可以通过双向链表的前驱指针和后继指针配合哨兵位进行相关操作。

---

开辟空间函数：

 面对头插、尾插等操作，我们需要先进行一个开辟空间，以此来获取新的节点。

 

---

尾插操作： 

尾插的本质是在链表的尾部插入一个节点。

• 在单链表中，我们先遍历到最后一个节点位置，然后将原先的最后一个节点的指向进行改变，内部的指针指向新开辟的节点，最后新开辟的节点内部指针指向NULL

但是在带头的双向链表中，我们要进行的操作有一些繁杂。

新开辟的节点不仅仅要被原先的最后一个节点指向，还要指向最后一个节点，作为自己的前驱，并且，还要指向哨兵位，达成后继的同时完成循环。

而哨兵位，也因为循环的关系，它的前驱指针要指向这一个新开辟的节点。

而原先的最后一个节点，它的操作和单链表一样，指向新开辟的节点。 

头文件部分：

• phead 表示 头节点，x 表示插入节点的数据 

源文件部分：

• node - > prev  表示新节点的前驱指针，指向原先的最后一个节点
• phead - >prev  表示哨兵位的前驱指针，表示原先的最后一个节点
• node - >next    表示新节点的后继指针，指向哨兵位
• phead - >prev ->next  表示 原先最后一个节点的 后继指针，该指针指向的是哨兵位

主函数部分：

---

打印函数： 

 和单链表的打印函数不同，带头的双向循环链表的打印函数有一个非常特殊的东西——哨兵位。

在之前我们提过，哨兵位内部存储的是一个无效数据，因此在打印的过程中，我们是不能够打印哨兵位的，所以我们应该从第一个有效节点进行打印。

且，因为循环的缘故，当我们在使用while 进行循环打印的同时，最终会回到哨兵位，但是哨兵位不能打印，于是不能打印哨兵位就成为了我们的循环打印停下的判断条件。

源文件部分： 

主函数部分：

打印效果：

---

 头插：

带头链表的头插和单链表的头插有明显的不同。

• 在单链表中，头插是直接插在原先第一个节点之前，而带头链表，由于哨兵位是不能进行修改的，所以头插是指，在第一个有效节点之前进行插入。

如图所示，新节的前驱指针指向了哨兵位，后继指针指向了原先第一个有效节点。

哨兵位的后继指针指向了新节点，第一个有效节点的前驱指针指向了新节点。

源文件部分：

• node - > prev  表示新节点的前驱指针，指向哨兵位
• phead - >next  表示哨兵位的后继指针，表示原先的第一个有效节点
• node - >next    表示新节点的后继指针，指向原先第一个有效节点
• phead ->next -> prev  表示原先第一个有效节点的前驱指针，现在指向新节点

头文件部分：

主函数部分：

---

 尾删：

• 关于尾删，如若是单链表，只需要将倒数第二个节点内部的指针指向进行修改，在把最后一个节点进行free释放即可。

而对于带头的双向循环链表，我们进行一下操作：

1. 把哨兵位的前驱指针指向进行修改，指向倒数第二个节点。
2. 倒数第二个节点的后继指针指向进行修改，指向哨兵位。 
3. 原先的最后一个节点，使用临时变量进行保存，随后删除释放。

注意事项：尾删的时候链表要存在，且不能只有哨兵位。 

源文件：

• del 是哨兵位的前一个节点，也就是尾节点。
• del->prev是尾节点的前一个节点
• del->prev  -> net 是倒数第二个节点的后继指针要指向哨兵位
• 而del ->prev 这个倒数第二个节点 要被哨兵位的前驱指针指向 

头文件：

主函数部分：

---

 头删：

基于之前讲诉过的头插，头删在带头链表中，就是删除第一个有效节点。

1. 如图所示，将哨兵位的后继指针指向第二个有效节点。
2. 第二个有效节点的前驱指针指向哨兵位。
3. 然后把原先的第一个有效节点用临时变量存储，然后进行释放删除。 

注意事项：尾删的时候链表要存在，且不能只有哨兵位。 

源文件部分：

• del 表示第一个有效节点
• del - >next 表示第一个有效节点的后继指针，代表第二个有效节点
• phead->next 表示哨兵位的后继指针，原先指向第一个有效节点，现在指向第二个有效节点
• del -> next ->prev 代表第二个有效节点的前驱指针，现在指向哨兵位 

头文件部分： 

主函数部分：

---

查找位置函数：

• 在指定位置之后插入数据和删除指定位置之后的操作中需要用到的指定位置就有查找位置函数进行查找。
• 查找函数是以节点所存储的数据来进行查找，以及进行判断该位置是否在链表中存在。
• 如若存在则将查找到的位置返回到之后的操作中。

源文件部分：

主函数部分：

---

 在指定位置之后插入数据：

指定位置之后插入数据分为两种情况：

情况1：

情况2：

情况1的插入方式和方法和头插有些类似，只不过将哨兵位变成了指定位置节点，而情况2则是和尾插操作有些类似。

源文件：

以下代码是有先后顺序的！

• node是需要插入的新节点，在指定位置pos之后插入
• pos是指定位置
• node->next 新节点的后继指针，接收原先pos指定位置的后继指针的指向
• pos->next  指定位置的后继指针，指向原先后继指针的后面一个节点
•  node->prev  新节点的前驱指针，指向的指定位置pos的节点
• node->next ->prev  在之前的操作下，node->next代表的是原先指定位置pos的后面一个指针，现在->prev 表示原先指定位置pos后面的一个指针的前驱指针。

主函数部分：

• 需要用到查找位置函数的返回值。

---

删除指定位置的节点：

删除指定位置的节点，需要对指定位置前的指针和指定位置后的指针进行修改。 

1. 将指定位置pos前的节点的后继指针指向指定位置pos后面一个节点。
2. 指定位置pos后的节点的前驱指针指向指定位置pos前面的一个节点。 
3.  然后用临时变量存储指定位置pos，然后进行pos的释放和删除。

 源文件部分：

• pos - >next 指定位置pos的后继指针，代表指定位置pos的后面一个节点
• pos ->prev 指定位置pos的前驱指针，代表指定位置pos的前面一个节点
• pos ->next ->prev  代表指定位置pos的后面一个节点  的  前驱指针，现在指向pos前面一个节点
• pos ->prev - >next   代表指定位置pos的前面一个节点 的 后继指针，现在指向pos后面一个节点

主函数部分：

---

 销毁链表：

销毁链表的本质：

销毁链表的本质其实就是轮流删除有效节点，这里需要使用循环，并且要注意，每次循环只能释放一个节点，而释放节点之前要把释放的那个节点的后面那个节点和前面那个节点的指向发生改变。

最重要的是：要把哨兵位进行删除！

同时销毁链表也分为两种传参形式：

传一级指针：

源文件部分：

主要步骤：把需要销毁的节点的下一个节点放到临时变量中，然后释放销毁的节点，然后再把存放下一个节点的临时变量重新交给cur

• cur表示为需要销毁的节点，同时在销毁前表示第一个有效节点！
•  cur->next表示为第一个有效节点的后继指针，表示第二个有效节点，表示需要销毁的节点的后一个节点
• next是一个临时变量，存储需要销毁的节点的后一个节点。

主函数部分：

头文件：

注意事项：传一级指针需要手动将链表变为NULL 

传二级指针：

源文件部分：

• 内部操作和一级指针一样！

头文件部分：

 主函数部分：

传一级指针和二级指针的区别：

建议：使用一级指针，这是为了代码的规范性。

---

顺序表和双向链表的区别：

---