这篇文章主要介绍“C++带头双向循环链表怎么实现”，在日常操作中，相信很多人在C++带头双向循环链表怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++带头双向循环链表怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
与单链表的区别
单向/双向
单向：只有一个ｎｅｘｔ指针，只指向下一位元素
双向：有两个指针，指向上一位和下一位元素，寻找前一节点和后一节点很便利
带头/不带头
带头：在本来的头结点之前还有一个哨兵卫节点作为头节点，它的址域指针指向头节点，值域不做使用
不带头：没有哨兵卫头节点，在尾删尾插等问题中要考虑头结点的情况（局限）
循环/非循环
循环：头结点会与尾节点相连
非循环：头结点不与尾节点相连
代码的实现
接口
// 创建链表（链表初始化）ListNode* ListCreate();//创建节点ListNode* BuyListNode(ListNode* pHead);// 双向链表销毁void ListDestory(ListNode* pHead);// 双向链表打印void ListPrint(ListNode* pHead);// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删void ListPopBack(ListNode* pHead);// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删void ListPopFront(ListNode* pHead);// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x);// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点void ListErase(ListNode* pos);节点的构造
typedef int LTDataType;typedef struct ListNode{LTDataType data;struct ListNode* next;struct ListNode* prev;}ListNode;初始化链表
// 创建链表（初始化）ListNode* ListCreate(){//开辟哨兵卫头结点ListNode* plist = (ListNode*)malloc(sizeof(ListNode));if (plist == NULL)//失败打印错误信息并结束进程{perror("ListCreat fail:");exit(-1);}plist->next = plist;plist->prev = plist;return plist;}开辟节点
//创建节点ListNode* BuyListNode(LTDataType x){//创建节点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL)//失败打印错误信息并结束进程{perror("creatnode fail:");exit(-1);}newnode->data = x;//初始化结点newnode->next = NULL;newnode->prev = NULL;return newnode;}销毁链表
注：动态开辟的链表空间，在不使用后需要将之释放，避免造成内存泄漏
// 双向链表销毁void ListDestory(ListNode* pHead){//断言传入指针不为NULLassert(pHead);ListNode* cur = pHead;pHead->prev->next = NULL;while (cur!=NULL){ListNode* next = cur->next;free(cur);cur = next;}return;}打印链表
// 双向链表打印void ListPrint(ListNode* pHead){//断言传入指针不为NULLassert(pHead);//创建寻址指针ListNode* cur = pHead->next;//循环遍历链表while (cur != pHead){//打印数据printf("%d->", cur->data);//找到下一个节点cur = cur->next;}printf("NULL\n");return;}尾插链表
// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x){//断言传入指针不为NULLassert(pHead);//创建节点ListNode* newnode = BuyListNode(x);//找到尾节点ListNode* tail=pHead->prev;tail->next = newnode;newnode->prev = tail; pHead->prev = newnode;newnode->next = pHead;}尾删链表
尾删前记录前一节点的地址
// 双向链表尾删void ListPopBack(ListNode* pHead){//断言传入指针不为NULLassert(pHead);//只剩哨兵卫头结点的情况if (pHead->prev == pHead)return;//记录尾节点及其前一节点ListNode* tail = pHead->prev;ListNode* tailprev = tail->prev;//释放尾节点free(tail);//构建尾节点前一节点与哨兵卫头结点的关系tailprev->next = pHead;pHead->prev = tailprev;return;}头插链表
头插前记录哨兵卫头节点的下一节点
// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x){//断言传入指针不为NULLassert(pHead);//创建节点ListNode* newnode = BuyListNode(x);//记录哨兵卫头结点的下一节点ListNode* next = pHead->next;//构建各节点之间的关系pHead->next = newnode;newnode->prev = pHead; newnode->next = next;next->prev = newnode;return;}头删链表
// 双向链表头删void ListPopFront(ListNode* pHead){//断言传入指针不为NULLassert(pHead);//只剩哨兵卫头结点的情况if (pHead->next == pHead)return;//记录哨兵卫头结点下一节点及其的下一节点ListNode* next = pHead->next;ListNode* nextNext = next->next;//释放节点free(next);pHead->next = nextNext;nextNext->prev = pHead;return;}查找链表
// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x){//断言传入指针不为NULLassert(pHead);//创建寻址指针ListNode* cur = pHead->next;while (cur != pHead){//比较数据if (cur->data == x)return cur;//找到下一个节点cur = cur->next;}//没找到则返回NULLreturn NULL;}链表pos位置的删除
void ListErase(ListNode* pos){assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);prev->next = next;next->prev = prev;return;}到此，关于“C++带头双向循环链表怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！
