一.特点
pre：指向上一个节点的指针 next:指向下一个节点的指针
- 链表头节点的pre指向尾节点，链表尾节点的next指向头节点
- 两个相邻节点直接相互指向
二.节点插入(尾插)
1.步骤
1.让尾部节点的next指向新添加的节点 2.让新增节点的next节点指向头节点 3.让新增节点的pre节点指向原尾节点 4.改变头节点的pre节点，使其指向新增节点(⚠ 放到最后，否则原尾节点会丢失)
2.示例
(1)反思
注意不要不小心修改传入指针的指向，这样非但没法成功新增节点，还会造成内存泄露
我这次犯的错误：(代码中已修正)
1.将传入节点赋值给申请空间时用了node = &tmp;，这修改了node引用，导致申请空间泄露
2.更新外部head时用了PinHead = &head;,这同样修改了PinHead的引用，传入的head在此时就已经丢失了，所以至始至终，外部的head都还是空的。
(2)代码
这只是一部分，我会在文末放上完整代码
这个代码是外部传入头节点指针，直接通过传入指针修改主调函数的head,所以无需返回值，这个代码内的修改会作用到内存中的数据中，但操作时需要千万注意不要造成内存泄露
/*新增节点*/
//不返回头节点，通过直接修改头节点的指针来实现新增
void LikeInsertion(STU **PinHead, STU tmp) {
//将传入的头节点还原一下，方便操作
STU *head = *PinHead;
//申请空间存储需要添加的节点
STU *node = (STU *) calloc(1, sizeof(STU));
*node = tmp;//注意不要修改node引用
node->pre = NULL;
node->next = NULL;
//判断链表是否为空
if (head == NULL) {
//直接将当前的节点赋值给头节点
head = node;
//修改pre和next两个指针域的指向⚠(只有一个节点时是这么指向的)
node->pre = node;
node->next = node;
} else {
/*链表不为空*/
//让尾节点(head的pre)的next指向新插入的节点
head->pre->next = node;
//让新插入的节点的next指向头节点
node->next = head;
//让新增节点的pre添加尾节点的地址
node->pre = head->pre;
//最后，修改头节点的pre指向新增节点
head->pre = node;
}
//修改头指针的指向，作用于头节点的头指针
*PinHead = head;//注意不要修改PinHead引用
}
(3)结果
请输入你要添加的学生个数:5
请输入你要添加的学生信息:1 yiyi
请输入你要添加的学生信息:2 erer
请输入你要添加的学生信息:3 zhangsan
请输入你要添加的学生信息:4 lisi
请输入你要添加的学生信息:5 wangwu
三.遍历链表
1.概述
双向循环链表的遍历，因为节点间是相互联系的，所以可以尝试两侧同时进行遍历，以提高遍历的效率。因为从两侧同时进行遍历，所以也是存在相遇的情况
(1)遍历的情况：
假设前循环指针是pb,后循环指针是pn
-
节点奇数的情况
- 最后二者会指向同一个节点
pb == pn，只遍历一次即可
- 最后二者会指向同一个节点
-
节点偶数的情况
- 前循环节点的next就是后循环节点
pb->next == pn,两个所指向的节点都要进行打印
- 前循环节点的next就是后循环节点
-
正常情况
- 两个节点所指向的节点都要进行打印
(2)关于前循环节点和后循环节点的移动
前循环指针是向后移动,pb = pb->next
后循环指针是向前移动,pn = pn->pre
2.示例
这只是一部分，我会在文末放上完整代码
代码:
void ergodic(STU *head) {
//判断链表是否为空
if (head == NULL) {
perror("链表为空\n");
return;
} else {
//头部遍历指针
STU *pb = head;
//尾部遍历指针
STU *pn = head->pre;
//死循环
while (1) {
if (pb == pn) {//节点奇数个结束情况，二者指向同一个节点，只遍历一次即可
printf("StuId:%d StuName:%s\n", pb->id, pb->name);
//这是最后才会出现的情况，所以将其作为循环的结束条件
break;
} else if (pb->next == pn) {//节点偶数个结束情况，前循环节点的下一个就是后循环节点
//两个所指向的节点都要进行打印
printf("StuId:%d StuName:%s\n", pb->id, pb->name);
printf("StuId:%d StuName:%s\n", pn->id, pn->name);
//同样，这是最后才会出现的情况，所以将其作为循环的结束条件
break;
} else {
//除上述情况外的情况就是普通的遍历情况了，两个节点所指向的节点都要进行打印
printf("StuId:%d StuName:%s\n", pb->id, pb->name);
printf("StuId:%d StuName:%s\n", pn->id, pn->name);
//移动两个指针,注意，个是向后跑的，一个是向前跑的
pb = pb->next;
pn = pn->pre;
}
}
}
}
**结果:**承接上面插入代码提交的数据
遍历结果
StuId:1 StuName:yiyi
StuId:5 StuName:wangwu
StuId:2 StuName:erer
StuId:4 StuName:lisi
StuId:3 StuName:zhangsan
四.查找指定结点
1.概述
(1)简述
查找结点同样也可以利用双向链表的特点，从两侧同时开始查找，从而提高效率。因为是两侧开始查找，同样也存在结点奇数和偶数时要进行不同处理的情况，这里是直接以其为退出条件即可
(2)结束条件
-
到达双向循环链表的循环结束条件
- 前循环节点等于后循环节点，即重合
- 前循环节点的next指向后循环节点
-
找到要查找的节点
2.示例
**代码:**通过循环去不断匹配结果，当匹配到结果抑或是到了双向循环的
/*根据ID查找节点*/
STU *Search(STU *head, int id) {
//判断链表是否为空
if (head == NULL) {
perror("链表为空\n");
return NULL;
} else {
/*定义两个节点进行遍历查找*/
//头部遍历指针
STU *pb = head;
//尾部遍历指针
STU *pn = head->pre;
/*
*退出条件
* - 到达双向链表循环退出条件
* - 匹配到对应的节点
*/
while (pb != pn && pb->next != pn && pb->id != id && pn->id != id) {
pb = pb->next;
pn = pn->next;
}
//判断是找到节点还是没找到
if (pb->id == id) {
return pb;
} else if (pn->id == id) {
return pn;
} else {
perror("没有找到对应的节点");
}
return NULL;
}
}
**结果：**成功查找到ID为2的同学
请输入你要查找的id:2
该ID对应的是:erer同学
五.删除指定节点
1.概述
(1)简述
最开始当然是找到要删除的节点，逻辑和上面一样。最后删除的时候，分两种情况，一种删除的是头节点，一种删除的是尾部、中部节点
(2)删除逻辑
删除的是头部节点：
假设pb指针指向头结点
关键就在于将头结点的下一个结点变成新的头结点，之后再通过指向头结点的指针去释放头结点即可
//让头节点的下一个节点的pre指向尾节点
head -> next ->pre = head ->pre;
//让尾节点的pre指向头节点的下一个节点
head -> pre = head -> next;
//让头节点指向下一个节点，设置第二个节点为新的头结点
head = head -> next
//释放指向头结点的指针即可
free(pb);
删除的节点是尾部、中部节点:
假设pb指向待删除结点
**尾部节点：**关键在于让其前一个结点与头结点建立联系并断开其与尾部结点的联系，实际逻辑代码和删除中部结点的代码一致 **中部节点：**关键在于将要删除结点的前后两个结点建立联系，解除它们和待删除结点的联系
//让待删除结点的上一个结点的next指向待删除结点的下一个结点
pb -> pre -> next = pb -> next;
//让待删除结点的下一个结点的pre指向待删除结点的上一个结点
pb -> next -> pre = pb -> pre;
2.示例
**代码：**通过操作指针进行节点的删除，删除完毕后更新了外部的head
void delete(STU **InputHead,int id) {
//还原下传入的头部结点指针
STU *head = *InputHead;
//判断链表是否为空
if (head == NULL) {
perror("链表为空\n");
} else {
/*定义两个节点进行遍历查找要删除的结点*/
//头部遍历指针
STU *pb = head;
//尾部遍历指针
STU *pn = head->pre;
/*
*退出条件
* - 到达双向链表循环退出条件
* - 匹配到对应的节点
*/
while (pb != pn && pb->next != pn && pb->id != id && pn->id != id) {
pb = pb->next;
pn = pn->next;
}
if (pb->id == id) {//头、中部结点
if (pb == head) {//遍历到头部结点
//让头部结点的下一个结点指向尾部结点
head->next->pre = head->pre;
//让尾部结点指向头部结点的下一个结点
head->pre->next = head->next;
//将头部节点的下一个结点定义为新的头部结点
head = head->next;
} else {
pb->next->pre = pb->pre;
pb->pre->next = pb->next;
}
printf("删除的节点的ID是%d\n",pb->id);
free(pb);//通过指针释放结点
} else if (pn->id == id) {//尾、中部结点
/*尾部结点和头部结点的逻辑是一样的*/
pn->next->pre = pn->pre;
pn->pre->next = pn->next;
printf("删除的节点的ID是%d\n",pn->id);
free(pn);
} else {
perror("没有找到对应的节点");
}
//删除成功，更新外部的head
*InputHead = head;
}
}
**结果:**成功删除ID为3的节点
请输入你要删除的id:3
删除的节点的ID是3
六.释放链表
1.概述
需要注意双向链表的释放结束条件是指针指向头结点的地址，不需要多在意，空间释放了，其地址还是存在的
它其实仍然是使用单向链表的方式进行释放，让head不断移动到下一个结点，用指向head的指针释放head结点，最后的结束条件是head的指针指向了最开始的头结点地址
2.示例
需要注意的是循环的结束条件，这不同于单向链表
**代码：**操作指针去释放链表，最后将释放后链表的头节点置空，让后继还能继续添加数据
void linkFree(STU **Head) {
//将head指针还原成head
STU *head = *Head;
STU *pb = head;
//循环依次释放节点
do {
head = head->next;
free(pb);
pb = head;
} while (pb != *Head);//当pb等于最开始传入头节点的地址时，停止循环
//将外部的head置空，让其后继还可以进行添加
*Head =NULL;
}
**结果：**遍历的结果为空，说明之前添加的数据被释放
链表为空
: Success
1 条评论
不错不错，我喜欢看