数据结构-双向链表
函数功能实现
/**************************************************************************** * @name* @author* @date** *CopyRight (c) 2025-2026 All Right Reserved* *************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;//构造双向链表的节点,链表中所有节点的数据类型应该是相同的
typedef struct DoubleLinkedList
{DataType_t data; //节点的数据域struct DoubleLinkedList *prev; //直接前驱的指针域struct DoubleLinkedList *next; //直接后继的指针域}DoubleLList_t;/**************************************************************************** * @name DoubleLList_Create* @brief 创建一个空双向链表，空链表应该有一个头节点，对链表进行初始化* @param NULL* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
DoubleLList_t * DoubleLList_Create(void)
{//1.创建一个头节点并对头节点申请内存DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));if (NULL == Head){perror("Calloc memory for Head is Failed");exit(-1);}//2.对头节点进行初始化，头节点是不存储数据域，指针域指向NULLHead->prev = NULL;Head->next = NULL;//3.把头节点的地址返回即可return Head;
}/**************************************************************************** * @name DoubleLList_NewNode* @brief 创建新的节点，并对新节点进行初始化（数据域 + 指针域）* @param DataType_t data:数据域* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
DoubleLList_t * DoubleLList_NewNode(DataType_t data)
{//1.创建一个新节点并对新节点申请内存DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));if (NULL == New){perror("Calloc memory for NewNode is Failed");return NULL;}//2.对新节点的数据域和指针域（2个）进行初始化New->data = data;New->prev = NULL;New->next = NULL;return New;
}/**************************************************************************** * @name DoubleLList_HeadInsert* @brief 头节点后插入节点* @param DoubleLList_t *Head:头节点* DataType_t Data:数据域* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_HeadInsert(DoubleLList_t *Head , DataType_t Data)
{DoubleLList_t *New = DoubleLList_NewNode(Data);//判断是否创建成功if (NULL == New){return false;}//如果为空链表，将头节点的Next指向新创建的节点 if (NULL == Head->next){Head->next = New; //头节点的next指向NewNew->prev = Head; //新节点的prev指向头节点return true;}Head->next->prev = New; //首节点的prev指向 New节点New->prev = Head; //New节点的prev指向 Head节点New->next = Head->next; //New节点的next指向 首节点Head->next = New; //头节点的next指向 New节点return true;
}/**************************************************************************** * @name DoubleLList_TailInsert* @brief 尾节点后插入节点* @param DoubleLList_t *Head:头节点* DataType_t Data:数据域* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_TailInsert(DoubleLList_t *Head , DataType_t Data)
{DoubleLList_t *New = DoubleLList_NewNode(Data);//判断是否创建成功if (NULL == New){return false;}//如果为空链表，将头节点的Next指向新创建的节点 if (NULL == Head->next){Head->next = New; //头节点的next指向NewNew->prev = Head; //新节点的prev指向头节点return true;}DoubleLList_t *PHead = Head; //将头节点地址赋值给p指针while (PHead->next != NULL){PHead = PHead->next;}PHead->next = New; //尾节点的next指向 New节点New->prev = PHead; //New节点的prev指向 尾节点return true;}/**************************************************************************** * @name DoubleLList_DestInsert* @brief 指定位置后插入节点* @param DoubleLList_t *Head:头节点* DataType_t Data:数据域* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_DestInsert(DoubleLList_t *Head , DataType_t Dest , DataType_t Data)
{DoubleLList_t *New = DoubleLList_NewNode(Data);//判断是否创建成功if (NULL == New){return false;}//如果为空链表，将头节点的Next指向新创建的节点 if (NULL == Head->next){Head->next = New; //头节点的next指向NewNew->prev = Head; //新节点的prev指向头节点return true;}//非空，遍历DoubleLList_t *PHead = Head; //将头节点地址赋值给p指针while (PHead->next){PHead = PHead->next;if (PHead->data == Dest){break;}}//遍历没有目标节点,退出if (PHead->next == NULL && PHead->data != Dest){printf("dest node is not found\n");return false;}//如果有，分为尾，中间if (PHead->next == NULL) //尾插 {New->prev = PHead;PHead->next = New;}else //中间{New->next = PHead->next;//新节点的next指向 目标节点的直接后继New->prev = PHead;//新节点的prev指向 目标节点PHead->next->prev = New;//目标节点的直接后继的prev 指向新节点PHead->next = New;//目标节点的next指向 新节点}return true;
}/**************************************************************************** * @name DoubleLList_HeadDel* @brief 删除首节点* @param DoubleLList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_HeadDel(DoubleLList_t *Head)
{//判断是否为空链表if (NULL == Head->next){printf("dest node is not found\n");return false;}DoubleLList_t *PHead = Head->next;PHead->next->prev = Head; //当前节点直接后继的prev指向 HeadPHead->prev = NULL; //当前节点的prev指向 NULLHead->next = PHead->next; //头节点的next指向 当前节点直接后继PHead->next = NULL; //当前节点next指向 NULLfree(PHead);return true;
}/**************************************************************************** * @name DoubleLList_TailDel* @brief 删除尾节点* @param DoubleLList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_TailDel(DoubleLList_t *Head)
{//判断是否为空链表if (NULL == Head->next){printf("dest node is not found\n");return false;}DoubleLList_t *PHead = Head; //将头节点地址赋值给p指针while (PHead->next){if (PHead->next == NULL){break;} PHead = PHead->next;}PHead->prev->next = NULL;PHead->prev = NULL;PHead->next = NULL;free(PHead);return true;
}/**************************************************************************** * @name DoubleLList_DestDel* @brief 删除指定节点* @param DoubleLList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_DestDel(DoubleLList_t *Head, DataType_t Dest)
{//判断是否为空链表if (NULL == Head->next){ printf("dest node is not found\n");return false;}//非空DoubleLList_t *PHead = Head; //将头节点地址赋值给p指针while (PHead->next){PHead = PHead->next;if (PHead->data = Dest){break;}}//如果没有目标节点，退出if (PHead->next == NULL && PHead->data != Dest){printf("dest node is not found\n");return false;}//如果有，位置可能为头、尾、中if (PHead == Head->next) //头{Head->next = PHead->next;//判断是否只有首节点if (PHead->next != NULL){PHead->next->prev = NULL;PHead->next = NULL;}free(PHead); //释放节点}else if (PHead->next == NULL) //尾 {PHead->prev->next = NULL; //尾节点的直接前驱的next指向 NULLPHead->prev = NULL; //尾节点的prev 指向 NULLfree(PHead); //释放节点}else{PHead->prev->next = PHead->next; //待删除节点直接前驱的next 指向待删除节点的直接后继PHead->next->prev = PHead->prev; //待删除节点直接后继的prev 指向待删除节点的直接前驱PHead->next = NULL; //待删除节点的next 指向 NULLPHead->prev = NULL; //待删除节点的prev 指向 NULLfree(PHead); //释放节点}return true;
}/**************************************************************************** * @name DoubleLList_Print* @brief 遍历* @param DoubleLList_t *Head:头节点* * @retval ** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
void DoubleLList_Print(DoubleLList_t *Head)
{DoubleLList_t *PHead = Head; //打印整个链表while (PHead->next != NULL){PHead = PHead->next;printf("Data=%d\n",PHead->data);}
}
主函数
int main(int argc, char const *argv[])
{DoubleLList_t *DoubleLList = DoubleLList_Create(); //初始化DoubleLList_HeadInsert(DoubleLList,20); //头添20DoubleLList_HeadInsert(DoubleLList,10); //头添10DoubleLList_HeadInsert(DoubleLList,5); //头添5DoubleLList_HeadInsert(DoubleLList,0); //头添0DoubleLList_TailInsert(DoubleLList,25); //尾添25DoubleLList_DestInsert(DoubleLList,10,15); //10后添15DoubleLList_Print(DoubleLList); //0,5,10，15，20，25printf("\n");DoubleLList_HeadDel(DoubleLList); //删0DoubleLList_Print(DoubleLList); //5,10，15，20，25printf("\n");DoubleLList_TailDel(DoubleLList); //删25DoubleLList_Print(DoubleLList); //5,10，15，20printf("\n");DoubleLList_DestDel(DoubleLList,5); //删5DoubleLList_Print(DoubleLList); //10，15，20printf("\n"); return 0;
}
