带头双向循环链表的基本操作
- 结构体定义
- 初始化
- 创建新节点
- 头插
- 头删
- 尾插
- 尾删
- 查找
- 在指定位置之后插入
- 删除指定位置的值
- 打印
结构体定义
typedef int DataType;
typedef struct LinkNode
{
DataType data;
struct LinkNode* prev;
struct LinkNode* next;
}LNode;
初始化
有两种初始化方式
第一种你需要在main函数里或者全局定义一个LNode* phead，注意，只需要定义就可以了，然后再调用Init（&phead）；
为什么要传地址呢？
因为在Init函数内部我们需要对phead进行操作（分配空间），那么一旦需要对参数进行操作，那就不能只穿本身，而要传地址。
void Init(LNode** pphead)
{
*pphead=(LNode*)malloc(sizeof(LNode));
(*pphead)->data=-1;
(*pphead)->next=(*pphead)->prev=*pphead;
}
这一种的话，不需要在main函数里创建，直接调用Init_1（）函数就行。
void Init_1()
{
LNode* phead=(LNode*)malloc(sizeof(LNode));
phead->data=-1;
phead->prev=phead->next=phead;
}
初始化以后，头结点就是这样子了：
创建新节点
函数参数为DataType类型
LNode* CreateNode(DataType x)
{
LNode* newnode=(LNode*)malloc(sizeof(LNode));
newnode->prev=newnode->next=NULL;//这个地方也将prev和next初始化为newnode自身
//因为这两个指针后续都会改变方向，因此初始状态无所谓。
return newnode;
}
头插
这里的头插指的是在第一个有效节点之前插入，也就是插入到head的后一个。
我们第一步先把新节点的prev和next设置好，因为这样做不影响链表结构，肯定先把简单的搞了嘛~
然后再修改head->next和head->next->prev（图中1号节点）的指向，至于这两个谁先谁后，那就无所谓了。
头插完以后就是这个样子了
void PushHead(LNode* phead,DataType x)
{
LNode* new=CreateNode(x);
new->next=phead->next;
new->prev=phead;
phead->next->prev=new;
phead->next=new;
}
头删
头删需要注意的一个点就是判断是否只剩下了一个节点，有些题目会要求头删直至为NULL，有的会要求删到只剩最后一个，我们这里以后者为例
先这么改
再这么改（这两步顺序可以变）
最后再释放掉new节点就可以了（当然考试的时候不释放也行，平时养成这个习惯还是很好的！）
void DelHead(LNode* phead)
{
if(phead->next==phead)
return;
else
{
LNode* tmp=phead->next;
phead->next=tmp->next;
tmp->next->prev=phead;
free(tmp);
}
}
尾插
尾插其实就是在头结点的前一个插，所以简单程度可想而知：
void PushBack(LNode*phead,DataType x)
{
LNode*new=CreateNode(x);
new->next=phead;
new->prev=phead->prev;
phead->prev->next=new;
phead->prev=new;
}
尾删
跟刚才尾插一个道理，就是头结点的前一个。
void DelBack(LNode*phead)
{
LNode* tmp=phead->prev;
phead->prev=tmp->prev;
tmp->prev->next=phead;
free(tmp);
}
查找
查找的时候，有时候对查找的开始位置可能也有限制。如果是带头的双循环链表比较好办，如果是不带头的，如果要从phead开始查找，那么开始访问位置cur就得是phead->prev;
我们这里介绍从phead的next开始访问的情况，其他情况趋同，只需要改变初始访问指针cur的值就可以
LNode* Find(LNode* phead,DataType x)
{
LNode* cur=phead->next;
while(cur!=phead)
{
if(cur->data==x)
return cur;
cur=cur->next;
}
return NULL;
}
在指定位置之后插入
跟头插简直一模一样，就是把参数换了个名儿
void Insert(LNode* pos,DataType x)
{
LNode* new=CreateNode(x);
new->next=pos;
new->prev=pos->prev;
pos->prev->next=new;
pos->prev=new;
}
删除指定位置的值
跟刚才头删尾删一样，有些题可能需要删到最后一个为止
void DelPos(LNode* pos)
{
if(pos->next=pos)
return;
else
{
LNode* front=pos->prev;
LNode* after=pos->next;
front->next=after;
after->prev=front;
}
}
打印
这个地方比较巧妙，如果想让phead的值第一个被打印，那么循环就要用do while 因为如果用了while（cur！=phead），那么循环完全进不去，因为访问指针cur的初始值就为phead，用do while可以先执行一次，执行完之后cur的指向就不再是phead了，然后再判断循环条件。
void Print(LNode* phead)
{
LNode* cur=phead;
do
{
printf("%d ",cur->data);
cur=cur->next;
} while (cur!=phead);
}
有两道非常好的双向循环链表的题推荐给大家：
link
这是我写的我们学校作业的题解，
空闲空间申请模拟和 ***文件加密!***这两道题都用到了循环链表，但是比刚刚的基础操作要复杂很多，但是基本的思想都是大差不差的，我在本文中提到的一些注意事项，在这两道题中都有体现，比如说开始访问位置，判断是否为空等等，大家如果想要提高一下可以去看看那两道题哈~
