前言

`带头双向循环链表：
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势

一、双向链表结构的建立：

typedef int LTDateType;//数据的类型typedef struct ListNode {LTDateType date;struct ListNode *prev;//前一个结点的地址struct ListNode* next;//后一个结点的地址
}LTNode;

二、双向链表的基本操作

2.1链表新结点的建立（BuyListNode）

LTNode* BuyListNode(LTDateType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {//判断申请的是否有意义perror("BuyListNode");return NULL;}//对新结点进行初始化newnode->date = x;newnode->prev = NULL;newnode->next = NULL;return newnode;//返回新结点
}

2.2链表的初始化（Init）

LTNode* Init() {LTNode* phead = BuyListNode(-1);//建立哨兵位即头phead->prev = phead;phead->next = phead;
//1.尾的next指向哨兵位的头
//2.哨兵位的头的prev指向尾
//因为刚开始只有一个哨兵所以循环过来就是他自己return phead;
}

2.3链表的打印（LTPrint）

void LTPrint(LTNode* phead) {assert(phead);LTNode* cur = phead->next;//从哨兵位的下一个结点开始打印printf("<-head->");while (cur!=phead) {//哨兵位不打印printf("%d->", cur->date);cur = cur->next;}printf("\\n");
}

2.32链表是否为空的判断（LTEmpty）

bool LTEmpty(LTNode* phead) {assert(phead);//哨兵位地址要有意义不能为空return phead->next == phead;//相等返回true//否则false
}

2.4链表的尾插（LTPushBack）

void LTPushBack(LTNode* phead, LTDateType x) {assert(phead);//方法一：LTNode* newnode = BuyListNode(x);//建立要尾插的结点LTNode* tail = phead->prev;//原先的尾结点tail->next = newnode;newnode->next = phead;newnode->prev = tail;phead->prev = newnode;//哨兵位前一个结点发生改变//方法二：LTInsertBefore(phead, x);（后面会说）//因为为循环结构所以直接在哨兵位的前面插入相当于//尾插
}

2.45链表的头插（LTPushFront）

void LTPushFront(LTNode* phead, LTDateType x) {assert(phead);LTNode* newnode = BuyListNode(x);//创建新结点LTNode* first = phead->next;//先保存第一个结点的地址newnode->next = first;newnode->prev = phead;//对新结点前后指针域进行赋值first->prev = newnode;phead->next = newnode;
}

2.5链表的尾删（LTPopBack）

void LTPopBack(LTNode* phead) {assert(phead);assert(!LTEmpty(phead));//判断是否为空链表、//空链表：除了哨兵位没有别的结点LTNode* tail = phead->prev;//找到要删除的尾结点LTNode* tailPrev = tail->prev;//改变尾结点前面一个结点的指向tailPrev->next = phead;phead->prev = tailPrev;//原先的尾结点删除则哨兵位前面一个结点改变了free(tail);tail = NULL;
}

2.5链表的头删（LTPopFront）

void LTPopFront(LTNode* phead) {//方法一：assert(phead);assert(!LTEmpty(phead));//既然要删除原链表肯定不能为空LTNode* del = phead->next;//要删除元素phead->next = del->next;//哨兵位next指向要删除结点后面一个结点del->next->prev = phead;//要删除节点后面一个结点的prev指向哨兵位free(del);del = NULL;//方法二：//LTErase(phead->next);
}

2.6链表指定元素之前插入新元素（LTInsertBefore）

void LTInsertBefore(LTNode* pos, LTDateType x) {//在pos之前插入assert(pos);LTNode* newnode = BuyListNode(x);LTNode* Prev = pos->prev;//Prev为要插入结点之前一个结点newnode->next = pos;newnode->prev = Prev;Prev->next = newnode;pos->prev = newnode;
}

2.7链表指定元素的删除（LTErase）

void LTErase(LTNode* pos) {assert(pos);LTNode* Prev = pos->prev;
//pos之前一个结点LTNode* Next = pos->next;
//pos之后的一个结点Prev->next = Next;Next->prev = Prev;free(pos);pos = NULL;
}

2.8链表的查找（LTFind）

LTNode* FindNode(LTNode* phead, LTDateType x) {assert(phead);LTNode* cur = phead->next;while (cur!=phead) {//到哨兵位时候结束if (cur->date == x) {return cur;}cur = cur->next;}return NULL;
}

2.9链表的销毁（LTDestroy）

void LTDestroy(LTNode* phead) {assert(phead);LTNode* cur = phead->next;while (cur!=phead) {LTNode* Next = cur->next;//保存要删除结点的下一个结点的地址free(cur);cur = Next;}//这里提醒一下调用完这个函数以后，//phead要置空，想在这个函数里面置空的话//要传二级指针
}