链表-双向循环链表【C语言】
双向循环链表是最好的选择, 它弥补了单链表无法解决的问题, 是一种结构较为复杂但操作简便的数据结构. 其插入与删除操作的时间复杂度均为O(1).
双向链表：
与单链表相比，双向链表包含两个指针：一个是连接到下一个节点的指针，另一个是连接到前一个节点的指针。
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
PS：在建立此链表时，请确保使用哨兵位以简化操作流程；其pre域指向尾节点；而tail node的next域指向sentinel node。
打印链表：
因为链表末尾节点未被置空处理，则无法准确确定该节点是否为链表末尾。然而，在这种情况下由于哨兵位置处无数据存储，则可以通过检查当前处理的节点是否属于哨兵位置来终止循环过程。
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next; //这里传入哨兵位的下一个
while (cur!=pHead) {
printf("%d -> ",cur->_data);
cur = cur->_next;
}
printf("head\n");
}数据插入：
由于它采用了哨兵位技术，在插入操作中仅需确认其后继节点即为头节点即可无需修改头节点，并因此无需维护二级指针。
ListNode* ListCreate()
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (!newNode)
{
perror("申请失败\n");
return NULL;
}
newNode->_next = newNode;
newNode->_prev = newNode;
return newNode;
}PS：只有一个节点的时候，要自己指向自己，这样会方便后面的操作。
插入节点：
架设已经有一段链表，要在P节点前面插入一个新节点newNode。
这里双向链表的优势得以体现，在插入到节点前面时无需遍历链表（p->_pre）直接连接。
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->_data = x;
ListNode* cur = pos;
ListNode* pre = pos->_prev;
pre->_next = newNode;
newNode->_prev = pre;
newNode->_next = pos;
pos->_prev = newNode;
}PS：在操作过程中可以直接将上一个节点保存下来，这就不必担心连接时的顺序了。如果不进行保存操作，则需要特别注意连接的顺序。
当链表为空仅有一个哨兵节点时
由于该哨兵节点指向自身
在连接操作中自然也能应用此函数
这个哨兵位的其后驱与前驱都指向newNode；同时,newNode的其后驱与前驱都同样地指向哨兵位
头部插入节点：
在前面部分实现了链表的插入功能，在其原因在于，在头部进行链表插入时可以直接利用已有的函数。这里的链表头结点位于哨兵位之后的一个位置，在这种情况下将该节点传递进来等同于在其头部进行插入操作。
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListInsert(pHead->_next,x);
}
尾部插入节点：
链表的尾结点位于哨兵节点之前，在哨兵节点之前插入新节点等价于在尾部进行插入操作无需额外处理即可调用插入函数
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListInsert(pHead,x);
}
判断链表是否为空：
因为哨兵节点没有存储数据, 那么如果哨兵节点的后继节点就是它自己, 就表示该链表为空。
bool ListEmtpy(ListNode* head)
{
//如果下一个节点是自己那么其就是空链表。
assert(head);
return head->_next==head;
}删除节点：
将要删除的前驱节点与后继节点进行链接操作，并断开它们之间的关系
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* pre = pos->_prev;
ListNode* next = pos->_next;
pre->_next = next;
next->_prev = pre;
free(pos);
}头部删除：
和前面类似的操作一样，在处理哨兵位置之后可以直接调用删除节点的函数
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!ListEmtpy(pHead));
ListErase(pHead->_next);
}PS：注意要判断一下链表是不是为NULL。
尾部删除：
还是跟尾插一样，删除哨兵位前面的节点就是链表的尾部删除。
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!ListEmtpy(pHead));//如果链表为NULL,返回
ListErase(pHead->_prev);
}
查找节点位置：
如同处理链表打印时的做法，在遍历链表的过程中难以确定尾节点的位置。因此需要检查是否已经到达了哨兵位置。如果到达了哨兵位置则表示未找到数据，并结束循环并返回NULL值。
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur!=pHead) {
if (cur->_data==x) {
return cur;
}
cur = cur->_next;
}
return NULL;
}删除链表：
清除链表同样可以复用删除节点函数，并非只是将该链表中的所有节点全部删掉
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur!=pHead) {
ListNode* temp = cur;
cur = cur->_next;
free(temp);
}
free(pHead);
}拓展：
顺序表优点： 下标随机访问、cup高速缓冲命中率高（物理空间连续）
顺序表缺点 ：其在进行头部插入或中间插入操作时的数据效率不高；当进行扩容操作时会消耗较多的性能资源；此外还存在空间浪费的问题
链表优点 ：任意位置插入和删除为O(1)，按需释放。
链表缺点 ：不支持随机访问。
cup高速缓冲命中率高：内存存储了这些数据；当CPU与内存进行数据交换时，在其中包含一个高速缓存区域中能够一次性加载一段连续的数据块；顺序表由于其物理存储区域是连续的，在从起始地址开始访问时，默认会加载后续的一段数据；这种加载方式减少了遍历所需的时间；相比之下，在链表结构中其访问路径较为分散且不连续。