目录
?
一、什么是双向链表
二、双向链表的定义?
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
哨兵位头结点：里面有两个指针，prev和next
prev：记录前一个结点的地址
next：记录后一个结点的地址
哨兵位结点是为了方便增删查改，里面并不存储有效数据
三、链表的初始化
typedef int SLDataType;//方便后续修改数据类型
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;//前驱指针
struct ListNode* prev;//后继指针
}LTNode;
因为我们的链表带了一个哨兵位头结点，我们初始化时需要开辟一个头结点出来，哨兵位头结点head的特征是不存储有效数据，有prev和next指针。
因为我们要设计链表的增删查改，涉及对于结点的操作，于是我们可以将创造结点封装成一个函数BuyListNode。
//创建一个新结点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;//新结点赋值
node->prev = NULL;
node->next = NULL;
return node;//返回新结点
}
//初始化链表
LTNode* ListInit()
{
LTNode* phead = BuyListNode(-1);//申请一个头结点，头结点不存储有效数据
phead->prev = phead;
phead->next = phead;
return phead;//返回头结点
}
四、销毁链表
我们用于动态内存开辟的空间，到最后都会返还给操作系统，我们不能直接free哨兵位结点的下一个结点，必须遍历一遍挨着销毁，定义一个cur指针，直到最后返回到头指针结束
void ListDestroy(LTNode* phead)
{
assert(phead);
LTNode*cur=phead->next;
LTNode*next=cur->next;记录cur的下一个位置
while(cur!=phead)
{
free(cur);
cur=next;
next=next->next;
}
free(phead);
phead=NULL;
}五、链表的插入
由于我们有着哨兵位的头结点，我们根本不会改变它，就不用像单链表那样传二级指针，只需传入一级指针即可，而且有了它我们操作双向链表不需要再进行找尾。
任意位置的插入
准确的说，我们是在任意位置之前插入，我们只需要在要修改的位置，直接改变指针间的链接关系即可，我们需要pos位置，为方便操作，我定义一个posPrev记录前一个位置
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->next = pos;
pos->prev = newnode;
newnode->prev = posPrev;
}
动画演示：
?
?
头插
我们只需在哨兵位结点的后面插入即可，引用我们刚刚写的任意位置插入函数即可?
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
尾插
根据双向链表的结构，头结点的前一个就是尾，我们只需要在头的前面插入即相当于尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
六、链表的删除
任意位置的删除
我们只需要直接修改两个结点间的指向关系，相当于就把中间结点给断开删除了
void ListErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
动画演示：
?
头删
我们可以复用我们的任意位置删除函数，相当于在头结点的下一个结点删除数据
void ListPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* head = phead->next;
head->next->prev = phead;
phead->next = head->next;
free(head);
head = NULL;
}
尾删
我们同样可以复用我们的任意位置删除函数，只需要在phead的前一个给free掉，再调整指向关系即可
void ListPopBack(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* tail = phead->prev;
tail->prev->next = phead;
phead->prev = tail->prev;
free(tail);
tail = NULL;
}
七、链表的查找
我们可以定义一个cur指针去遍历寻找，比较可得要查找的数字
LTNode* ListFind(LTNode* phead,LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
八、链表的打印
同样可以定义一个cur指针去循环遍历打印
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
谢谢大家的观看！！