在单链表的基础上，我们再加一个prev指针，让该节点既能找到下一节点，也能找到上一个节点，这样的链表我们称为双向链表
链表可分为带哨兵卫头节点和不带头节点的，单链表或者双向链表，循环或者不循环的，这3种方式可以组成8种链表，其中，最常见的是不带头节点的单向不循环链表和带头节点的双向循环链表
带头节点的双向循环链表，只有给了其中任意一个节点，我们就可以找到其中的其他任意节点
定义
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;我们每次创建双向链表的新节点时，要把该节点的next和prev都指向自己，而不是NULL指针，这样才能体现循环链表
//申请节点 LTNode* LTBuyNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail!"); exit(1); } node->data = x; node->next = node->prev = node; return node; }在双向链表中，因为链表带哨兵卫头节点，，该头节点不含有效数据，所以我们不能改变头节点
所以我们最好对链表的操作传参时，最好传1级指针
之前对于无哨兵卫头节点的单链表，我们传的都是2级指针，所以有小伙伴不能理解，是不是因为带头节点就可以传2级指针，而不带头节点的就穿二级指针呢？
其实不是这样的~
传什么样的指针，取决于你是否对头节点进行了修改
假设我们有一个带头结点和不带头节点的单链表
head → [空节点] → [数据] → [数据] → NULLhead永远指向一个“固定的头结点”（不存有效数据）
head → [数据] → [数据] → NULLhead指向第一个有效数据节点
当我们删除无头结点的第一个数据时
void func(Node* head) { head = head->next; // 只改了副本 }如果还看不懂，我给大家画了一张图
这张图很清晰明了
所以在双向链表中，传1级指针就够用
对双向链表插入数据时，一定要有哨兵卫头节点，所以我们可以在初始化时返回一个头节点，-1表示不是有效数据
//初始化 LTNode* LTInit() { LTNode* head = LTBuyNode(-1); return head; }插入数据
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead phead->prev newnode newnode->prev = phead->prev; newnode->next = phead; phead->prev->next = newnode; phead->prev = newnode; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead newnode phead->next newnode->next = phead->next; newnode->prev = phead; phead->next->prev= newnode; phead->next = newnode; }思路都是一样的，先申请一个节点，然后让该节点的前后指针改变，最后再对前节点的next和后节点的prev指针改变
删除数据
//尾删 void LTPopBack(LTNode* phead) { assert(phead && phead->next != phead); LTNode* ptail = phead; //ptail->prev ptail phead while (ptail->next != phead) { ptail = ptail->next; } phead->prev = ptail->prev; ptail->prev->next = phead; free(ptail); ptail = NULL; } //头删 void LTPopFront(LTNode* phead) { assert(phead && phead->next != phead); LTNode* pcur = phead->next; //phead pcur pcur->next pcur->next->prev = phead; phead->next = pcur->next; free(pcur); pcur = NULL; }大致思路也是一样的，先修改前后节点的指针，然后再释放该节点
指定位置插入/删除
//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); //pos newnode pos->next newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; } //删除pos节点 void LTErase(LTNode* pos) { assert(pos); //pos->prev pos pos->next pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; }查找
//查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }销毁
//销毁 void LTDesTroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur->next != phead) { LTNode* next = pcur->next; free(pcur); pcur = NULL; pcur = next; } free(phead); phead = NULL; }这里要注意一点，销毁和指定位置删除数据时，最后虽然都有对节点=NULL，但是由于是传1级指针，所以在函数外并没有被赋值为NULL，所以我们在main函数调用该函数时，一定要自己加上赋值为NULL
有人问为什么不传2级指针，这样就能在函数内完成赋值NULL操作，结论是：可以这样做，但不建议
因为我们要保持接口的一致性，其他的接口都是传1级，如果这里传2级，就增加了记忆成本
以上就是对双向链表的介绍
