概念
本文讲述的双向链表，全名叫做带头双向循环链表，我们学习的链表总共有八种
在前文讲述单链表时所讲到的单链表，其实就叫做不带头单向不循环链表，这里的带头、不带头才是真正的头结点，前文中的头结点其实叫做首元素结点，为了方便理解就叫做头结点，要注意分别
那真正的头结点是什么呢？有什么用呢？
带头链表中头结点其实叫做“哨兵位”，在哨兵位中不存储任何有效元素，在这里就是占个位置，听起来有点占着茅坑不拉屎的意思，其实不然，它在循环链表中具有重要作用，接下来为你缓缓讲述
双向链表的实现
结构体形式
在本文讲述的双向链表中，它由三个部分组成：存储的数据（data）、指向上一结点的指针（prev）、指向下一结点的指针（next）
代码为：
typedef struct ListNode
{LTDataType data;struct ListNode* next;//指向下一个结点地址的指针struct ListNode* prev;//指向上一个结点地址的指针}LTNode;初始化
双向链表的初始化有两种方法，一种是传参、一种是返回值形式
这里我们使用返回值形式，在初始化中为了实现循环，一开始要将它的next和prev都指向它本身，它存储的数据随便赋一个值这里我是赋值为-1
代码为：
LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//申请空间建立结点--哨兵位phead->data = -1;phead->next = phead->prev = phead;return phead;
}
结点的建立
代码为
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = node;return node;
}打印
打印开始是从哨兵位的下一结点，结束条件是再次回到哨兵位
代码为
//打印
LTNode* LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;//指向哨兵位的下一个结点while (pcur != phead)//循环结束条件：当pcur回到哨兵位时{printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}尾插
双向链表的尾部插入需要注意插入位置前后两个结点，本文求的链表是双向带头循环的，尾部插入就需要注意哨兵位和哨兵位前一个结点（也就是尾结点）
画图可得
代码为
//尾插
LTNode* LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}头插
头插和尾插思路差不多，不同的就是根据插入位置，要处理的结点也不同，头部插入要注意的就是哨兵位和首元素结点（又是哨兵位的下一结点）
画图可得
代码为
//头插
LTNode* LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}判空
判定链表是否只有哨兵位
代码为
//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//当哨兵位的下一结点等于它自身时，链表为空
}尾删
尾部的删除要考虑的结点就是哨兵位和尾结点的前一结点
画图可得
代码为
//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));//phead del->prev del LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}头删
头部的删除就是处理哨兵位和首结点下一结点的关系
画图可得
代码为
//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));//phead del del->nextLTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = 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;
}在指定位置之后插入数据
在给定位置之后插入数据，首先要将插入位置之后的结点位置保存下来，在进行结点的插入
画图可得
代码为
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);LTNode* next = pos->next;//pos newnode pos->next(next)newnode->next = next;newnode->prev = pos;next->prev = newnode;pos->next = newnode;
}在指定位置删除数据
这一步也很简单，不需要特意考虑哨兵位的关系，就直接将指定位置前后结点相连，再将指定位置结点删除就行
代码为
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}销毁
销毁有两种方式：
一种是以二级指针将链表在销毁函数中彻底实现销毁，但这种方法用到二级指针和其他功能实现函数用到的一级指针不同，这样会导致接口不一致，虽然不是什么大问题，如果别人要使用你的这个双向链表可能会出错，所以不建议使用
代码为
void LTDestroy(LTNode** pphead)//为了保证接口一致性，不使用这种方法
{assert(pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;}第二种就是用一级指针，在销毁函数将除哨兵位以外的结点都给销毁，但是哨兵位要在函数外进行手动销毁，这种方式保证了接口的一致性
代码为
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}
链表和顺序表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理结构为线性，为连续性 | 逻辑结构上为线性，物理结构上不为线性 |
| 随机访问 | 支持（时间复杂度O(1)） 可以根据下标进行随机访问 | 不支持（访问时间复杂度O(n)） |
| 任意位置插⼊或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表在空间不足时可以申请空间，但可能会造成空间浪费 | 不需要扩容，可以根据需求来进行空间的申请，不会造成空间浪费 |
| 应用场景 | 元素高度存储和频繁访问 | 在任意位置高效插入和删除数据 |