1.概念以及结构
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
2.双向链表结点结构体
双向链表每个结点除了存储数据data外，还有两个指针记录上一个结点和下一个结点的地址，分别是前驱指针prev和后继指针next，所以双向链表结点定义如下：
typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode;
3.接口实现
我们主要进行以下操作：
//动态申请一个结点 LTNode* BuyListNode(LTDataType x); //初始化链表 LTNode* LTInit(); //打印链表 void LTPrint(LTNode* phead); // 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x); // 双向链表尾删 void LTPopBack(LTNode* phead); // 双向链表头插 void LTPushFront(LTNode* phead, LTDataType x); // 双向链表头删 void LTPopFront(LTNode* phead); // 双向链表查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的结点 void LTErase(LTNode* pos);
3.1动态申请一个结点
LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
思路：
这一步跟之前单链表的操作类似，大家可以看之前的讲解！
3.2初始化链表
LTNode* LTInit() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }
思路：
我们进行初始化之前需要清楚我们结构的状态，我们这里写的是带头结点的双向循环链表，开始时我们先定义一个phead指针，它的next指向自己，prev也是指向自己，头结点和尾结点指向NULL空的话就不能满足我们循环的需求。
3.3打印链表
void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
思路：
原理同单链表的操作基本一致！
3.4双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
思路：
分为两种情况：
链表为空，那插入的结点既是尾结点，也是头结点；
链表不为空，将新结点和链表通过前驱指针prev和后继指针next连接起来，并将尾结点改为新插入的结点，让新节点与最后一个节点进行双层逻辑关系；
3.5 双向链表尾删
void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); // 判空 LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev;//作为新的尾结点 tailPrev->next = phead; phead->prev = tailPrev; free(tail); }
思路：
链表为空，不操作，先断言：
链表结点大于1，保存尾结点，新尾结点等于原尾结点的上一个结点，然后释放保存的尾结点的内存；
3.6双向链表头插
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
思路：
跟尾插一样：
链表为空，那插入的结点既是头结点，也是尾结点；
链表不为空，将新结点和链表通过前驱指针prev和后继指针next连接起来，并将头结点改为新插入的结点，一定要注意链接顺序；
3.7双向链表头删
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); // 判空 LTNode* first = phead->next; LTNode* second = first->next; free(first); phead->next = second; second->prev = phead; }
思路：
思路跟之前的尾删大差不差，具体对照下图，第二张图就是判断删空的情况：
3.8双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
这跟我们单链表的情况也基本一样，大家可以对照学习！
3.9双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); // prev newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode;
思路：
还是分为两种情况考虑：
当插入的位置为第一个位置时，这时就相当于我们的头插操作：
第二种就是正常的插入的操作，具体结合下图：
3.10双向链表删除pos位置的结点
void LTErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; free(pos); prev->next = next; next->prev = prev; }
思路：
这需要注意的就是删除之后的链接关系！
结合图进行理解，我相信大家都能明白。
总结：
以上就是关于带头循环双向链表的基本实现过程！大家之前学过单链表理解起来就很轻松。
