当前位置： 首页 > news >正文

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

news 2025/10/15 1:03:34

双向链表操作实现

双向链表

双向链表（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不指向HeadTemp->next->prev = NULL;//头结点next指向要删除结点的nextHead->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;
}

测试结果

vmware_aquEagpzNv

http://www.sczhlp.com/news/5241/

相关文章：

  • 开源驱动下的能源管理革新：安全自主可控与 MyEMS 的实践路径
  • 一个简单的nginx日志切割shell脚本
  • CF1385D a-Good String
  • Docker 替换宿主与容器的映射端口和文件路径
  • Origin2022如何绘制一个2D饼图？
  • SharePoint漏洞被利用传播勒索软件
  • MySQL 高级(进阶) SQL 语句
  • Integer缓存IntegerCache详解
  • 普科科技电流互感器在电力系统继电保护领域替代皮尔逊电流互感器的测试案例
  • 隐藏滚动条但不影响使用 - Joshua
  • 【ARM Cache 及 MMU 系列文章 6 -- Cache 寄存器 CTR_EL0 CLIDR CCSIDR CSSELR 使用详解 1】
  • GitLab项目导入远程代码执行漏洞分析(CVE-2022-2185)
  • 自用思源笔记CSS配色记录
  • 定期删除全量和增量备份
  • JUC学习-23-线程池拒绝策略
  • RS485硬件电路设计参考：工业数据交互的基石
  • Kubernetes v1.33：HPA 可配置容差
  • Java学习：Java与C++数组初始化全对比
  • Revit高版本载入低版本族库，软件卡死 - Andy
  • ​​Linux CentOS 命名空间（Namespace）​​ 的应用场景及命令详解
  • 洛谷P1364 医院设置（dfs\树形dp\树重心）
  • Modbus转Profinet协议网关与微型空气质量监测系统
  • VLAN 0 1 4095
  • [CTF Reverse] 初见SMC
  • 深入指南：在SCSS中高效使用@font-face引入自定义字体
  • 题解：qoj9564 Hey, Have You Seen My Kangaroo?
  • BT137-800-ASEMI工业自动化BT137-800
  • 8.4
  • Java数组
  • appium安装文档