1.双向链表概念
双向链表是一种数据结构，它是单链表的扩展，每个节点除了有指向后继节点的指针之外，还有指向前驱节点的指针。
双向链表的节点有三个部分组成：数据域、指向前驱结点的指针和指向后继结点的指针。
双向链表的构建和单链表类似，可以从头部或尾部插入节点，也可以从头部或尾部删除节点，可以在双向链表中任意节点前或后插入节点，也可以删除任意节点。相比于单链表，双向链表的优点在于能够直接访问前驱节点，这在一些场景下非常方便，但相应地，需要额外的空间存储每个节点的前驱指针。同时，由于需要维护前驱指针，双向链表的插入和删除操作比单链表复杂一些。
2.双向链表的结构
直接看图：
3.双向链表的增删查改
在编写插入时有一个小技巧，我们可以先让新创建的结点的指针先指向链表，然后再去修改链表的头结点和尾结点的指针，这样可以避免在插入新结点过程中造成混乱
修改链表头结点和尾结点的指针指向：
这样新结点就插入成功啦！
头文件：
typedef int LTDataType; //定义双向链表节点的结构 typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; //声明双向链表中提供的方法 //初始化 void LTInit(LTNode** pphead); //LTNode* LTInit(); //销毁链表 void LTDesTroy(LTNode* phead); //打印 void LTPrint(LTNode* phead); //插入数据之前，链表必须初始化到只有一个头结点的情况 //不改变哨兵位的地址，因此传一级即可 //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x); //删除pos节点 void LTErase(LTNode* pos); //查找结点 LTNode* LTFind(LTNode* phead, LTDataType x);
代码实现：
初始化：
void LTInit(LTNode** pphead) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) exit(1); node->next = node; node->prev = node; *pphead = node; }
销毁链表：
void LTDesTroy(LTNode* phead) { LTNode* node = phead->next; while (node != phead) { LTNode* node1 = node->next; free(node); node = node1; } free(phead); phead = NULL; }
打印：
void LTPrint(LTNode* phead) { LTNode* node = phead->next; while (node!= phead) { printf("%d->", node->data); node = node->next; } }
尾插尾删：
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { LTNode* node = c_jian(x); node->prev = phead->prev; node->next = phead; phead->prev->next = node; phead->prev = node; } //尾删 void LTPopBack(LTNode* phead) { LTNode* node = phead->prev; phead->prev->prev->next = phead; phead->prev = phead->prev->prev; free(node); node = NULL; }
头插头删：
//头插 void LTPushFront(LTNode* phead, LTDataType x) { LTNode* node = c_jian(x); node->next = phead->next; node->prev = phead; phead->next->prev = node; phead->next = node; } //头删 void LTPopFront(LTNode* phead) { LTNode* node = phead->next; phead->next->next->prev = phead; phead->next = phead->next->next; free(node); node = NULL; }
在pos位置之后插入数据：
void LTInsert(LTNode* pos, LTDataType x) { LTNode* node = c_jian(x); node->next = pos->next; node->prev = pos; pos->next->prev = node; pos->next = node; }
查找结点：
LTNode* LTFind(LTNode* phead, LTDataType x) { LTNode* node = phead->next; while (node != phead) { if (node->data == x) { return node; } node = node->next; } return NULL; }
删除pos节点：
void LTErase(LTNode* pos) { LTNode* node = pos; pos->next->prev = pos->prev; pos->prev->next = pos->next; free(node); node = NULL; }
