前言
这篇文章主要讲的就是带头+双向+循环链表增删查改的实现
一、带头双向循环链表的初始化
1.1带头双向循环链表的结构体定义
我们应该知道为什么他叫双向循环链表，因为他有两个指针，一个指向自己的next（也就是下一个），一个是prev（也就是自己的上一个），这样是不是就很方便了呢？对比单链表，单链表的删除就需要定义两个指针来删除，还得从头来删除，而带头双向循环链表就不用那么的麻烦啦。下面是结构体的代码描述
typedef int LTDatatype; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDatatype data; }LNode;
1.2初始化代码的实现
首先带头双向循环链表的初始化首先是有一个next，一个prev,这是什么呢？这是一个头指针，一个尾指针，初始化的话可以都先指向自己，如下图所示这就是初始化代码的由来啦。
LNode* LTInit() { LNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
我们会发现这里有一个BuyLTNode函数，这个函数是用来干什么的呢？这个函数是用来开辟一个新的节点的，那么具体是怎么实现的呢？这里我们用到了malloc函数用来动态开辟一个节点。
LNode* BuyLTNode(LTDatatype x) { LNode* newnode = (LNode*)malloc(sizeof(LNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
二、带头+双向+循环链表的增功能实现
2.1头插代码的实现
void LTPustFront(LNode* phead, LTDatatype x) { assert(phead); LNode* newnode = BuyLTNode(x); LNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
我们要进行带头双向循环链表的头插，那么我们应该怎么样头插呢？很多人会认为是在phead那一个指针进行头插，实则并不然，应该是在phead与p之间才是对的，那么我们应该怎么操作才能把我们newnode的节点头插进去呢？首先我们应该找到first，也就是phead->next,我们为什么要找到这一个节点呢？因为我们要在phead和p之间头插所以first这个节点我们必须得是知道的，而且找到这个节点也是有好处的，有什么好处呢？找到这个节点我们就能知道这个节点的位置，之后的操作也会方便很多。
先将cur定义出来，也就是LNode* cur = phead->next;,其次在链接就行啦，phead->next = newnode,newnode->prev = phead,newnode->next = cur,cur->next = newnode;这里的p指针要根据图来链接哦！
2.2尾插代码的实现
void LTPustBack(LNode* phead, LTDatatype x) { assert(phead); LNode* tail = phead->prev; LNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
尾插：顾名思义就是在尾部插入，那么双向带头循环链表有啥优势呢？我们可以直接从头就可以找到尾，就不像单链表需要从头开始找了。如下图所示
这是未插入之前：
这是插入之后：
该图把尾指针的next链接到newnode上，再把头指针的链接链到新开的newnode的节点上。这里我们还需要找到未插入之前的尾节点，那么我们应该怎么找到尾节点呢？LNode* tail = phead->prev;这样我们是不是就能找到尾节点了呢？
三、带头+双向+循环链表的打印功能实现
3.1打印代码的实现
void LTPrint(LNode* phead) { assert(phead); LNode* cur = phead->next; printf("phead<==>"); while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); }
因为我们是带有双向循环链表，我们的最后一个节点，会重新指向头结点，我们只需要把遍历的继续条件设为cur!=phead时就行啦。
四、带头+双向+循环链表删功能实现
4.1头删功能的实现
首先，我们应该怎么样进行头删呢？既然遇到解决不了的事情，我们选择画图来进行理解吧
void LTPopFront(LNode* phead) { assert(phead); LNode* first = phead->next; LNode* second = first->next; phead->next = second; second->prev = phead; free(first); }
4.2尾删功能的实现
void LTPopBack(LNode* phead) { assert(phead); LNode* tail = phead->prev; LNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead; }
五、带头+双向+循环链表查功能实现
5.1查功能代码实现
其实查找功能也就是遍历一遍所有的节点，找到我们想要的值，然后返回就行啦。
LNode* LTFind(LNode* phead, LTDatatype x) { assert(phead); LNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
六、最后的代码全过程实现
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" void TestList1() { LNode* plist = LTInit(); LTPustBack(plist, 1); LTPustBack(plist, 2); LTPustBack(plist, 3); LTPustBack(plist, 4); LTPrint(plist); LTPopBack(plist); LTPrint(plist); } void TestList2() { LNode* plist = LTInit(); LTPustFront(plist, 1); LTPustFront(plist, 2); LTPustFront(plist, 3); LTPustFront(plist, 4); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LNode* pos = LTFind(plist, 3); //LTInsert(pos, 4); LTErase(pos); LTPrint(plist); } int main() { TestList2(); return 0; }
list.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDatatype; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDatatype data; }LNode; LNode* LTInit(); void LTPustBack(LNode* phead, LTDatatype x); void LTPustFront(LNode* phead, LTDatatype x); void LTPopBack(LNode* phead); void LTPopFront(LNode* phead); void LTPrint(LNode* phead); void LTInsert(LNode* pos, LTDatatype x); LNode* LTFind(LNode* phead, LTDatatype x); void LTErase(LNode* pos);
list.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" LNode* BuyLTNode(LTDatatype x) { LNode* newnode = (LNode*)malloc(sizeof(LNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } LNode* LTInit() { LNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTPustBack(LNode* phead, LTDatatype x) { assert(phead); LNode* tail = phead->prev; LNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void LTPrint(LNode* phead) { assert(phead); LNode* cur = phead->next; printf("phead<==>"); while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); } //void LTPustFront(LNode* phead, LTDatatype x) //{ // assert(phead); // LNode* newnode = BuyLTNode(x); // newnode->next = phead->next; // phead->next->prev = newnode; // phead->next = newnode; // newnode->prev = phead; // //} void LTPustFront(LNode* phead, LTDatatype x) { assert(phead); LNode* newnode = BuyLTNode(x); LNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } void LTPopBack(LNode* phead) { assert(phead); LNode* tail = phead->prev; LNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead; } void LTPopFront(LNode* phead) { assert(phead); LNode* first = phead->next; LNode* second = first->next; phead->next = second; second->prev = phead; free(first); } LNode* LTFind(LNode* phead, LTDatatype x) { assert(phead); LNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void LTInsert(LNode* pos, LTDatatype x) { assert(pos); LNode* prev = pos->prev; LNode* newnode = BuyLTNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } void LTErase(LNode* pos) { assert(pos); LNode* tail = pos->next; LNode* prev = pos->prev; prev->next = tail; tail->prev = prev; }
总结
今天带大家了解了数据结构的带头双向循环链表的增删查，其中该数据结构还有随机插入和随机删除我没讲解，大家有不懂的可以评论区留言啦！
