前言：
往期给大家介绍了单链表， 单链表在 OJ 中出现频率较高，但实际使用的不多；而双链表是存储数据常用的表，它的全名是 带头双向循环链表 ，虽然结构复杂，但不一定复杂，甚至会比单链表容易实现。
Part1: 双向链表结构
所谓双向循环链表，就是相比单链表来说，一个节点中多了一个 结构体指针 ， 指向前一个结点 罢了。
我是图示
Part2: 相关功能实现
1.开工准备
1.1创建新结点
一个结点包含 要储存的元素 ， 前一个结点的指针 和 下一个结点的指针 。
代码实现：
// 创建新结点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
1.2创建头节点
一个重要的问题是头结点中的两个指针指向哪里，指向空吗？
其实不是，这样就没有双向链表的特点了，
为了能准确体现双向链表的特点，要 先把头节点的两个指针都指向自己 ，这样就形成了闭环。
代码实现：
//创建头节点 ListNode* LTInit() { ListNode* pHead = BuyListNode(-1); pHead->next = pHead; pHead->prev = pHead; return pHead; }
2.相关功能实现
2.1链表打印
与单链表打印逻辑相近
代码实现：
// 双向链表打印 void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; printf("<=>pHead<=>"); while (cur != pHead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
2.2尾部插入
与单链表相比，双向链表尾插不需要查找尾部，直接将头节点的前一个记录为尾即可。
剩下的就是修改四个指针。
代码实现：
// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* tail = pHead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = pHead; pHead->prev = newnode; //ListInsert(pHead, x); }
2.3尾部删除
先记录，再修改指针，最后释放置空。
代码实现：
// 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); ListNode* tail = pHead->prev; ListNode* tailprev = tail->prev; pHead->prev = tailprev; tailprev->next = pHead; free(tail); tail = NULL; }
2.4头部插入
代码实现：
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* first = pHead->next; ListNode* newnode = BuyListNode(x); pHead->next = newnode; newnode->prev = pHead; newnode->next = first; first->prev = newnode; }
2.5头部删除
代码实现：
// 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); ListNode* first = pHead->next; ListNode* firstnext = first->next; pHead->next = firstnext; firstnext->prev = pHead; free(first); first = NULL; }
2.6查找位置
这个也与单链表的位置查找相近
代码实现：
// 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead; while (cur && cur->data != x) { cur = cur->next; } return cur; }
2.7在pos前插入
代码实现：
// 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyListNode(x); ListNode* posprev = pos->prev; posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; }
2.8删除pos位置的结点
代码实现：
// 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* posprev = pos->prev; ListNode* posnext = pos->next; posprev->next = posnext; posnext = posprev; free(pos); pos = NULL; }
2.9销毁链表
代码实现：
// 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* posprev = pos->prev; ListNode* posnext = pos->next; posprev->next = posnext; posnext = posprev; free(pos); pos = NULL; }
总结：
在学习完单链表后再进行双链表的实现可谓是水到渠成，所以有些地方就没做详细解释，这也告诉我们复杂的东西不一定难实现。
