一.双向链表的结构
最常用的链表就是单链表和双向链表。我们首先要知道，链表有八种分类。单链表是不带头单向不循环链表。而此篇博客要讲的是带头双向循环链表。
结构如下：
注意：带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的” 。它存在的意义就是遍历循环链表避免死循环。
我们所说的双向链表为空，跟单链表不同，双向链表就是只存在哨兵位。双向链表的实现就比单链表简单的多了。
二.双向链表的实现
1.申请一个新节点和初始化
//创建一个新节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));//动态申请空间if (node == NULL){perror("node");exit(1);}node->next = node;node->prev = node;//把新节点的next指针和prev指针都指向自己node->data = x;return node;//返回我们的新节点
}
//初始化
void LTInit(LTNode** pphead)
{//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);//初始化时我们需要改变首节点，用二级指针传参
}注意在创建新节点的时候我们一定要把next指针和prev都指向自己。初始化其实就是给我们创建一个哨兵位。
其实初始化不用二级指针也可以做到初始话：
//不用二级指针的初始化
LTNode* LTInit(LTNode* phead)
{phead = LTBuyNode(-1);return phead;
}返回指针就行了。
2.尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//创建一个新节点newnode->prev = phead->prev;newnode->next = phead;//先把newnode的指向指针都给改了phead->prev->next = newnode;phead->prev = newnode;//这一行不能与上一行交换位置
}为了方便查看我们写的代码是否有错误，我们可以打印出来：
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}这个是在后面的测试过程来用的。
3.头插
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//先改变newnode节点指针的指向phead->next->prev = newnode;phead->next = newnode;//同样这两个的位置也不可以调换
}4.尾删
尾删就更简单了：
//尾删
void LTPopBack(LTNode* phead)
{assert(phead&&phead->next!=NULL);//链表必须不能为NULL，且必须有效LTNode* del = phead->prev;//把尾节点存起来del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;//释放后置为NULL，这是习惯
}5.头删
头删的时候一定要注意，我们删的可不是哨兵位，是有效位的头。
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != NULL);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;//这两行代码可以互换，因为我们已经提前把phead->next的值存起来了free(del);del = NULL;
}6.指定位置之后插入
在指定位置插入，我们可以先写一个函数来找到指定位置：
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead)//遍历双向链表{if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}然后执行插入：
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}7.删除指定节点
//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead，但是没有参数phead，无法增加校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}8.销毁链表
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead，而phead还没有被销毁free(phead);phead = NULL;
}三.双向链表功能实现的测试
void text1()
{//初始化LTNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);//打印LTPrint(plist);//头插LTPushFront(plist, 100);LTPushFront(plist, 200);LTPushFront(plist, 300);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找LTNode* find = LTFind(plist, 1);//在指定位置之后插入数据LTInsert(find, 66);LTPrint(plist);//删除指定位置的数据LTErase(find);find = NULL;LTPrint(plist);//销毁链表LTDesTroy(find);plist=NULL;
}
int main()
{text1();return 0;
}
为了保证接口的一致性，即使是LTErase和LTDesTory这些理论上需要传递二级指针的函数，我们也给它传递了一级指针。但是我们一定要注意 LTDesTory和LTErase当我们在函数内部把节点给释放掉之后，在函数的内部我们把释放掉的指针给置为了NULL，但是在出了函数的时候，我们是实参并没有置为NULL，所以我们需要多加一步对实参置为NULL，这样代码才完整。
关于双向链表是比单向链表要简单的多的。感谢大家的观看，如有错误，请多多指出。
