本文总结讲解【双向带头循环链表】如何实现，以及各种功能的具体步骤详细过程。

• Ⅰ表的分类
• • 1.1单向或者双向
  • 1.2带头或者不带头
  • 1.3循环或者非循环
• Ⅱ.双向循环链表
• • 2.1生成一个新结点
  • 2.2初始化链表
  • 2.3链表尾插
  • 2.4链表尾删
  • 2.5链表的打印
  • 2.6链表的头插
  • 2.7链表的头删
  • 2.8链表的插入
  • 2.9链表的删除
  • 2.10链表的销毁

Ⅰ表的分类

链表在实际种的结构非常多样，以下结构组合起来就有8种链表结构

1.1单向或者双向

1.2带头或者不带头

1.3循环或者非循环

Ⅱ.双向循环链表

虽然有这么多链表的结构，但是我们实际中最常用的还是两种结构：

1.无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际种更多的是作为其他数据结构的子结构，如哈希桶，图的邻解=接表等等。另外这种结构在笔试面试中出现很多
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是栓不高兴循环链表。虽然这个结构复杂，但是实现后就会发现结构会带来很多优势，实现反而简单了。
接下来就让我一一解析带头双向循环链表是如何实现的

#pragma once
#include 
#include 
#include 
#include 
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指向tailnewnode->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;elsereturn false;
}
void SLTpopBack(SLTNode* phead)//尾删
{assert(phead);//断言判断phead不为NULLassert(!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);//断言判断是否为NULLassert(!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  posPrevpos->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);//释放pospos = 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;}