双向链表的定义与基本操作

双向链表操作实现

双向链表

双向链表（Doubly Linked List）是一种链式数据结构，其中的每个节点不仅指向下一个节点，还指向前一个节点。这与单向链表不同，后者每个节点只包含到下一个节点的引用。双向链表因此允许在两个方向上遍历：向前和向后。

每个节点在双向链表中通常包含三部分：

  1. 指向前一个节点的引用（或指针）。
  2. 存储的数据元素。
  3. 指向下一个节点的引用（或指针）。

双向链表的优点包括：

  • 可以从任意一个节点出发，既能够向前访问也能够向后访问，增加了灵活性。
  • 在已知节点位置的情况下，插入和删除操作可以高效地进行，因为只需要改变相应节点的前驱和后继的指针即可。

缺点是由于每个节点需要额外存储指向前一个节点的指针，因此相比单向链表会占用更多的内存空间。

代码实现

双向链表的创建、插入、删除、查找等常用操作。

#include <stdio.h>	// 标准输入输出库，用于 printf 等函数
#include <stdbool.h>	// 布尔类型库，提供 bool、true、false
#include <stdlib.h>	// 标准库，提供 malloc/calloc/free 和 exit 等函数
//定义链表中数据域的类型为 int
typedef int DataType_t; 
//定义双向链表的结点结构体
typedef struct DoubleLinkedList
{
	DataType_t 	 data; //结点的数据域
	struct DoubleLinkedList	*prev; //直接前驱的指针域
	struct DoubleLinkedList	*next; //直接后继的指针域
}DoubleLList_t;
//创建头结点：初始化一个空的双向链表
DoubleLList_t* DoubleLList_Create(void)
{
 // 为头结点动态分配内存，并初始化为 0（calloc 会清零）
	DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	 // 如果内存分配失败，打印错误信息并退出程序
 if(Head == NULL){
	perror("Calloc memory for the Head is failed!\n");
	exit(-1);
	}
	Head->next = NULL;
	Head->prev = NULL;
	return Head;
}
//创建一个新结点（仅数据域赋值，指针域初始化为 NULL）
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;
}
// 头插法：在链表头部（第一个有效结点位置）插入新元素
bool DbleLList_HeadInsert(DoubleLList_t* Head,DataType_t data)
{
 // 创建新结点
	DoubleLList_t *New = DoubleLList_NewNode(data);
 	if (New == NULL){
 return false; 
 	}
 // 若为空，新结点直接作为第一个有效结点
	if(Head->next == NULL){
	Head->next = New;
	}
	else{// 否则，将新结点插入到首结点之前
	New->next = Head->next;
	Head->next->prev = New;
	Head->next = New;
	}
	return true;// 插入成功
}
// 尾插法：在链表尾部插入新元素
bool DbleLList_TailInsert(DoubleLList_t* Head,DataType_t data)
{
	DoubleLList_t *New = DoubleLList_NewNode(data);
 if (New == NULL) {
 return false; 
 }
 //如果只有头结点，New直接成为首结点
	if(Head->next == NULL){//如果只有头结点，New直接成为首结点
	Head->next = New;
	}
	else{// 否则，从首结点开始遍历，寻找最后一个结点
	DoubleLList_t *Find_Tail = Head->next;
	while(Find_Tail->next != NULL){
	Find_Tail = Find_Tail->next;
	}
 // 找到尾结点后，将新结点连接在其后
	Find_Tail->next = New;
	New->prev = Find_Tail;	
	}
	return true;
}
//指定在链表中某个结点后插入一个新结点
bool DbleLList_DestInsert_l(DoubleLList_t* Head,DataType_t dest,DataType_t data)
{
	DoubleLList_t *New = DoubleLList_NewNode(data);
 	if (New == NULL) {
 return false; 
 	}
	if(Head->next == NULL){//如果只有头结点，New直接成为首结点
	Head->next = New;
	}
	DoubleLList_t *Find_Dest = Head->next;
	//遍历链表，找到数据域data等于目标值dest的结点
	while(Find_Dest->data != dest){	
	if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
	
	printf("无效指定结点位置\n");
	return false;
	}
	Find_Dest = Find_Dest->next;
	}
	if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，数据域data等于dest，新结点New成为尾结点
	
	Find_Dest->next = New;
	New->prev = Find_Dest;
	}
	else{
	New->next = Find_Dest->next;
	Find_Dest->next->prev = New;
	New->prev = Find_Dest;
	Find_Dest->next = New;
	}
	return true;
}
//指定在链表中某个结点前插入一个新结点
bool DbleLList_DestInsert_f(DoubleLList_t *Head,DataType_t dest,DataType_t data)
{
	DoubleLList_t *New = DoubleLList_NewNode(data);
 	if (New == NULL) {
 return false; 
 	}
	if(Head->next == NULL){//如果只有头结点，New直接成为首结点
	Head->next = New;
	}
	DoubleLList_t *Find_Dest = Head->next;
	//遍历链表，找到数据域data等于目标值dest的结点
	while(Find_Dest->data != dest){	
	if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
	
	printf("无效指定结点位置\n");
	return false;
	}
	Find_Dest = Find_Dest->next;
	}
	//1.首结点是目标结点
	if(Find_Dest == Head->next){
	New->next = Head->next;
	Head->next->prev = New;
	Head->next = New;	
	}
	else{
	New->prev = Find_Dest->prev;
	Find_Dest->prev->next =New;
	New->next = Find_Dest;
	Find_Dest->prev = New;
	}
	return true;
}
//遍历链表并输出所有结点的data值
bool DbleLList_Print(DoubleLList_t *Head)
{
	DoubleLList_t *Phead = Head;
	if(Head->next == NULL){
	printf("current DoubleLList is empty!\n");
	return false;
	}
	printf("链表内容: ");
	while(Phead->next){
	Phead = Phead->next;
	printf("%d ",Phead->data);
	if(Phead->next == NULL){	
	break;
	}
	}
	printf("\n");
	return true;
}
//删除链表头结点
bool DbleLList_HeadDel(DoubleLList_t *Head)
{
	DoubleLList_t *Temp = Head->next;
	//if链表只有一个头结点
	if(Head->next == NULL){
	printf("current DoubleLList is empty!\n");
	return false;
	}
	//if当前链表只有一个首结点
	if(Temp->next == NULL){
	Head->next = NULL;
	free(Temp);
	return true;
	}
	//新的首结点pre指向NULL不指向Head
	Temp->next->prev = NULL;
	//头结点next指向要删除结点的next
	Head->next = Temp->next;
	
	free(Temp);
	return true;
}
//指定位置删除链表结点
bool DbleLList_del_dest(DoubleLList_t* Head,DataType_t dest)
{	
	if(Head->next == Head){
	printf("current DoubleLList is empty!\n");
	return false;
	}
	DoubleLList_t *Find_Dest = Head->next;
	while(Find_Dest->data != dest){	
	if (Find_Dest->next == NULL){//若遍历到链表最后一个结点
	printf("未找到指定节点\n");
	return false;
	}
	Find_Dest = Find_Dest->next;
	}
	if (Head->next == Find_Dest){//若目标结点是链表第一个结点
	if(Find_Dest->next = NULL){//若目标结点还是是链表唯一结点
	Head->next = NULL;
	}
	else{
	Find_Dest->next->prev = NULL;
	Head->next = Find_Dest->next;
	}
	}
	else{//若目标结点是链表最后一个结点
	if(Find_Dest->next == NULL){
	Find_Dest->prev->next = NULL;
	}
	else{//若目标结点有前驱后继
	Find_Dest->prev->next = Find_Dest->next;
	Find_Dest->next->prev = Find_Dest->prev;
	}
	}
	free(Find_Dest);
	return true;
}

主函数测试

int main(int argc, char const *argv[])
{
 // 创建双向链表
 DoubleLList_t *Head = DoubleLList_Create();
 printf("1. 创建双向链表完成\n");
 DbleLList_Print(Head);
 
 // 测试头插法
 printf("\n2. 测试头插法插入 10, 20, 30\n");
 DbleLList_HeadInsert(Head, 10);
 DbleLList_HeadInsert(Head, 20);
 DbleLList_HeadInsert(Head, 30);
 DbleLList_Print(Head); // 预期结果: 30 20 10
 
 // 测试尾插法
 printf("\n3. 测试尾插法插入 40, 50\n");
 DbleLList_TailInsert(Head, 40);
 DbleLList_TailInsert(Head, 50);
 DbleLList_Print(Head); // 预期结果: 30 20 10 40 50
 
 // 测试指定节点后插入
 printf("\n4. 测试在20后插入25\n");
 DbleLList_DestInsert_l(Head, 20, 25);
 DbleLList_Print(Head); // 预期结果: 30 20 25 10 40 50
 
 // 测试指定节点前插入
 printf("\n5. 测试在40前插入35\n");
 DbleLList_DestInsert_f(Head, 40, 35);
 DbleLList_Print(Head); // 预期结果: 30 20 25 10 35 40 50
 
 // 测试删除头节点
 printf("\n6. 测试删除头节点\n");
 DbleLList_HeadDel(Head);
 DbleLList_Print(Head); // 预期结果: 20 25 10 35 40 50
 
 // 测试删除指定节点
 printf("\n7. 测试删除节点10\n");
 DbleLList_del_dest(Head, 10);
 DbleLList_Print(Head); // 预期结果: 20 25 35 40 50
 
 // 测试删除尾节点
 printf("\n8. 测试删除尾节点(50)\n");
 DbleLList_del_dest(Head, 50);
 DbleLList_Print(Head); // 预期结果: 20 25 35 40
 
 // 测试删除中间节点
 printf("\n9. 测试删除中间节点(25)\n");
 DbleLList_del_dest(Head, 25);
 DbleLList_Print(Head); // 预期结果: 20 35 40
 
 // 测试删除所有节点
 printf("\n10. 测试删除所有节点\n");
 DbleLList_HeadDel(Head);
 DbleLList_HeadDel(Head);
 DbleLList_HeadDel(Head);
 DbleLList_Print(Head); // 预期结果: 空链表
 
 // 释放头节点
 free(Head);
 Head = NULL;
 printf("\n11. 释放链表完成\n");
 
 return 0;
}

测试结果

作者:Yue+原文地址:https://www.cnblogs.com/YueZone/p/19021456
0
分享 2025-08-04

%s 个评论

要回复文章请先登录或注册

关于我们 • 赞助与捐赠 • 站点地图 • 联系我们 • 网站合作 • 免责声明
友情链接： 乐读文化 • 开发者 • MySQL Workbench • 大牛教程 • 微信聊天模拟器 • 交换链接
本站为个人网站，部分内容来自于互联网，版权归原作者所有。如本站内容有侵权，敬请来信联系我们，我们将及时删除清理。
© 2026 大牛教程