双向循环链表与双向链表的区别：指的是双向循环链表的首节点中的Prev指针成员指向链表的尾节点，并且双向循环链表的尾节点里的next指针成员指向链表的首节点，所以双向循环链表也属于环形链表
Double_Circular_Linked_list.h
/**
* @file : doubleCircularlinkedist
* @brief : 实现循环双链表的插入、删除、遍历
* @author : TingFengLuo@126.com
* @date : 2025-12-23
* @version 1.0 : V1.0
* @note : 循环双链表的前后指针没有指向空，体现循环思想，该链表有个头节点便于管理
*/
#ifndef __DOUBLECIRCULARLINKEDLIST_H
#define __DOUBLECIRCULARLINKEDLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//将int类型重命名为DataType_t,便于后续用户修改
typedef int DataType_t;
//创建环形双链表节点
typedef struct DoubleCircular_linkedlist{
DataType_t data;
struct DoubleCircular_linkedlist *prev;
struct DoubleCircular_linkedlist *next;
}DoubleCirLList_t;
//双向循环链表的创建
DoubleCirLList_t *DoubleCirLList_create(void);
//双向循环链表新节点的创建
DoubleCirLList_t *DoubleCirLList_NewNode(DataType_t data);
//双向循环链表在头部插入新节点
bool DoubleCirLList_HeadAdd(DoubleCirLList_t *head,DataType_t data);
//双向循环链表在尾部插入新节点
bool DoubleCirLList_TailAdd(DoubleCirLList_t *head,DataType_t data);
//双向循环链表在目标值后面插入新节点
bool DoubleCirLList_DestAdd(DoubleCirLList_t *head,DataType_t dest,DataType_t data);
//双向循环链表在头部删除节点
bool DoubleCirLList_HeadDel(DoubleCirLList_t *head);
//双向循环链表在尾部删除节点
bool DoubleCirLList_TailDel(DoubleCirLList_t *head);
//双向循环链表删除目标值
bool DoubleCirLList_DestDel(DoubleCirLList_t *head,DataType_t dest);
//双向循环链表遍历
void DoubleCirLList_show(DoubleCirLList_t *head);
#endif
Double_Circular_Linked_list.c
#include "doubleCircularlinkedlist.h"
/**
* @name : DoubleCirLList_create
* @brief : 实现循环双向链表的创建
* @param : void
* @retval : 返回创建成功的头节点地址
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : 双循环链表的创建有一个头头节点，头节点的前指针和后指针都指向自身，头指针没有数据域
*/
DoubleCirLList_t *DoubleCirLList_create(void)
{
//创建头节点，并为其分配内存
DoubleCirLList_t *head = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_t));
//判断头节点是否创建成功
if(NULL == head){
perror("create mempry failed for head");
return NULL;
}
//初始化头指针的前后节点指向自身，体现循环思想，头指针只是便于管理链表，所以不需要数据域
head->prev = head;
head->next = head;
return head;
}
/**
* @name : DoubleCirLList_NewNode
* @brief : 实现循环双向链表新节点的创建
* @param
@data :用于给新节点传输的数据
* @retval : 返回创建成功的新节点
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : 新节点创建成功返回新节点的地址，否则直接退出程序
*/
DoubleCirLList_t *DoubleCirLList_NewNode(DataType_t data)
{
//创建一个变量new_node用于存储新节点的地址
DoubleCirLList_t *new_node = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_t));
//判断新节点是否创建成功，若失败，直接退出程序
if(NULL == new_node){
perror("create memory failed for new_node");
return NULL;
}
//初始化新节点
new_node->data = data;
new_node->prev = new_node;
new_node->next = new_node;
return new_node;
}
/**
* @name : DoubleCirLList_HeadAdd
* @brief : 实现循环双向链表在头部插入新节点
* @param
@head: 表示需要操作的链表
@data: 用于给新节点传输的数据
* @retval : 创建成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_HeadAdd(DoubleCirLList_t *head,DataType_t data)
{
//判断链表是否为空
if(NULL == head){
printf("double circular linked list do not exist\n");
return false;
}
//创建变量用于存储新节点的地址
DoubleCirLList_t *new_node = DoubleCirLList_NewNode(data);
if(NULL == new_node){
printf("Double Circular linked list create memory failed for new_node in headAdd\n");
return false;
}
//插入新节点
new_node->next = head->next;
new_node->prev = head;
head->next->prev = new_node;
head->next = new_node;
return true;
}
/**
* @name : DoubleCirLList_TailAdd
* @brief : 实现循环双向链表在尾部插入新节点
* @param
@head: 表示需要操作的链表
@data: 用于给新节点传输的数据
* @retval : 创建成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_TailAdd(DoubleCirLList_t *head,DataType_t data)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list do not exist\n");
return false;
}
//创建变量用于存储新节点的地址
DoubleCirLList_t *new_node = DoubleCirLList_NewNode(data);
if(NULL == new_node){
printf("Double Circular linked list create memory failed for new_node in headAdd\n");
return false;
}
//如果链表为空,直接添加节点
if(head->next == head){
new_node->prev = head;
new_node->next = head;
head->next = new_node;
head->prev = new_node;
return true;
}
//创建变量用于保存尾节点
DoubleCirLList_t *tail_node = head->prev;
new_node->prev = tail_node;
new_node->next = head;
tail_node->next = new_node;
head->prev = new_node;
return true;
}
/**
* @name : DoubleCirLList_DestAdd
* @brief : 实现循环双向链表在目标值后插入新节点
* @param
@head: 表示需要操作的链表
@dest: 表示需要加入的目标值的前一个值
@data: 用于给新节点传输的数据
* @retval : 创建成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_DestAdd(DoubleCirLList_t *head,DataType_t dest,DataType_t data)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list do not exist\n");
return false;
}
//创建变量用于存储新节点的地址
DoubleCirLList_t *new_node = DoubleCirLList_NewNode(data);
if(NULL == new_node){
printf("Double Circular linked list create memory failed for new_node in headAdd\n");
return false;
}
//创建变量用于保存目标节点的地址
DoubleCirLList_t *phead = head->next;
//查找目标节点
while(phead != head){
if(phead->data == dest){
new_node->prev = phead;
new_node->next = phead->next;
phead->next->prev = new_node;
phead->next = new_node;
return true;
}
phead = phead->next;
}
printf("double circular linked list do not have dest value=%d\n",dest);
free(new_node);
new_node = NULL;
return false;
}
/**
* @name : DoubleCirLList_HeadDel
* @brief : 实现循环双向链表在头部删除首节点
* @param
@head: 表示需要操作的链表
* @retval : 删除成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_HeadDel(DoubleCirLList_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list create memory failed for head\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("double circular linked list do not Valid node\n");
return false;
}
//创建变量用与保存首节点地址
DoubleCirLList_t *phead = head->next;
// 尾节点指向原首节点的下一个节点
phead->next->prev = phead->prev;
// 原首节点的后继节点指向尾节点
phead->prev->next = phead->next;
// 哨兵头节点指向新的首节点
head->next = phead->next;
//释放待删除节点内存
free(phead);
// 避免野指针
phead = NULL;
return true;
}
/**
* @name : DoubleCirLList_TailDel
* @brief : 实现循环双向链表在尾部删除首节点
* @param
@head: 表示需要操作的链表
* @retval : 删除成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_TailDel(DoubleCirLList_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list create memory failed for head\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("double circular linked list do not have Valid node\n");
return false;
}
//创建变量用于存储存储尾节点地址
DoubleCirLList_t *tail = head->prev;
tail->prev->next = head;
head->prev = tail->prev;
free(tail);
tail = NULL;
return true;
}
/**
* @name : DoubleCirLList_DestDel
* @brief : 实现循环双向链表删除目标值
* @param
@head: 表示需要操作的链表
@dest: 表示要删除的目标值
* @retval : 删除成功返回true，否则返回false;
* @date : 2025-12-23
* @version 1.0 : v1.0
* @note : NULL
*/
bool DoubleCirLList_DestDel(DoubleCirLList_t *head,DataType_t dest)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list create memory failed for head\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("double circular linked list do not have Valid node\n");
return false;
}
//创建变量用于遍历目标值
DoubleCirLList_t *Dest_node = head->next;
//遍历链表找到目标节点
while(Dest_node != head){
if(Dest_node->data == dest){
Dest_node->next->prev = Dest_node->prev;
Dest_node->prev->next = Dest_node->next;
free(Dest_node);
Dest_node = NULL;
return true;
}
Dest_node = Dest_node->next;
}
printf("double circular linked list do not have dest value=%d\n",dest);
return false;
}
void DoubleCirLList_show(DoubleCirLList_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("double circular linked list do not exist\n");
return;
}
//创建变量用于遍历链表
DoubleCirLList_t *phead = head->next;
//遍历链表
while(phead != head){
printf("current node value = %d\n",phead->data);
phead = phead->next;
}
}
main.c
#include "doubleCircularlinkedlist.h"
int main(int argc,char * const argv[])
{
//创建变量存储链表地址
DoubleCirLList_t* head = DoubleCirLList_create();
//判断链表是否存在
if(NULL == head){
printf("double circular linked list create linked list failed\n");
return -1;
}
//头插
DoubleCirLList_HeadAdd(head,45);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//头部插入
DoubleCirLList_HeadAdd(head,75);
DoubleCirLList_HeadAdd(head,15);
DoubleCirLList_HeadAdd(head,94);
DoubleCirLList_HeadAdd(head,25);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//尾部插入
DoubleCirLList_TailAdd(head,90);
DoubleCirLList_TailAdd(head,88);
DoubleCirLList_TailAdd(head,86);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//目标值后面插入
DoubleCirLList_DestAdd(head,94,20);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//头删
DoubleCirLList_HeadDel(head);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//尾删
DoubleCirLList_TailDel(head);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
//目标删除
DoubleCirLList_DestDel(head,15);
DoubleCirLList_show(head);
printf("----------------------------------------\n");
DoubleCirLList_DestDel(head,9);
//遍历
DoubleCirLList_show(head);
printf("----------------------------------------\n");
return 0;
}
发表回复