一、有头双向循环链表
（一、）我们先讲一些学习的小知识点和注意点
我们不管它昨天几点睡和今天有没有学习，把握好当下，我们今天要进行双向链表的学习
1.什么是双向链表（最主要讲的就是每个节点不仅是上一个结点存了下一个结点的地址（此时后一个结点也存了上一个结点的地址），这个就是双向链表）
2.所以现在我们还是一样不管那么多，我们先进行一个结构体的创建（但是此时的这个结构体不同于单链表的结构体，此时的结构体是多了一个指针的结构体）
3.单链表的题目考察较多，双链表没什么题目
4.二叉树也是两个指针
5.带头和不带头（就看与没有哨兵位），就是看头指针是否存放数据（头指针单独是一个指针就是哨兵位）
6.循环和非循环（如果是双向链表它的头结点和尾结点都是指向空指针的，但是如果是循环链表则不是）
7.循环链表的最后一个结点指向的位置是头结点
8.所以链表为什么会有8中结构（单、双）（带头、不带头）（循环、非循环）这些的排列组合刚好8种
9.但是在这8种中比较有价值（最常用的）的就是（最简单的和最复杂的）：无头单向非循环链表、带头双向循环链表
10.所以我们就开始带头双向循环链表的学习（比无头单向非循环链表更简单哦）
（二、）有关的图解（便于理解）
（三、）有头双向循环链表的实现
可以分为一下这些接口：
1.初始化
2.打印
3.尾插
4.尾删
5.头插
6.头删
7.查找
8.销毁
9.任意位置插入
10.任意位置删除
//1.初始化 DLNode* ListInit(); //2.打印 void ListPrint(DLNode* phead); //3.尾插 void ListPushBack(DLNode* phead, DSListType x); //4.尾删 void ListPoptBack(DLNode* phead); //5.头插 void ListPushFront(DLNode* phead, DSListType x); //6.头删 void ListPoptFront(DLNode* phead); //7.查找 DLNode* ListFindname(DLNode* phead, DSListType x); //8.销毁 void ListDestory(DLNode* phead); //9.任意位置插入 void ListInsert(DLNode* pos, DSListType x); //10.任意位置删除 void ListDete(DLNode* pos); //11.上面的这两个函数是整个双向循环链表中最重要的
1.初始化接口
//1.初始化 //因为此时我有对这个传过来的指针进行改变（进行了初始化）所以此时的头结点是发生的改变的，所以这边一定要有返回值 DLNode* ListInit() { //因为我们是玩带哨兵位的，所以此时我们应该要先malloc出来一个结点（让这个结点成为我的哨兵位） //哨兵位头结点：（但是我函数外面的plist并拿不到这个哨兵位（也就是plist不会发生改变），所以需要有一个返回值来处理这个问题或者用二级指针也行） DLNode* phead = (DLNode*)malloc(sizeof(DLNode)); //因为此时的结构是一个双向的循环，所以(此时结构体中的两个指针应该要有不同的指向) //一个指针指向自己 phead->next = phead; //另一个指针也指向它自己 phead->prev = phead; return phead; }//以上就是对一个带头循环双向链表的初始化（这个就是C语言的魅力，什么都是靠自己来弄，你只是给了我一个概念的模型，剩下的东西都是要靠我自己来搞定这个结构应该是怎样的）
2.打印接口
//3.打印 // void ListPrint(DLNode* phead) { //因为此时phead中存的并不是一个有效的数据，所以此时不需要从头结点开始遍历（下一个结点开始） //判断结束条件就是通过：此时的这些数据在循环的过程之中最后会等于我的头结点（哨兵位），因为是循环的，所以不要以为它是一个循环就不能打印（只是停止的条件发生了一些的改变而已） assert(phead); DLNode* cur = phead->next; while (cur != phead) { printf("<-%d->", cur->data); cur = cur->next; } }
3.尾插接口
//2.尾插 //因为此时我的头结点plist传过来之后我并没有对其进行改变（因为我在初始化那步就已经改变过了，此时的这个plist就是已经拥有了两个指针（已经把哨兵位给创建好了），所以此时我在尾插时，就不会对plist进行任何形式的改变，所以此时我就不需要有返回值，当然也不需要有二进指针（这个也就是哨兵位的好处）） void ListPushBack(DLNode* phead, DSListType x) { assert(phead); //DLNode* tail = phead->prev;//这步就是循环链表的大好处了（直接就可以找到最后一个结点的位置） //DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));//这个就是开辟新结点（尾插就一定要开辟一个新结点不然插什么） //newnode->data = x; 以上就是一个准备工作，下面就是真正的双向的循环的原理实现（最好是附上一幅图） //tail->next = newnode;//这步的意思是因为此时的tail就是尾结点（就是让我的尾结点的最后一个指针去指向我新开辟出来的结点，这样就实现了尾插） //newnode->prev = tail;//这个就是为了实现双向循环链表（因为双向循环链表有两个指针，此时的一个指针就要指向刚刚那个尾结点（tail），只有这样我的newnode才可以取而代之） //newnode->next = phead;//然后此时的另一个指针就去指向我的头指针（为了实现循环，尾—>头） //phead->prev = newnode;//然后这步就是把刚刚的头的其中一个指针指向我的newnoode（还是为了循环）（头->尾），这样就实现了循环双指针链表 //附用任意插 ListInsert(phead, x); }
4.尾删接口
//4.尾删（我的正确写法） void ListPoptBack(DLNode* phead) { assert(phead); assert(phead->next != phead);//这边就是说明我不可以把哨兵位给删掉（就是当phead->next=phead;时，此时就是代表我这个循环双链表就只剩下哨兵位自己了（因为这是一个循环的链表），此时就不能再进行删除了） 首先肯定是不需要开辟新结点的 //DLNode* tail = phead->prev; while (cur->next != tail)//找尾的上一个 { cur = cur->next; } 不敢把这个单链表的理解带过来我们的双链表（因为此时的整体的结构就是不一样的，因为此时的双链表是有两个指针的，一个是next指针，一个是prev指针，所以此时的尾的前一个只需要用prev这个指针去找就可以了） //DLNode* prev = tail->prev; //free(tail); //prev->next = NULL; 此时以上只是大致的把尾给删除了，但是我还没有重新将这个循环链表给链接起来 //prev->next = phead; //phead->prev = prev; //附用任意删 ListDete(phead->prev); }
5.头插接口
//5.头插 void ListPushFront(DLNode* phead, DSListType x) { assert(phead); //DLNode* newnode = (DLNode*)malloc(sizeof(DLNode)); //newnode->data = x; //DLNode* tail = phead->next; //newnode->next = tail; //tail->prev = newnode; //newnode->prev = phead; //phead->next = newnode; //附用任意插 ListInsert(phead->next, x);//这个位置一定要记住是phead->next,不然就会出问题，因为哨兵位的后一个才是头结点，所以在这个头结点前面插入才是我的头插 }
7.查找接口
//7.查找 DLNode* ListFindname(DLNode* phead, DSListType x)//这个是为了找x，不敢当傻子了 { assert(phead); //这个的逻辑就有点像是print的逻辑，就是靠那个循环条件来完成 DLNode* cur = phead->next; while (cur != phead)//这个循环是在保证我这个链表中不止只有哨兵位，而是有数据结点才开始找 { if (cur->data == x) { return cur; } //这个位置就表示找到了 cur = cur->next; } return NULL; }
8.销毁接口
//8.销毁 void ListDestory(DLNode* phead) { DLNode* cur = phead->next; DLNode* next = NULL; //while (cur->next != phead)//这步一开始你是这样写的，但是如果你写成这样的话，就会导致最后一个结点free不了，所以应该写成下面这样 while (cur != phead) { //可以的怎么野指针怎么来（这就是我吗？） next = cur->next; free(cur); cur = NULL; cur = next; } //并且在你把所有的结点释放完之后（不能把哨兵位这个动态开辟的内存空间给忘记掉释放了），所以这边还要加一步 free(phead);//但是这边要注意一个二级指针的问题（因为这步现在再改变我的函数外部的plist哨兵位） phead = NULL; }
9.任意位置插入接口
//9.任意位置插入(pos位置) void ListInsert(DLNode* pos, DSListType x)//这个位置不一定要用pos，用一个int pos的下标也是一样的,但一定注意这个pos是一个DLNode结构体，里面是有两个指针和一个数据的 { assert(pos); DLNode* newnode = (DLNode*)malloc(sizeof(DLNode)); newnode->data = x; DLNode* prev = pos->prev; newnode->prev = prev; prev->next = newnode; newnode->next = pos; pos->prev = newnode; }
10.任意位置删除接口
//10.任意位置删除(pos位置) void ListDete( DLNode* pos) { assert(pos); /*assert(phead->next != phead);*/ DLNode* next = pos->next; DLNode* prev = pos->prev; free(pos); next->prev = prev; prev->next = next; }
附上图解：
（四、）测试代码
void Test1()
中的测试内容：
void Test2()
中的测试内容：
void Test3()
完整的测试代码：
#include"标头.h" void Test1() { //DLNode* plist = NULL;//（此时我的头结点是一个带哨兵位的，） //先初始化 /*ListInit(&plist);*///我们在使用哨兵位的就不用这种传地址的方式 DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式 //再尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); printf("\n"); //再尾删 ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPrint(plist); printf("\n"); //再头插 ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //再头删 ListPoptFront(plist); ListPoptFront(plist); ListPoptFront(plist); //打印 printf("NULL"); ListPrint(plist); printf("NULL\n"); ListDestory(plist); } void Test2() { DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式 //先尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); printf("\n"); //再头插 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //查找 DLNode* pos = ListFindname(plist, 1); printf("\n"); //打印 printf("NULL"); ListPrint(plist); printf("NULL\n"); ListDestory(plist); } void Test3() { DLNode* plist = ListInit(); //先尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); //再头插 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //再尾删 ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPrint(plist); printf("\n"); //再头删 ListPoptFront(plist); ListPoptFront(plist); ListPoptFront(plist); ListPrint(plist); printf("\n"); ListDestory(plist); //可以不使用二级指针，直接自己在外面置空指针(为了保持接口的一致性，所以不使用二级指针) plist = NULL; } int main() { //Test1(); //Test2(); Test3(); return 0; }
