【数据结构】单链表和双链表

文章目录

  • 一、链表的概念及结构
  • 二、链表的分类
  • 三、无头单向非循环链表
    • 1.单链表创建
    • 2.尾插和头插
    • 3.尾删和头删
    • 4.打印
    • 5.查找
    • 6.插入
    • 7.删除
    • 8.销毁
  • 四、带头双向循环链表
    • 1.双链表的创建
    • 2.初始化
    • 3.判断链表是否为空
    • 4.尾插和头插
    • 5.尾删和头删
    • 6.查找
    • 7.插入
    • 8.删除
    • 9.销毁
  • 五、总结
    • 链表和顺序表的对比

一、链表的概念及结构

通过上篇顺序表我们了解到顺序表是一种顺序存储结构,顺序存储结构是用一段物理地址连续的存储单元依次存储数据元素的线性结构,我们一般采用数组来存储。

而本篇我们介绍的链表是链式存储的结构,链式存储结构的特点是:数据的物理地址是非连续的,可以在内存中的任意位置。也就是说逻辑上相邻的数据元素在空间上不一定连续。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

在这里插入图片描述
因为链表的每个结点是从堆上动态申请的,每次申请的空间是随机的,所以物理地址不一定是连续的。

二、链表的分类

1.带哨兵位头结点或不带头结点

在这里插入图片描述

2.单向或双向

在这里插入图片描述
3.非循环或循环
在这里插入图片描述

一共有2^3 = 8种链表结构。
八种结构中,我们经常用到的只有两种结构:无头单向非循环链表和带头双向循环链表。
接下来我们就主要介绍这两种链表结构。掌握了这两种结构,其他几种也可以自己写出来了。
下面的内容涉及到结构体和指针等相关知识,忘了的小伙伴可以复习一下前面的知识。
传送门:结构体篇,指针篇,动态内存管理

三、无头单向非循环链表

我们所说的单链表通常是指无头单向非循环链表
在这里插入图片描述单链表的定义

typedef int DataType;//int可以换成char、double或者其他结构体类型
typedef struct SingleListNode
{
	DataType data;//存储数据元素
	struct SingleListNode* next;//存储下一个结点的地址
}SLNode;

1.单链表创建

//动态申请一个节点
SLNode* BuySLNode(DataType x)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (NULL == newNode)
	{
		perror("malloc");
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

注意,单链表是不需要单独初始化的,因为我们每增加一个数据结点,都会动态申请一个空间,在申请的同时会初始化该结点,所以封装成一个函数,方便调用。

2.尾插和头插

现在介绍的是不带哨兵位头结点的单链表,后面的pphead都是单链表头结点地址,这里的头结点不是指哨兵位头结点,而是指链表的第一个结点,表头的位置,二者是不一样的,具体会在后面介绍双链表时细说。

单链表尾插是将新申请的结点链接到尾结点的后面,但不能直接访问链表的尾结点,因此需要从头结点开始遍历链表到尾结点,然后链接新节点。
在这里插入图片描述尾插分为两种情况:1.链表为空;2.链表非空

//尾插
void SLNodePushBack(SLNode** pphead, DataType x)
{
	assert(pphead);//防止传错成空指针NULL 
	//*pphead无需assert断言,链表可以为空
	SLNode* newNode = BuySLNode(x);
	if (NULL == *pphead)//空链表情况
	{
		*pphead = newNode;
	}
	else
	{
		//从第一个结点开始遍历到尾节点
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//在尾结点后面插入新结点
		tail->next = newNode;
	}
}

注意:链表在传入头结点(第一个结点)时,由于头结点是一个结构体指针类型,函数体中会修改头结点,所以要用二级指针来接收,否则形参的改变不会影响实参。

链表头插是在新结点的后面链接头结点,然后更新头结点。
在这里插入图片描述

//头插
void SLNodePushFront(SLNode** pphead, DataType x)
{
	assert(pphead);//防止传错成空指针NULL 
	//空链表可以头插,*pphead无需assert断言
	SLNode* newNode = BuySLNode(x);
	newNode->next = *pphead;//头结点为空也适用
	*pphead = newNode;//头插后更新头结点为第一个的结点
}

总结:

插入不需要assert断言链表是否为空,因为空链表也可以进行插入操作,只需断言传入的参数是否为空,因为要对pphead解引用,NULL不能解引用。

3.尾删和头删

尾删需要两个指针,prev用来指向尾结点的前一个结点,tail用来指向尾结点。
在这里插入图片描述
尾删同样需要分两种情况处理:1.链表只有一个结点;2.链表有两个结点及以上

//尾删
void SLNodePopBack(SLNode** pphead)
{
	assert(pphead);//防止传错成空指针NULL 
	assert(*pphead);//空链表不可删除
	if (NULL == (*pphead)->next)//头结点下一个结点为空,则只有一个结点
	{
		free(*pphead);//删除结点释放空间
		*pphead = NULL;
	}
	else	//两个以上结点
	{
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)//找到尾结点的前一个结点
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

头删则不用考虑链表是否只有一个结点,只需要将头结点指向下一个结点即可。但是在改变头结点的指向之前要记得保存原来的头结点,是为了释放要删除的结点空间。
在这里插入图片描述

//头删
void SLNodePopFront(SLNode** pphead)
{
	assert(pphead);//防止传错成空指针NULL 
	assert(*pphead);//空链表不可删除
	SLNode* head = *pphead;//保存头结点 后续释放
	*pphead = head->next;//头结点指向第二个结点
	free(head);//释放刚刚保存的头结点
	head = NULL;//置空,防止野指针
}

总结:

1.删除操作需要保证链表不为空,所以pphead和*pphead都需要断言判断。
2.结点删除后,需要及时free释放,防止内存泄漏;并置空,防止野指针的形成。

4.打印

遍历一遍链表,将每个结点的data打印。这里以int类型示例。

//打印链表
void SLNodePrint(SLNode* phead)
{
	//空链表可以打印,无需assert断言
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//切忌cur++
	}
	printf("NULL\n");
}

5.查找

遍历链表,查找值为x的结点并返回该结点的指针

//查找
SLNode* SLNodeFind(SLNode* phead, DataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

6.插入

插入分为两种情况插入:

1.在pos位置之前插入
在这里插入图片描述

在pos位置之前插入,prev用来找到pos的前一个结点,在prev的后面尾插新结点即可。

//插入pos位置之前
void SLNodeInsert(SLNode** pphead, SLNode* pos, DataType x)
{
	assert(pphead);//防止传错成空指针NULL 
	assert(pos);//检查要插入的位置是否存在
	assert(*pphead);
	if (pos == *pphead)//在头结点之前插入相当于头插
	{
		SLNodePushFront(pphead, x);//头插
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)//找到pos位置的前一个结点
		{
			prev = prev->next;
		}
		SLNode* newNode = BuySLNode(x);
		prev->next = newNode;
		newNode->next = pos;
	}
}

2.在pos位置之后插入
在这里插入图片描述
这种情况不需要找到pos的前一个结点,直接在pos后面链接新结点。

//插入pos位置之后
void SLNodeInsertAfter(SLNode* pos, DataType x)
{
	assert(pos);
	SLNode* newNode = BuySLNode(x);
	//这两行顺序不能反,否则pos的下个结点会找不到
	newNode->next = pos->next;
	pos->next = newNode;
}

注意:因为没有用到头结点,所以头结点可以不用传参。因为只改变了pos结点的next的指向,pos结点本身的值并没有改变,所以不需要用二级指针接收。

总结:

1.在pos位置之前插入,则不能进行尾插;在pos位置之后插入,则不能进行头插。
2.插入时要对pos进行检查,pos不能为空。

7.删除

删除pos指针指向的结点

//删除pos位置的结点
void SLNodeErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);//防止传错成空指针NULL 
	assert(pos);//检查要插入的位置是否存在
	assert(*pphead);
	if (*pphead == pos)//头删
	{
		SLNodePopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL; pos是形参,改变对实参无影响;可以传二级指针,或者在外部置空
	}
}

注意:pos指向的结点free掉之后,为了防止野指针的形成,需要置空处理。 如果传参时pos用的一级指针接收,则需要在外部调用SLNodeErase函数后,自行置空;如果要在函数内部free的同时置空,则需要用二级指针接收pos的地址。按喜好自行选择任意一种即可。

8.销毁

//销毁链表
void SLNodeDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur != NULL)
	{
		SLNode* next = cur->next;//先保存下一个结点再销毁
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

链表使用完毕不要忘了释放空间。

至此,单链表的内容总结完毕。接下来介绍带头双向循环链表的实现。

四、带头双向循环链表

在这里插入图片描述1.“带头”是指带有哨兵位头结点,与前面单链表中的头结点(链表第一个结点)不一样,哨兵位头结点不存储数据,并且next指向链表的第一个结点。这种情况就不需要单独考虑头结点是否为空。代码也更容易写。
2.双向链表则比单向链表多一个prev指针,指向前一个结点。
3.循环链表中,尾结点的后驱结点指向头结点;双向循环链表中,头结点的前驱结点指向尾结点,尾结点的后驱结点指向头结点,整体构成一个环。

双链表的定义

typedef int DataType;
typedef struct DListNode
{
	DataType data;
	struct DListNode* prev;//存储前一个结点的地址
	struct DListNode* next;//存储后一个结点的地址
}DLNode;

1.双链表的创建

//申请结点
DLNode* BuyDLNode(DataType x)
{
	DLNode* newNode = (DLNode*)malloc(sizeof(DLNode));
	if (NULL == newNode)
	{
		perror("malloc");
		return NULL;
	}
	newNode->data = x;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
}

2.初始化

初始化将头结点的前驱结点和后驱结点都指向自身

//双链表初始化
DLNode* DLInit()
{
	DLNode* phead = BuyDLNode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

3.判断链表是否为空

链表为空的条件是:头结点的前驱结点和后驱结点都指向自身,判断一个就行。

bool DLEmpty(DLNode* phead)
{
	assert(phead);
	return phead->next == phead;//或者return phead->prev == phead;
}

4.尾插和头插

尾插的时要注意,先将新结点和尾结点链接起来,再将新结点和头结点链接起来,否则先链接头结点会找不到尾结点。但是如果先将尾结点保存起来,则不用按照顺序。
在这里插入图片描述

//尾插
void DLPushBack(DLNode* phead, DataType x)
{
	assert(phead);//phead不能为空,否则说明传错了
	DLNode* newNode = BuyDLNode(x);
	DLNode* tail = phead->prev;//一步找到尾结点
	
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

头插也是一样,如果先将第一个结点保存起来,则不需要注意链接顺序。
在这里插入图片描述

//头插
void DLPushFront(DLNode* phead, DataType x)
{
	assert(phead);
	DLNode* newNode = BuyDLNode(x);
	DLNode* newNode first = phead->next;//保存第一个结点

	first->prev = newNode;
	newNode->next = first;
	newNode->prev = phead;
	phead->next = newNode;
}

注意:带哨兵位头结点的链表,传参时不需要用二级指针接收,因为从始至终都不会改变头结点本身的值。

5.尾删和头删

在这里插入图片描述

//尾删
void DLPopBack(DLNode* phead)
{
	assert(phead);
	//链表非空才能删除
	assert(!DLEmpty(phead)); //或者写成assert(phead->next != phead);
	DLNode* tail = phead->prev;//保存尾结点
	DLNode* prev = tail->prev;//保存尾结点的前一个结点
	phead->prev = prev;
	prev->next = phead;
	free(tail);
	tail = NULL;
}

在这里插入图片描述

//头删
void DLPopFront(DLNode* phead)
{
	assert(phead);
	assert(!DLEmpty(phead));//链表为空不能删
	DLNode* first = phead->next;//保存第一个结点
	DLNode* next = first->next;//保存第一个结点的下一个结点
	phead->next = next;
	next->prev = phead;
	free(first);
	first = NULL;
}

6.查找

查找值为x的结点并返回指向该结点的指针

//查找
DLNode* DLFind(DLNode* phead, DataType x)
{
	assert(phead);
	DLNode* cur = phead->next;//cur指向第一个结点
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//找不到则返回空
}

注意:查找结束的条件是当前结点不等于头结点,相等说明进入下一轮循环。

7.插入

在pos之前插入新结点

//pos位置之前插入
void DLInsert(DLNode* pos, DataType x)
{
	assert(pos);
	DLNode* newNode = BuyDLNode(x);
	DLNode* prev = pos->prev;

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

实现该函数后,头插和尾插可以用一行代码解决:

DLInsert(phead->next, x);//头插:在头结点的下个结点(第一个结点)之前插入
DLInsert(phead, x);//尾插:在头结点的前面(尾结点的后面)插入

8.删除

//pos位置删除
void DLErase(DLNode* phead, DLNode* pos)
{
	assert(pos);
	assert(pos != phead);//不能删除头结点
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);//外部置空
}

同样,实现该函数后,头删和尾删可以用一行代码解决:

DLErase(phead, phead->next);//头删
DLErase(phead, phead->prev);//尾删

9.销毁

//链表销毁
void DLDestroy(DLNode* phead)
{
	assert(phead);
	DLNode* cur = phead->next;
	while (cur != phead)
	{
		DLNode* next = cur->next;//先保存待销毁结点的下一个结点
		free(cur);
		cur = NULL;
		cur = next;
	}
}

五、总结

1.通过本篇,掌握不带头单向非循环链表和带头双向循环链表之后,大概也能类推写出其他六种链表结构。
2.不带头的链表传参数需要二级指针来接收,因为函数中可能会改变头结点(第一个结点)的值,例如链表为空时的操作。带头的链表传参时只需一级指针接收即可,因为并不会改变头结点(哨兵位头结点)的值。
3.双向链表插入删除操作时,如果不事先保存结点的前后结点,则需要注意链接顺序,否则会找不到原来的结点。
4.在pos位置进行删除操作时,要么传入二级指针置空,要么在外部调用函数完自行置空,否则会形成野指针。
5.链表的头插尾插和头删尾删可以不用写,都可以用插入和删除函数实现。

完整代码放在gitee上:
单链表
双链表

链表和顺序表的对比

顺序表存储方式是顺序存储,即在内存中连续存储数据元素,通过下标来访问元素。

链表存储方式是链式存储,即数据元素在内存中不一定连续,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的优点:
1.任意位置插入和删除只需修改指针指向,效率很高,时间复杂度为O(1)。
2.需要一个结点就申请一个空间,空间利用率高。
链表的缺点:
不支持随机访问,对结点的操作需要从头指针开始遍历,效率低。

顺序表的优点:
可以根据下标随机访问任意位置的元素,效率为O(1),尾插尾删效率很高。
顺序表的缺点:
1.任意位置插入和删除需要移动元素位置,效率很低,时间复杂度为O(N)。
2.扩容有一定的消耗,可能会有一定空间的浪费。

可以发现,顺序表和链表的优缺点是互补的。对于数据元素较少,访问频繁,插入、删除情况较少的场景选择顺序表,对于数据元素较多,插入、删除操作频繁的场景选择链表。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/610613.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《窄门》安德烈·纪德

究竟会不会有这样一种爱情,即使毫无希望,一个人也可以将它长久地保持在心中;即使生活每天吹它,也始终无法把它吹灭……? 在《窄门》中,纪德将爱情中的神秘主义体验推向极致,为我们讲述了一段纯…

C语言(指针)3

Hi~!这里是奋斗的小羊,很荣幸各位能阅读我的文章,诚请评论指点,关注收藏,欢迎欢迎~~ 💥个人主页:小羊在奋斗 💥所属专栏:C语言 本系列文章为个人学习笔记&#x…

YOLOv9改进策略 | 添加注意力篇 | 利用YOLO-Face提出的SEAM注意力机制优化物体遮挡检测(附代码 + 修改教程)

一、本文介绍 本文给大家带来的改进机制是由YOLO-Face提出能够改善物体遮挡检测的注意力机制SEAM,SEAM(Spatially Enhanced Attention Module)注意力网络模块旨在补偿被遮挡面部的响应损失,通过增强未遮挡面部的响应来实现这一目…

链表第4/9题--翻转链表--双指针法

LeetCode206:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 输入:head [1,2,3,4,5] 输出:[5,4,3,2,1]示例 2: 输入:head [1,2] 输出:[2,1]示例…

鸿蒙OpenHarmony开发板解析:【特性配置规则】

特性 特性配置规则 下面介绍feature的声明、定义以及使用方法。 feature的声明 开发前请熟悉鸿蒙开发指导文档:gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 在部件的bundle.json文件中通过feature_list来声明部件的feature列…

生信技能45 - 基于docker容器运行生信软件

1. 获取docker镜像 以运行xhmm CNV分析软件为例。 # 搜索仓库镜像 sudo docker search xhmm# 拉取镜像 sudo docker pull ksarathbabu/xhmm_v1.0# 启动镜像,非后台 sudo docker run -it ksarathbabu/xhmm_v1.0 /bin/bash # -i: 交互式操作。 # -t: 终端。 # ksarathbabu/xhmm…

爆爽,英语小白怒刷 50 课!像玩游戏一样学习英语~

重点!!!(先看这) 清楚自己学英语的目的, 先搞清楚目标,再行动自身现在最需要的东西:词汇量?口语?还是阅读能力?找对应的书籍,学习资料往兴趣靠拢:网上有大量的推荐美剧学习、小说学习,不要被他…

机器学习算法应用——K近邻分类器(KNN)

K近邻分类器(KNN)(4-2) K近邻分类器(K-Nearest Neighbor,简称KNN)是一种基本的机器学习分类算法。它的工作原理是:在特征空间中,如果一个样本在特征空间中的K个最相邻的样…

【一刷《剑指Offer》】面试题 17:合并两个排序的链表

力扣对应题目链接:21. 合并两个有序链表 - 力扣(LeetCode) 核心考点:链表合并。 一、《剑指Offer》内容 二、分析题目 这道题的解题思路有很多: 可以一个一个节点的归并。可以采用递归完成。 三、代码 1、易于理解的…

Linux-基础命令第三天

1、命令:wc 作用:统计行数、单词数、字符数 格式:wc 选项 文件名 例: 统计文件中的行数、单词数、字符数 说明:59代表行数,111代表单词数,2713代表字符数,a.txt代表文件名 选项…

c语言查找字符串中指定字符串的个数

目录 一、测试思路二、方式1三、方式2 一、测试思路 使用C语言来查找一个字符串中指定数量的子字符串&#xff0c;使用 strncmp 函数或者 memcmp 函数&#xff0c;遍历主字符串并计数子字符串出现的次数。或者使用 strstr 函数&#xff0c; strstr 函数是 C 语言标准库 <str…

Java 集合-List

集合主要分为两组(单列集合, 双列集合) Connection 接口有两个重要的子接口LIst 和 Set, 它们的实现子类都是单列集合, Map 接口的实现子类是双列集合, 存放的是 K-V Connection 接口 Collection 接口和常用方法 下面以 ArrayList 演示一下 add: 添加单个元素remove: 删除指…

基于GIS地理技术+智慧巡检解决方案(Word原件)

传统的巡检采取人工记录的方式&#xff0c;该工作模式在生产中存在很大弊端&#xff0c;可能造成巡检不到位、操作失误、观察不仔细、历史问题难以追溯等现象&#xff0c;使得巡检数据不准确&#xff0c;设备故障隐患得不到及时发现和处理。因此建立一套完善的巡检管理系统是企…

【C语言】——联合体与枚举

【C语言】——联合体与枚举 一、联合体1.1、联合体类型的声明1.2、联合体的特点1.3、相同成员的结构体和联合体对比1.4、联合体的大小计算1.5、联合体的应用举例 二、枚举2.1、枚举类型的声明2.2、枚举类型的优点 一、联合体 1.1、联合体类型的声明 联合体也叫做共用体   与…

TLF35584 Windows Watchdog

1、相关寄存器 1&#xff09;WWDCFG0 - Protected Window watchdog configuration request 0 *R2 offset Address&#xff1a;09H&#xff1b;Reset Value&#xff1a;06H&#xff1b; 窗口看门狗关窗口的周期默认值&#xff1a;350wd cycles 350ms。 2&#xff09;WWDCFG1…

国产银河麒麟V10SP1系统下搭建TiDB数据库操作步骤图文

开发目的&#xff1a;在国产银河麒麟系统中搭建TiDB数据库运行环境。 开发工具&#xff1a;银河麒麟系统V10SP1TiDBMySql数据库8.0。 具体步骤&#xff1a; 1、在VmWare虚拟机中安装好国产银河麒麟V10Sp1操作系统。 2、打开终端命令&#xff0c;安装TiDB相关软件&#xff1…

调试记录 CPU PCIE 找不到设备,AC 耦合电容的问题

1. 问题 现象&#xff1a; 1. 国产CPU的主板&#xff0c;主板内的PCIE 设备找的到&#xff0c;但是另一块板子上连接的PCIE 设备找不到。 2. 排查问题在哪里的计划 1. 检查原理图先排除信号定义的问题&#xff0c; TXRX是否反接。 2. 示波器检查PCIE 的时钟频率是否正确。 3. …

ESLint: Unexpected ‘debugger‘ statement.(no-debugger)(debugger报红)

ESLint: Unexpected debugger statement.(no-debugger) 解决办法&#xff1a; 找到.eslintrc.js文件中rules的no-debugger更改为0即可

队列的实现(使用链表)

P. S.&#xff1a;以下代码均在VS2019环境下测试&#xff0c;不代表所有编译器均可通过。 P. S.&#xff1a;测试代码均未展示头文件stdio.h的声明&#xff0c;使用时请自行添加。 目录 1、队列的概念2、队列的链表实现方法2.1 前言2.2 正文2.2.1 队列的初始化2.2.2 队列的销毁…

苹果公司因iPad广告争议而道歉,承认“未达标”|TodayAI

周二&#xff0c;苹果公司发布了一则新的iPad Pro广告&#xff0c;引起了广泛争议&#xff0c;该公司随后发表道歉声明&#xff0c;承认这则广告“未达标”。这则名为“压碎&#xff01;”的广告意图展示全新的M4芯片iPad Pro的创意潜力&#xff0c;但却因其表现方式而备受批评…
最新文章