前言：

继上文，我们了解了结构最简单的一种链表---单链表

那么我们今天就来讲解一下结构最复杂的链表---带头循环双向链表。

当然今天的链表也许看起来结构十分复杂，对比单链表看上去难上很多，但实际上，越是结构复杂，越是操作起来简单。

那么话不多说，马上就开始我们的带头循环双向链表的讲解吧

那么还是先来了解一下各种特点的区别吧~

有无哨兵位头结点的区别：

无哨兵位头结点：

在链表的相关操作时，有可能涉及到操作第一个结点的操作，如果要修改第一个结点的指针，或是在第一个元素前插入一结点，或是删除第一结点。一系列的操作都与其他结点的操作不一致，所以会增加我们写代码的思考量。

有哨兵位头结点：

该结点是不存储任何有效的数据的，链表的系列操作都不会修改我们头结点的指针，也因为这个头结点，让我们第一元素的插入还有删除第一个结点的相关操作都与其他的结点操作保持了一致。

链表单向与双向的区别：

单向链表：

单向链表链表只能单项读取，只能从头遍历到尾，只能在此结点找到下一个结点，但无法从此结点找到上一个结点，但人家还是有一定的优势的，增删结点的操作比较简单，而且遍历的时候不会死循环。

双向链表：

双向链表可以从此结点找到前面的结点，也可以找到后面的结点，可进可退，十分的方便哦，但是人家对比单向的链表还是有一些小缺点的，遍历的时候可能会造成死循环，而且我们在增删结点的时候比单链表复杂，我们需要多分配一个指针存储空间。

那么了解完了我们的各个特点的区别之后，我们就来快乐的实现我们的带头循环双向链表吧~

当然在实现之前，我们先来看一下这种链表的图：

是不是看起来十分的复杂呢？

当你上手的时候你就不会觉得它困难了。

链表的代码实现：

接下来我们会完成以下内容：

创建返回链表的头结点

双向链表销毁

双向链表打印

双向链表尾插

双向链表尾删

双向链表头插

双向链表头删

双向链表查找

双向链表在pos的前面进行插入

双向链表删除pos位置的节点

创建返回链表的头结点：

ListNode* ListCreate()
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));head->next = head;head->prev = head;return head;
}

创建一个带哨兵位的头结点，让我们对第一个元素的操作和其他结点的操作保持一致。

双向链表销毁:

void ListDestroy(ListNode* pHead)
{ListNode* cur = pHead->next;while (cur != pHead){ListNode* next = cur->next;free(cur);cur = next;}free(pHead);
}

遍历整个链表，之后依次释放我们的结点，等最后循环回到我们的头结点时，我们再把头结点释放，从而完成整个链表的销毁释放

双向链表打印：

void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}

还是和销毁同样的思路，遍历我们的链表，等回到头结点的时候停止。

双向链表尾插：

void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode = BuyListNode(x);phead         tail   newnode//ListNode* tail = pHead->prev;//tail->next = newnode;//newnode->prev = tail;//newnode->next = pHead;//pHead->prev = newnode;ListInsert(pHead, x);
}

我们的尾插的思路其实很简单，只需要创建一个新的结点之后，再创建一个指针，通过头结点，找到链表的尾部，之后让尾部的next指向我们的新节点，再让新节点的prev指向我们的尾部，接下来让新结点的next指向我们的头结点，最后再让头结点的prev指向我们的新结点，这样就可以让我们的新结点成为我们链表的尾部，这样就完成了我们的链表尾插的实现。

细心的同学可能发现了，我们的尾插实现是我们的注释部分，剧透一下：尾插和头插都可以归类成一个函数。

双向链表尾删：

void ListPopBack(ListNode* pHead)
{assert(pHead);//ListNode* tail = pHead->prev;//ListNode* tailPrev = tail->prev;pHead     tailPrev tail//tailPrev->next = pHead;//pHead->prev = tailPrev;//free(tail);/*ListNode* tail = pHead->prev;pHead->prev = tail->prev;tail->prev->next = pHead;free(tail);*/ListErase(pHead->prev);
}

尾删和头删的操作也是可以归并为同一个函数哦。

双向链表头插：

void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode = BuyListNode(x);//ListNode* first = pHead->next;//pHead->next = newnode;//newnode->prev = pHead;//newnode->next = first;//first->prev = newnode;/*ListNode* newNode = BuyListNode(x);newNode->next = pHead->next;pHead->next->prev = newNode;pHead->next = newNode;newNode->prev = pHead;*/ListInsert(pHead->next, x);
}

与尾插相同的思路哦

双向链表头删：

void ListPopFront(ListNode* pHead)
{ListErase(pHead->next);
}

双向链表查找：

ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

思路也是遍历整个链表，如果再遇头结点还没有所匹配的，那么我们就返回一个空指针。

双向链表在pos的前面进行插入：

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);// prev newnode posprev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

看看这个思路！！！是不是就可以不需要单独头尾插了？？？

双向链表删除pos位置的节点：

void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);
}

再看看这个思路！！！是不是也可以不需要单独的头尾删了？？？