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

初阶数据结构【双链表及其接口的实现】

article 2025/1/15 8:23:33

目录

  • 前言
  • 一、基本结构
  • 二、双链表的接口实现
    • 2.1 双链表基本功能接口
      • 2.1.1 双向链表打印
      • 2.1.2 申请一个节点
      • 2.1.3 创建并返回双向链表的头结点
      • 2.1.4 双向链表清理（不销毁）
      • 2.1.5 双向链表销毁
    • 2.2 双向链表增加节点接口
      • 2.2.1 双向链表头插
      • 2.2.2 双向链表尾插
      • 2.2.3 双向链表在pos的前面进行插入
      • 2.2.4 优化头插尾插
    • 2.3 双向链表删除节点接口
      • 2.3.1 双向链表的头删
      • 2.3.2 双向链表的尾删
      • 2.3.3 双向链表删除pos位置的结点
      • 2.3.4 优化头删尾删
    • 2.4 双向链表修改节点数据接口
    • 2.5 双向链表查找节点接口
  • 三、顺序表和链表的区别
  • 四、是否传二级指针的总结
  • 总结

前言

前面我们介绍了数据结构中的链表，并实现了我们在实际中最常用的两个链表之一——无头单向非循环链表，这期我们继续来用C语言实现第二个常用链表——带头双向循环链表；

一、基本结构

带头双向循环链表(简称双向链表)的结构
在这里插入图片描述

typedef struct ListNode
{
	struct ListNode* next; //指向下一个节点
	struct ListNode* prev; //指向上一个节点
	LTDataType data;
}ListNode;

二、双链表的接口实现

2.1 双链表基本功能接口

2.1.1 双向链表打印

我们为了验证双向链表的其他接口，我们需要实时打印双向链表，所以我们单独设计一个打印模块：

这里我们唯一要知道的是双向循环链表的空链表形式的prev和next都指向自己自身：
在这里插入图片描述

// 双向链表打印
void ListPrint(ListNode* plist) {
	assert(plist);
	ListNode* cur = plist->next;
	if (cur == plist)
		printf("空链表");
	while (cur != plist)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.1.2 申请一个节点

当我们需要对双链表进行增加一个节点，我们就要利用malloc来申请一个节点的空间，为了提高代码的复用性，我们将这部分代码封装成函数：

//申请一个节点
ListNode* BuyListNode(LTDataType x) {
	ListNode* newNode = malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}

2.1.3 创建并返回双向链表的头结点

我们根据前面的申请节点接口可以很容易写出创建双向链表的接口（初始双向链表为空）:

// 创建返回链表的头结点.
void ListCreate(ListNode** pplist) {
	*pplist = BuyListNode(0);
	(*pplist)->next = *pplist;
	(*pplist)->prev = *pplist;
}

2.1.4 双向链表清理（不销毁）

当我们不想要这个双向链表的值，但是接下来还要使用这个双向链表，需要对双向链表执行一个清理的操作：

这里我们简单讲解一下使用的思想，由于我们free掉一个节点我们就无法再通过这个节点的next来寻找下个节点，所以我们这里实现这个操作需要两个节点来实现；

// 双向链表清理但不销毁,保留头结点可以继续使用
void ListClear(ListNode* plist){
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		ListNode* next = cur->next; //记录下一个节点的地址
		free(cur);  //释放目标节点
		cur = next; //指向下一个节点
	}
	plist->next = plist;
	plist->prev = plist;
}

2.1.5 双向链表销毁

我们先将头节点之后的节点进行释放，最后将头结点释放，第一步我们可以复用双向链表的清理：

// 双向链表销毁,利用二级指针，将plist置为空，防止野指针
void ListDestory(ListNode** plist) {
	assert(*plist);

	/*ListNode* cur = plist;
	while (cur != plist)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}*/
	ListClear(*plist);
	free(*plist);
	*plist = NULL;
}

2.2 双向链表增加节点接口

2.2.1 双向链表头插

双向链表比较于单向链表的头插简单的多，我们简单画图理解：

我们先申请一个节点cur，记录插入后目标节点的后面一个节点curNext，进行头插：
在这里插入图片描述

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
	assert(plist);

	//创建新节点
	ListNode* cur = BuyListNode(x);
	//找到插入后的下一个节点
	ListNode* curNext = plist->next;

	//解决头指针与新节点的链接
	plist->next = cur;
	cur->prev = plist;

	//解决下一个节点与新节点的链接
	curNext->prev = cur;
	cur->next = curNext;
}

2.2.2 双向链表尾插

与上面的头插一样，我们需要先申请一个节点newNode，找到双向链表的尾tail，再将其插入双向链表尾部：
在这里插入图片描述

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	//防止plist为空
	assert(plist);
	ListNode* tail = plist->prev;
	ListNode* newNode = BuyListNode(x);//申请一个节点

	//链接
	tail->next = newNode;
	newNode->prev = tail;

	newNode->next = plist;
	plist->prev = newNode;
}

2.2.3 双向链表在pos的前面进行插入

我们通过上面的头插和尾插已经有了一定的经验，我们想要插入一个节点，我们需要知道插入节点的前后两个节点的地址，我们想要在pos前插入节点，我们要知道插入节点前pos的prev，想到这，我们实现pos前面插入就不难了：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
	assert(pos);
	//申请新的节点
	ListNode* cur = BuyListNode(x);
	ListNode* curPrev = pos->prev;

	//解决cur与前面的节点的链接
	curPrev->next = cur;
	cur->prev = curPrev;

	//解决cur与后面的节点的链接
	cur->next = pos;
	pos->prev = cur;
}

若想实现在pos后插入也是同理的，这里就不多赘述了；

2.2.4 优化头插尾插

到这我相信大家发现了这三种插入其实是一个插入：
头插可以写成：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
	assert(plist);

	创建新节点
	//ListNode* cur = BuyListNode(x);
	找到插入后的下一个节点
	//ListNode* curNext = plist->next;

	解决头指针与新节点的链接
	//plist->next = cur;
	//cur->prev = plist;

	解决下一个节点与新节点的链接
	//curNext->prev = cur;
	//cur->next = curNext;

	ListInsert(plist->next, x);
}

同理，尾插可以写成：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	//防止plist为空
	assert(plist);

	//ListNode* tail = plist->prev;
	//
	//ListNode* newNode = BuyListNode(x);

	链接
	//tail->next = newNode;
	//newNode->prev = tail;

	//newNode->next = plist;
	//plist->prev = newNode;
	ListInsert(plist, x);
}

2.3 双向链表删除节点接口

2.3.1 双向链表的头删

我们要讲目标节点的上一个节点和下一个节点链接起来即可，我们需要注意的是，删除的节点我们最后要free掉：
在这里插入图片描述

// 双向链表头删
void ListPopFront(ListNode* plist) {
	assert(plist);
	assert(plist != plist->next);//防止对空链表删除，free了头指针

	//指向被删节点
	ListNode* cur = plist->next;
	//被删节点的下个节点
	ListNode* curNext = cur->next;

	//取消头结点与第一个节点链接
	plist->next = curNext;
	curNext->prev = plist;

	//释放空间
	free(cur);
	cur = NULL;
}

2.3.2 双向链表的尾删

理解了上面的头删，我们很容易写出尾删：
这里很多人会这样写：

 //双向链表尾删
void ListPopBack(ListNode* plist) {
	assert(plist);

	//找到尾节点
	ListNode* tail = plist->prev;
	//改变头指针的prev
	plist->prev = tail->prev;

	//改变尾指针上一个节点的next
	tail->prev->next = plist;

	free(tail);
    tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

这样写本身没有什么错误，但是不利于代码的可读性，所以我们一般这样来写：

//上面的代码不利于可读性，我们可以这样写
void ListPopBack(ListNode* plist) {
	assert(plist);
	
	assert(plist->next != plist);//防止对空链表进行删除
	
	ListNode* tail = plist->prev;
	ListNode* tailPrev = tail->prev; //需要删除节点的上一个节点

	tailPrev->next = plist; 
	plist->prev = tailPrev;

	free(tail);
	tail = NULL;//防止野指针，函数内部局部变量，不置空也可以
}

2.3.3 双向链表删除pos位置的结点

// 双向链表删除pos位置的结点
void ListErase(ListNode* pos) {
	assert(pos);
	/*assert(pos != plist);*/

	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;

	free(pos);
	pos = NULL;
}

2.3.4 优化头删尾删

与插入一样我们同样可以使用ListErase一个接口来实现这里所有的删除：

双链表的头删：

void ListPopFront(ListNode* plist) {
	assert(plist);
	assert(plist != plist->next);//防止对空链表删除，free了头指针

	指向被删节点
	//ListNode* cur = plist->next;
	被删节点的下个节点
	//ListNode* curNext = cur->next;

	取消头结点与第一个节点链接
	//plist->next = curNext;
	//curNext->prev = plist;

	释放空间
	//free(cur);
	//cur = NULL;

	ListErase(plist->next);
}

双链表的尾删：

void ListPopBack(ListNode* plist) {
	assert(plist);
	
	assert(plist->next != plist);//防止对空链表进行删除
	
	//ListNode* tail = plist->prev;
	//ListNode* tailPrev = tail->prev;

	//tailPrev->next = plist;
	//plist->prev = tailPrev;

	//free(tail);
	//tail = NULL;//防止野指针，函数内部局部变量，不置空也可以

	ListErase(plist->prev);
}

2.4 双向链表修改节点数据接口

通过节点的地址来将所指节点的数据进行修改：

//双向链表修改数据接口
void ListUpData(ListNode* pos, LTDataType x){
	assert(pos);
	pos->data = x;
}

pos节点一般由下面的查找节点接口实现。

2.5 双向链表查找节点接口

通过数据查找节点，如果找到节点我们就返回这个节点的地址，反之，返回空：

// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x) {
	assert(plist);

	ListNode* cur = plist->next;
	while(cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	//没找到

	return NULL;
}

三、顺序表和链表的区别

到目前为止我们已经用C语言实现了顺序表和链表的部分接口，我们也已经知道两者部分的优缺点，我们今天做一个总结：

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持 O(1)不支持：O(N)
任意位置插入或删除元素可能需要搬移元素，效率低 O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

要想了解的更详细可以去看看<<深入理解计算机系统>>

四、是否传二级指针的总结

通过我们对顺序表和链表的实现接口的过程中我们有时候需要改变其头指针的值，如对无头单链表进行头插：

在这里插入图片描述
这样由于头指针发生了改变，所以我们要传二级指针来修改这个指针的值，这样我们就不难理解为什么要创造出带哨兵位的链表了；

总结

这期我们利用C语言实现了带头双向循环链表的接口，我们充分体会到了链表对于顺序表的优点.我们下期继续，谢谢观看；
26考研一战成硕！


http://www.kler.cn/a/503345.html

相关文章：

  • G1原理—7.G1的GC日志分析解读
  • 73.矩阵置零 python
  • 非PHP开源内容管理系统（CMS）一览
  • 2_CSS3 背景 --[CSS3 进阶之路]
  • Mysql--运维篇--空间管理（表空间，索引空间，临时表空间，二进制日志，数据归档等）
  • 微信小程序mp3音频播放组件，仅需传入url即可
  • 安装MySQL在Linux环境下
  • 深入解析Alertmanager启动命令行参数及其作用
  • zookeeper-配置
  • [Git] 深入理解 Git 的客户端与服务器角色
  • 通信网络安全分层及关键技术解决
  • 深圳观澜森林公园及五指耙森林公园边坡自动化监测
  • C# HslCommunication库
  • java 组合框
  • Flutter（Dart）的集合类型List、Set 和 Map
  • open3d+opencv实现矩形框裁剪点云操作（C++）
  • 【动态规划-矩阵】5.下降路径最小和
  • 蓝牙的UUID（Universally Unique Identifier，通用唯一识别码）
  • 探索深度学习：开启智能新时代
  • 信号量机制之苹果-橘子问题
  • 【汇编】x86汇编编程寄存器资源心中有数
  • vulnhub靶场【IA系列】之Tornado
  • 地瓜机器人RDK Studio使用入门教程
  • 《自动驾驶与机器人中的SLAM技术》ch10：自动驾驶车辆的实时定位系统
  • 解决 vxe-table 的下拉框、日期选择等组件被 element-plus element-ui 弹窗遮挡问题 z-index
  • es 3期 第23节-运用Pipeline实现二转聚合统计