本篇博客只讲：带头双向循环链表

💨回顾单链表

之前在博客中讲过单链表，但单链表的缺陷很明显。它无法找到前驱（即前一个节点）。

单链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,
如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

💨双链表

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

有了单链表的讲述，我们就直接进行双链表的结构体定义和一些接口实现。

💨双链表结构体的定义

typedefintLTDataType;
typedefstructListNode{
structListNode*next;
structListNode*prve;
LTDataTypedata;
}ListNode;

1. 把int重命名为LTDataType （为了增强代码可维护性）
2. 结构体的成员变量里，我定义了两个结构体指针，next和prve，双链表有两个指针域一个数据域，next指针指向下一个节点，prve指针指向前一个节点，data就是当前节点的数据域，存的数据类型就是LTDataType（int）。
3. 把结构体变量重命名为ListNode，不然每次使用都要带上struct。

💨接口函数的实现

🎈开辟节点函数

ListNode*BuyListNode(LTDataTypex)
{
ListNode*newnode= (ListNode*)malloc(sizeof(ListNode));
newnode->data=x;
newnode->next=NULL;
returnnewnode;
}

我们无论是初始化链表，还是头插尾插时，一定会使用到新开辟一个节点，所以单门拿出来写成一个函数。

带返回值的目的是为了初始化链表的时候，避免使用二级指针，因为带头节点的链表我们就是可以避免使用二级指针的现象。

🎈初始化链表

ListNode*ListInit() //初始化{
ListNode*phead=BuyListNode(0);
phead->next=phead;
phead->prve=phead;
returnphead;
}

同样，为了避免使用二级指针，加入了返回值，当初始化完成时，直接把头节点指针返回给主函数，这样，一个带有头节点的双向循环链表就初始化完成了。

主函数接收如下

ListNode*plist=ListInit();

• 初始化的时候，那个BuyListNode()括号里的任填，只要是L只是为了头插尾插而准备，一般不会用到头节点的数据域。只要数据类型是LTDataType（int）就行。
• 初始化的时候，头节点的指针域肯定都指向自己。

🎈打印链表

voidListPrint(ListNode*phead) //打印{
ListNode*cur=phead->next;
while (cur!=phead)
    {
printf("%d ",cur->data);
cur=cur->next;
    }
printf("\n");
}

定义一个结构体指针cur，从头节点的下一个节点开始打印，直到cur再次指向头节点结束。

🎈查找

ListNode*ListFind(ListNode*phead,LTDataTypex) //查找{
assert(phead);
ListNode*cur=phead->next;
while (cur!=phead)
    {
if(cur->data==x)
returncur;
cur=cur->next;
    }
returnNULL;
}

• 查找时把链表和你要查找的内容传过来。
• assert判断你传的链表是否为空
• 建一个结构体指针cur从头节点phead的下一个节点开始找，一直再次到头节点为止。
• 如果中途找到返回指针，没找到等循环结束返回空指针

主函数接收如下

ListNode*pos=ListFind(plist,3);

因为我写的时候，初始化链表时，主函数用ListNode* plist接收，插入了一个3。

🎈在某位置前插入数据

//pos位置之前插入xvoidListInsert(ListNode*pos , LTDataTypex)
{
assert(pos);
ListNode*prve=pos->prve;
ListNode*newnode=BuyListNode(x);
prve->next=newnode;
newnode->prve=prve;
newnode->next=pos;
pos->prve=newnode;
}

1. 先判断链表是否为空
2. 先创建一个结构体指针prve指向当前位置的前一个节点（一定要先查找再用此函数，不然程序怎么知道你在哪个位置前插入）
3. 创建一个newnode指针作为你要插入的新节点
4. prve的next指针域指向newnode
5. newnode的prve指针域指向prve（注意prve指针域是结构体的成员变量，指向的prve是我定义的结构体指针，别弄混了）
6. newnode的next指针域指向pos
7. pos的prve指针域指向newnode

重点注意

🌹这种先创建一个结构体指针指向pos位置前一个节点的方法，好处是为了避免你写指针时需要注意顺序问题，有了指针，你就不用担心顺序写的对不对。

🎈删除某位置的值

//删除pos位置的值voidListErase(ListNode*pos)
{
assert(pos);
ListNode*prve=pos->prve;
ListNode*next=pos->next;
prve->next=next;
next->prve=prve;
free(pos);

1. 定义一个结构体指针prve指向当前位置的前一个节点
2. 定义一个结构体指针next指向当前位置的后一个节点
3. 前一个节点的next域指向后一个节点
4. 后一个节点的prve域指向前一个节点
5. 再释放掉此节点

🎈尾插

voidListPushBack(ListNode*phead , LTDataTypex) //尾插{
assert(phead);
ListNode*tail=phead->prve;
ListNode*newnode=BuyListNode(x);
tail->next=newnode;
newnode->prve=tail;
newnode->next=phead;
phead->prve=newnode;
// ListInsert(phead,x);}

1. assert判断链表是否为空
2. 新开一个tail指针指向头节点的前一个（原因开上面的重点注意）
3. 建一个newnode就代表你要插入的节点
4. 接下来就是更换本来的尾节点和next域指向和头节点prve域的指向就行
5. 然后newnode新节点的指向也要定义

上面我们写了在某个位置前插入的函数，可以直接调用他 ListInsert(phead,x)

🎈头插

voidListPushFront(ListNode*phead , LTDataTypex) //头插{
assert(phead);
ListNode*first=phead->next;
ListNode*newnode=BuyListNode(x);
phead->next=newnode;
newnode->prve=phead;
newnode->next=first;
first->prve=newnode;
//    ListInsert(phead->next,x);/*另一种写法需要注意顺序ListNode * newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prve = newnode;phead->next = newnode;newnode->prve = phead;*/}

• 同样也可以直接调用上面的那个函数，具体实现和尾插差不多，只要更改指针域的指向即可
• 下面我又写了另一种写法，这种写法就是不创建指针，但要注意顺序。

🎈尾删

voidListPopBack(ListNode*phead) //尾删{
assert(phead);
assert(phead->next!=phead);
ListNode*tail=phead->prve;
ListNode*prev=tail->prve;
prev->next=phead;
phead->prve=prev;
free(tail);
tail=NULL;
//ListErase(phead->prev);}

尾删，头删也可以调用之前我们写的删除某个位置的函数。

🎈头删

voidListPopFront(ListNode*phead) //头删{
assert(phead);
assert(phead->next!=phead);
ListNode*first=phead->next;
ListNode*second=phead->next->next;
phead->next=second;
second->prve=phead;
free(first);
first=NULL;
//ListErase(phead->next);}