目录

一.前言

二.双向带头循环链表的结构

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

2.Listdestroy

B.插入

1.头插  ListNodepushfront

2.尾插 ListNodepushback

3.插入 ListNodeinsert

C.删除

1.头删 ListNodepopfront

2.尾删 ListNodepopback

3.删除 ListNodeerase

D.打印  ListNodeprint

四.源码

List.h

List.c

test.c

一.前言

在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。

那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。

二.双向带头循环链表的结构

1.该链表有一个哨兵位节点，即头节点；

2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继；

3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。

请看图示：

 别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。

LNode* Buynewnode(DLdatatype x)   //定义一个 malloc 新节点的函数，以便后续需要
{LNode* newnode = (LNode*)malloc(sizeof(LNode));assert(newnode);newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}
LNode* ListNodeinit()
{LNode* phead = (LNode*)malloc(sizeof(LNode));assert(phead);phead->prev = phead;  //使其都指向自己phead->next = phead;phead->data = -1;return phead;
}

2.Listdestroy

我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；

注意：应该是从头节点的 next 开始遍历。

void ListNodedestroy(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){LNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

B.插入

1.头插  ListNodepushfront

1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题；

2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点；

3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点；

这里并不需要考虑链表为空的情况，这就是双链表的强大之处。

void ListNodepushfront(LNode* phead, DLdatatype x)
{assert(phead);LNode* newnode = Buynewnode(x);LNode* first = phead->next;  //保存头节点的下一个phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

2.尾插 ListNodepushback

1.尾插就需要找尾；

2.这里的找尾很简单，就是头节点的 prev；

3.将尾节点与新节点链接起来。

void ListNodepushback(LNode* phead, DLdatatype x)
{assert(phead);LNode* newnode = Buynewnode(x);LNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

3.插入 ListNodeinsert

1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos；

2.找到 pos 的前驱 prev ；

3.将前驱，pos，新节点链接起来。

LNode* ListNodefind(LNode* phead,DLdatatype x)
{assert(phead);LNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{assert(phead);assert(pos);LNode* newnode = Buynewnode(x);LNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。

C.删除

1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构；

2.如果是空链表也不能删除。

1.头删 ListNodepopfront

1.删除时保存其下一个节点；

2.链接头节点 phead 和 保存的下一个节点；

3.删除 phead 的next。

void ListNodepopfront(LNode* phead)
{assert(phead);assert(ListNodeempty(phead));if (phead->next == phead){perror("ListNodepopfront");return;}LNode* first = phead->next;LNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}

2.尾删 ListNodepopback

1.找尾，即：phead的prev；

2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；

void ListNodepopback(LNode* phead)
{assert(phead);assert(ListNodeempty(phead));if (phead->next == phead){perror("ListNodepopback");exit(-1);}LNode* tail = phead->prev;LNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;
}

3.删除 ListNodeerase

1.调用 find 函数找到要删除的节点pos；

2.找到 pos 的前驱和后继；

3.链接其前驱，后继；

4.删除pos。

void ListNodeerase(LNode* pos, LNode* phead)
{assert(phead);assert(pos);if (phead->next == phead){perror("ListNodeerase");exit(-1);}LNode* prev = pos->prev;LNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

总结：这里可以复用删除函数去实现头删和尾删。

D.打印  ListNodeprint

注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。

void ListNodeprint(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){printf("%d <=> ", cur->data);cur = cur->next;}printf("\n");}

四.源码

List.h

#pragma once#include 
#include 
#include 
#include typedef int DLdatatype;typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;DLdatatype data;
}LNode;LNode* ListNodeinit();void ListNodeprint(LNode* phead);void ListNodepushback(LNode*phead,DLdatatype x);void ListNodepushfront(LNode* phead, DLdatatype x);void ListNodepopback(LNode* phead);void ListNodepopfront(LNode* phead);LNode* ListNodefind(LNode* phead,DLdatatype x);void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x);void ListNodeerase(LNode* pos, LNode* phead);void ListNodedestroy(LNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS#include "List.h"LNode* Buynewnode(DLdatatype x)
{LNode* newnode = (LNode*)malloc(sizeof(LNode));assert(newnode);newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}LNode* ListNodeinit()
{LNode* phead = (LNode*)malloc(sizeof(LNode));assert(phead);phead->prev = phead;phead->next = phead;phead->data = -1;return phead;
}void ListNodeprint(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){printf("%d <=> ", cur->data);cur = cur->next;}printf("\n");}void ListNodepushback(LNode* phead, DLdatatype x)
{assert(phead);/*LNode* newnode = Buynewnode(x);LNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;*/ListNodeinsert(phead, phead, x);}void ListNodepushfront(LNode* phead, DLdatatype x)
{assert(phead);/*LNode* newnode = Buynewnode(x);LNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;*/ListNodeinsert(phead->next, phead, x);
}bool ListNodeempty(LNode* phead)
{assert(phead);return phead->next == phead;
}void ListNodepopback(LNode* phead)
{assert(phead);//assert(ListNodeempty(phead));if (phead->next == phead){perror("ListNodepopback");exit(-1);}/*LNode* tail = phead->prev;LNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;*/ListNodeerase(phead->prev, phead);
}void ListNodepopfront(LNode* phead)
{assert(phead);//assert(ListNodeempty(phead));if (phead->next == phead){perror("ListNodepopfront");return;}/*LNode* first = phead->next;LNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;*/ListNodeerase(phead->next, phead);
}LNode* ListNodefind(LNode* phead,DLdatatype x)
{assert(phead);LNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{assert(phead);assert(pos);LNode* newnode = Buynewnode(x);LNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}void ListNodeerase(LNode* pos, LNode* phead)
{assert(phead);assert(pos);if (phead->next == phead){perror("ListNodeerase");exit(-1);}LNode* prev = pos->prev;LNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}void ListNodedestroy(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){LNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;}

test.c

至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来。

😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃