本文总结讲解【双向带头循环链表】如何实现，以及各种功能的具体步骤详细过程。
Ⅰ表的分类
链表在实际种的结构非常多样，以下结构组合起来就有8种链表结构
1.1单向或者双向
1.2带头或者不带头
1.3循环或者非循环
Ⅱ.双向循环链表
虽然有这么多链表的结构，但是我们实际中最常用的还是两种结构：
1.无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际种更多的是作为其他数据结构的子结构，如哈希桶，图的邻解=接表等等。另外这种结构在笔试面试中出现很多
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是栓不高兴循环链表。虽然这个结构复杂，但是实现后就会发现结构会带来很多优势，实现反而简单了。
接下来就让我一一解析带头双向循环链表是如何实现的
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int SLData;//因为不知道要传入的数据是何类型，先定义为int类型，后面有需要再改。 typedef struct SLTNode//创建一个双向链表结构体 { struct SLTNode* next;//指向下一个结点的地址 struct SLTNode* prev;//指向前一个结点的地址 SLData data;//结点中的数据 }SLTNode; //初始化循环链表 SLTNode* SLTinit(); //生成一个新结点 SLTNode* BuyNode(SLData x); //循环链表尾插 void SLTpushBack(SLTNode*phead,SLData x); //循环链表打印 void SLTPrint(SLTNode* phead); //判断是否为空--还剩下一个哨兵头 bool SLTEmpty(SLTNode* phead); //循环链表尾删 void SLTpopBack(SLTNode* phead); //循环链表头插 void SLTpushFront(SLTNode* phead,SLData x); //循环链表头删 void SLTpopFront(SLTNode* phead); //在pos位置前面插入一个结点 void SLTInsert(SLTNode* pos, SLData x); //在pos位置删除一个结点 void SLTErase(SLTNode* pos); //销毁循环链表 void SLTDestroy(SLTNode* phead);
2.1生成一个新结点
我们需要带头的链表的话，就需要动态申请一个结点，而且后面插入结点的操作都是需要生成一个新结点，所以我们将这个步骤整合成一个函数———BuyNode()
//动态申请一个结点 SLTNode* BuyNode(SLData x)//生成一个结点 { SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); if (node == NULL)//如果申请失败 { perror("malloc"); } node->data = x; node->next = NULL;//一开始需要将next和prev都置NULL防止野指针 node->prev = NULL; return node;//将生成的新结点地址返回 }
2.2初始化链表
带头双向循环链表该如何初始化呢？
因为一开始什么都没有只有一个头结点phead
那是不是将phead两端的指针指向NULL呢？
虽然这样符合了双向，但我们要的是双向循环链表
循环链表是怎么实现的呢？
1.头结点的prev指向尾结点
2.尾结点的next指向头结点
为了配合循环，我们应该将头结点的两个指针都指向自己，
也就是
phead->next=phead; phead->prev=phead;
这样更符合循环链表的定义
还有一个注意地方就是我们这个初始化函数应该用二级指针来接收，因为最终是要改变实参数据的，所以我们需要传二级指针，不过我们也可以不使用二级指针，而使用函数返回带回数据，这样就不用使用二级指针了。
SLTNode* SLTinit()//初始化，生成一个带有头哨兵的链表 { SLTNode* phead = BuyNode(-1);//头哨兵 phead->next = phead;//循环--指向自己 phead->prev = phead; return phead;//初始化，返回这个带有头哨兵的链表； }
2.3链表尾插
先生成一个结点。
不同于无头单向单链表，不能往前找，带头双向循环链表可以往前找结点，所以我们要尾插的化，就需要找到尾结点，头结点的前面就是尾结点了，直接就找到了。
然后尾插需要做的就是改变四个指针即可：
1.tail的next指向新结点
2.新结点的prev指向tail
3.新结点的next指向头节点
4.头结点的prev指向新结点
这种同样也适用于只有一个头结点的时候。
void SLTpushBack(SLTNode* phead,SLData x)//尾插 { assert(phead);//phead不可能为NULL，所以需要声明判断一下，如果为空则传错 SLTNode* newnode = BuyNode(x);//生成一个新结点 SLTNode* tail = phead->prev;//找尾 //改变4个指针 tail->next = newnode;//tail的next指向新结点 newnode->prev = tail;//新结点的prev指向tail newnode->next = phead;//新结点的next指向头节点 phead->prev = newnode;//头结点的prev指向新结点 }
2.4链表尾删
链表尾删不仅需要找尾tail，还要记录尾结点前面的结点地址Prevtail，因为删除尾结点后，还要链接尾结点之前的结点，因为双向所以可以往前找到前一个结点的地址，这就很方便。
删除尾结点后就需要将头结点与尾结点的循环关系调整下了，
将循环关系调整到尾结点的前一个结点去。
//用来判断是否链表只有头结点了，如果是那就返回true如果不是那就返回false bool SLTEmpty(SLTNode* phead) { assert(phead); if (phead->next == phead) return true; else return false; } void SLTpopBack(SLTNode* phead)//尾删 { assert(phead);//断言判断phead不为NULL assert(!SLTEmpty(phead));//判断是否删除过头，当只剩下头结点时，就报错 SLTNode* tail = phead->prev;//找尾 SLTNode* Prevtail = tail->prev;//记录尾结点前面的结点 Prevtail->next = phead;//改变循环关系 phead->prev = Prevtail; free(tail);//删除尾结点 tail = NULL;//记得置NULL }
2.5链表的打印
该链表为循环链表，一旦遍历怎么停下来呢？
我们需要打印的是头结点以后的数据，所以我们要将第一个结点记录下来，让它往后走，直到走回来到了头结点时，就停下来。
void SLTPrint(SLTNode* phead) { assert(phead); SLTNode* cur = phead->next;//记录第一个结点地址 while (cur!=phead) { printf("%d<=>", cur->data); cur = cur->next; } }
2.6链表的头插
首先生成一个新结点
头插就是在头结点和第一个结点直接插入新结点，想一想需要改变四个指针，不过这改变的指针也是有讲究的，如果直接从头结点开始改起，我们需要先该后面的指针，然后再该前面的指针，如果先改变前面的指针，那么第一个结点的地址就很难再找到了。
所以
1.我们先让新结点的next指向第一个结点
2.第一个结点的prev指向新结点
3.头结点的next指向新结点
4.新结点的prev指向头结点
void SLTpushFront(SLTNode* phead, SLData x)//头插 { assert(phead); SLTNode* newnode = BuyNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
不过如果要是把第一个结点的地址记录下来，那么就不要用注意顺序问题了，随便更改即可
void SLTpushFront(SLTNode* phead, SLData x)//头插 { SLTNode* fisrt = phead->next;//将第一个结点记录下来 phead->next = newnode;//不需要注意顺序 newnode->prev = phead; newnode->next = fisrt; fisrt->prev = newnode; }
2.7链表的头删
链表的头删即将第一个结点删除，那我们就需要记录第二结点的地址了，因为删除第一个结点后我们需要将头结点与第二个结点链接起来，链接过程很简单，就是让第二个结点的prev指向头结点，头结点的next指向第二个结点
void SLTpopFront(SLTNode* phead)//头删 { assert(phead);//断言判断是否为NULL assert(!SLTEmpty(phead));//判断是否删除过头，是否只剩下头结点 SLTNode* cur = phead->next;//记录第一个结点 SLTNode* Nextcur = cur->next;//记录第二个结点 phead->next = Nextcur;//头结点的next指向第二个结点 Nextcur->prev = phead;//第二个结点的prev指向头结点 free(cur);//删除头结点 cur = NULL;//记得置NULL }
2.8链表的插入
在链表任意pos位置前面插入一个结点，对于双向链表而言简简单单，轻轻松松。
因为pos的prev就记录着前面的结点位置，要在pos前面插入，改变四个指针即可
1.将新结点的next指向pos
2.pos的rev指向新结点
3.pos前面的结点的next指向新结点
4.新结点的prev指向pos前面的结点
void SLTInsert(SLTNode* pos, SLData x)//在pos位置前面插入---需要搭配一个find函数哈 { //我们只要记住pos结点前一个结点的地址就很好搞了 //双向pos的prev就是前一个结点的地址 assert(pos); SLTNode* newnode = BuyNode(x); SLTNode* Prevpos = pos->prev; //Prev newnode pos Prevpos->next = newnode; newnode->prev = Prevpos; newnode->next = pos; pos->prev = newnode; //我们可以发现在insert这个函数是在pos位置前面插入，我们可以复用它来代替头插和尾插了 //头插那就是在第一个结点之前插入，也就是让pos为第一个结点位置也就是phead->next //尾插也就是在phead前面插入即可，那就让pos=phead }
2.9链表的删除
删除pos位置的结点
void SLTErase(SLTNode* pos)//可以代替尾删头删 { SLTNode* Prev = pos->prev;//将pos前面结点记录下来 SLTNode* After = pos->next;//将pos后面结点记录下来 Prev->next = After;//将前后两个结点链接起来 After->prev = Prev; free(pos);//释放pos pos = NULL; }
2.10链表的销毁
链表的销毁要将所有的结点全部释放掉，包括头结点
所以我们就可以像打印一样循环到phead后就结束，最后再销毁phead头结点
要注意要记录每个销毁结点后面结点的地址。
还有要在外面使用如果传一级指针要手动置NULL。
void SLTDestroy(SLTNode* phead) { assert(phead); SLTNode* cur = phead->next; while (cur != phead) { SLTNode* next = cur->next; free(cur); cur = NULL; cur = next; } free(phead); phead = NULL; }
