数据结构入门篇 之 【双链表】的实现讲解(附完整实现代码及顺序表与线性表的优缺点对比)

在这里插入图片描述
一日读书一日功,一日不读十日空
书中自有颜如玉,书中自有黄金屋

一、双链表

1、双链表的结构

2、双链表的实现

1)、双向链表中节点的结构定义

2)、初始化函数 LTInit

3)、尾插函数 LTPushBack

4)、头插函数 LTPushFront

5)、尾删函数 LTPopBack

6)、头删函数 LTPopFront

7)、查找函数 LTFind

8)、在指定位置之后插入数据函数 LTInsert

9)、删除指定位置数据函数 LTErase

10)、销毁函数 LTDesTroy

二、双链表完整代码

三、顺序表和链表的优缺点对比

四、完结撒❀

前言

学习前先思考3个问题:

1.顺序表和链表的关系是什么?
2.链表的分类有哪些?
3.顺序表和链表的优缺点有哪些?

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
1.顺序表和链表的关系是什么

我们之前学习了“顺序表”,“单链表”。
链表和顺序表都是线性表
线性表是指

逻辑结构:一定是线性的。
物理结构:不一定是线性的。

在这里插入图片描述物理结构是指表在内存中开辟的空间结构,顺序表的物理结构是连续的,而链表的物理结构是不连续的,但它们的逻辑结构都是连续的。

2.链表的分类有哪些?
链表根据带头或者不带头单向或者双向循环或者不循环一共分为8种
我们之前所学的单链表全名是叫:不带头单向不循环链表,而现在要学习的双链表是叫带头双向循环链表
双链表:
在这里插入图片描述掌握单链表和双链表对于其他链表的实现也就不那么困难了。

3.顺序表和链表的优缺点有哪些?
这里涉及到顺序表和链表的对比,先讲解双向链表,这放到博客末尾为大家对比讲解

一、双链表

1、双链表的结构

在这里插入图片描述注意:这里的“带头”跟前面我们说的“头节点”是两个概念。
带有节点里的头节点实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”

“哨兵位”存在的意义:
遍历循环链表避免出现死循环。

2、双链表的实现

对于双向链表的实现,我们依然使用List.h,List.c,test.c,三个文件进行实现。

1)、双向链表中节点的结构定义

上面我们简单介绍过双链表,其全名为:带头双向循环链表

带头:指链表中带有哨兵位
双向:双链表的每个节点内含有两个链表指针变量,分别指向前一个节点和后一个节点,所以就可以通过一个节点找到这个节点前后的两个节点。
循环:链表中的每个节点互相连接,最后一个节点与哨兵位相连构成一个环,整体逻辑结构可以进行循环操作

代码如下:

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LTDataType data;
	struct ListNode* next;
}LTNode;

这里将结构体进行了重命名为LTNode。

2)、初始化函数 LTInit

在创建双链表中的哨兵位时我们需要对其进行初始化,防止意料之外的情况发生。
根据所传形参的类型不同,我们有两种写法
代码如下:

方案1

//方案1
void LTInit(LTNode** pphead)
{
	(*pphead) = (LTNode*)malloc(sizeof(LTNode));
	if (*pphead == NULL)
	{
		perror("mallic:");
		exit(1);
	}

	(*pphead)->data = -1;
	(*pphead)->prev = (*pphead)->next = *pphead;
}

方案2

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}

	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

//方案2
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

方案2里面包含了节点空间申请的函数,只是简单的创建双链表的节点,这里就不展开讲解了。

3)、尾插函数 LTPushBack

老规矩,我们开始实现管理链表数据的函数,这里讲的是头插。
在这里插入图片描述假如我们要在链表中尾插一个6,那么我们是需要先创建一个节点来存储6,下面分两步:

1.将6的节点里面前(prev)后(next)链表指针变量对应与原链表的尾节点d3和哨兵位head进行连接
2.将原链表尾节点d3的后链表指针变量(next)指向6的节点,再将哨兵位head的前链表指针变量(prev)指向6的节点

完成上面两部就实现了节点的插入。
代码如下:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

这里的LTBuyNode函数在初始化函数中提到过。

4)、头插函数 LTPushFront

实现了尾插,头插也是大同小异。
头插是指在哨兵位后面的进行插入,第一个有效节点之前插入,即为头插。
在这里插入图片描述根据上图,进行头插

1.改变插入节点6的前后链表指针变量的指向。
2.再分别改变哨兵位head后链表指针变量(next)和第一个有效节点d1的前链表指针变量(prev)的指向。

代码如下:

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;
}

也是简简单单。

5)、尾删函数 LTPopBack

尾删函数的操作如下图:
在这里插入图片描述
1.改变哨兵位的前链表指针变量,指向原链表(还没尾删时的链表)尾节点d3的前链表指针变量(即倒数第二个节点d2的地址)。
2.相反,再将d2节点的后链表指针变量(next)指向哨兵位head。

代码如下:

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表只有一个哨兵位也不行
	assert(phead != phead->next);

	LTNode* del = phead->prev;//要进行尾删的节点
	LTNode* ddel = del->prev;//要进行删除的前一节点
	phead->prev = ddel;
	ddel->next = phead;
	free(del);
	del = NULL;
}

记得最后将尾删的节点空间进行释放。

6)、头删函数 LTPopFront

头删函数的操作如下图:
在这里插入图片描述与尾删也是大同小异
代码如下:

//头删 在哨兵位之后进行删除
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* del = phead->next;//要进行删除的节点
	LTNode* ddel = del->next;//要进行删除节点的下一个节点

	phead->next = ddel;
	ddel->prev = phead;
	free(del);
	del = NULL;
}

7)、查找函数 LTFind

既然要查找,那么肯定需要遍历链表并且也要保证链表不为空

在双链表中,当链表中只剩下哨兵位,那么这个链表即为空链表。

代码如下:

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	assert(phead != phead->next);

	//遍历链表
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

断言时进行的assert(phead != phead->next);便是判断链表是否为空的条件。
而while (pcur != phead)是判断是否将链表遍历完的条件。
找到的话就返回给节点的地址,没有找到就返回空指针。

8)、在指定位置之后插入数据函数 LTInsert

操作过程如下图所示:
在这里插入图片描述假设我们在节点d2后面进行节点的插入,那么会受到影响的就是d2节点的后链表指针变量(next)和d3节点的前链表指针变量(prev),需要执行的操作:

1.将newnode节点的前链表指针变量(prev)指向d2节点,再将newnode节点的后链表指针变量(next)指向d3节点
2.将d3节点的前链表指针变量(prev)指向newnode’节点,再将d2节点的后链表指针变量(next)指向newnode节点。

注意! 第2步指针变量改变指向的先后顺序不能改变,不然指向地址不正确!

代码如下;

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* del = pos->next;//pos之后的数据
	LTNode* front = pos->prev;//pos之前的数据

	front->next = del;
	del->prev = front;

	free(pos);
	pos = NULL;
}

9)、删除指定位置数据函数 LTErase

操作过程如下图所示:
在这里插入图片描述假设删除d3节点,很明显这就是尾删操作,所以删除指定位置数据与其他删除函数也是一样的原理,其影响到的就是删除节点前后的节点链表指针的指向。

代码如下:

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* del = pos->next;//pos之后的数据
	LTNode* front = pos->prev;//pos之前的数据

	front->next = del;
	del->prev = front;

	free(pos);
	pos = NULL;
}

重要的是最在要记得将删除的节点空间进行销毁。

10)、销毁函数 LTDesTroy

那么最后的一个函数,销毁函数。
创建双建表使用后我们一定不要忘记进行销毁,将开辟的内存空间归还给计算机,不然在以后中可能会出现内存泄漏的工作事故。
销毁函数也根据传参类型不同有两种方案
代码如下:
方案1

//方案1
void LTDesTroy(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

方案2

//方案2
void LTDesTroy(LTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	LTNode* pcur = (*pphead)->next;
	while (pcur != (*pphead))
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free((*pphead));
	(*pphead) = NULL;
}

对比之下方案1所传的形参为一级指针,而方案2为二级指针,因此我们是可以在方案2中直接对形参解引用得到双链表的哨兵位进行释放,而方案1并不行。
所以大家评判一下是那种方案更好呢?
其实是方案1更好,因为我们需要保持接口一致性,细心的同学可能已经发现了,之前所写的函数形参都为一级指针,所以我们在写代码的时候保持接口一致性也是很重要的,所以方案1更合适一些,至于链表中哨兵位的释放,我们下面在销毁函数外(主函数内)进行销毁即可。

二、双链表完整代码

List.h:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LTDataType data;
	struct ListNode* next;
}LTNode;

//注意双向链表是带有哨兵位的,插入数据之前链表中必须先插入一个哨兵位

//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy();

//尾插
void LTPushBack(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead,LTDataType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

List.c:


	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

//方案1
//void LTInit(LTNode** pphead)
//{
//	(*pphead) = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL)
//	{
//		perror("mallic:");
//		exit(1);
//	}
//
//	(*pphead)->data = -1;
//	(*pphead)->prev = (*pphead)->next = *pphead;
//}

//方案2
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

void LTPrint(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表只有一个哨兵位也不行
	assert(phead != phead->next);

	LTNode* del = phead->prev;//要进行尾删的节点
	LTNode* ddel = del->prev;//要进行删除的前一节点
	phead->prev = ddel;
	ddel->next = phead;
	free(del);
	del = NULL;
}

//头删 在哨兵位之后进行删除
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* del = phead->next;//要进行删除的节点
	LTNode* ddel = del->next;//要进行删除节点的下一个节点

	phead->next = ddel;
	ddel->prev = phead;
	free(del);
	del = NULL;
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	assert(phead != phead->next);

	//遍历链表
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* del = pos->next;//pos之后的数据
	LTNode* front = pos->prev;//pos之前的数据

	front->next = del;
	del->prev = front;

	free(pos);
	pos = NULL;
}

//方案1
void LTDesTroy(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

//方案2
//void LTDesTroy(LTNode** pphead)
//{
//	assert(pphead);
//	assert(*pphead);
//
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != (*pphead))
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//	free((*pphead));
//	(*pphead) = NULL;
//}

三、顺序表和链表的优缺点对比

学到这里大家会感觉双链表听起来可能比较复杂,但学完之后感觉比顺序表和单链表还容易,事实就是如此。
顺序表和双向链表优缺点分析:
在这里插入图片描述由上图,并不是双链表一定比顺序表好。
顺序表和双链表各有优势,我们在使用中要根据实际情况选择适合的线性表进行存储就是最好的。

四、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多计算机知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友
在这里插入图片描述

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

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

相关文章

华为三层交换机:ACL的基本实验

实验要求&#xff1a; PC1不允许访问PC3&#xff0c;PC3可以访问PC1 分析问题&#xff1a; PC1不允许访问PC3&#xff0c;问题中含有“目标地址”则我们需要设置目标地址&#xff0c;这样基本ACL是不行的&#xff0c;必须使用高级ACL [sw1]acl ? INTEGER<2000-2999>…

数字图像处理 使用C#进行图像处理九 实现傅里叶变换

一、简述 傅立叶变换将图像分解为其正弦和余弦分量。换句话说,它将图像从空间域变换到频率域。这个想法是任何函数都可以用无限正弦函数和余弦函数之和来精确近似。傅里叶变换是实现此目的的一种方法。 网上有很多关于傅里叶变换的文章,这里就不进行赘述了,这里主要结合代码…

python爬虫实战——抖音

目录 1、分析主页作品列表标签结构 2、进入作品页前 判断作品是视频作品还是图文作品 3、进入视频作品页面&#xff0c;获取视频 4、进入图文作品页面&#xff0c;获取图片 5、完整参考代码 6、获取全部作品的一种方法 本文主要使用 selenium.webdriver&#xff08;Firef…

【WSN覆盖优化】基于改进黏菌算法的无线传感器网络覆盖 WSN覆盖优化【Matlab代码#65】

文章目录 【可更换其他算法&#xff0c;获取资源请见文章第5节&#xff1a;资源获取】1. 改进SMA算法1.1 改进参数p1.2 混沌精英突变策略 2. WSN节点感知模型3. 部分代码展示4. 仿真结果展示5. 资源获取 【可更换其他算法&#xff0c;获取资源请见文章第5节&#xff1a;资源获取…

Python 基于 OpenCV 视觉图像处理实战 之 开发环境搭建

Python 基于 OpenCV 视觉图像处理实战 之 开发环境搭建 目录 Python 基于 OpenCV 视觉图像处理实战 之 开发环境搭建 一、简单介绍 二、该项目案例的开发环境 三、Python 环境搭建 1、Python 安装包下载 2、这里以 下载 Python 3.10.9 为例 3、安装 Python 3.10.9 4、检…

http协议-基于TCP的超文本传输协议

一、通过http最终实现一个效果 用我们自己电脑上的浏览器去访问我们自己写的python程序&#xff0c;这个程序就可以满足浏览器的需求&#xff0c;你可以从浏览器里面看到自己写出来的网页。所谓的协议就是一种规定。 二、http协议 正常情况下www.xxx是域名&#xff0c;将来…

前端实现复制粘贴功能

在前端开发的世界里&#xff0c;复制粘贴功能就像是那个总是被忽视&#xff0c;却在关键时刻能救你一命的老朋友。我们习惯了用那些古老的魔法咒语&#xff08;document.execCommand(copy)&#xff09;来实现这一功能&#xff0c;但时代在进步&#xff0c;技术在更新&#xff0…

LNMP架构之web服务器实战

LNMP架构 1.nginx部署 systemctl disable --now keepalived.service 关闭keepalived服务&#xff0c;避免冲突 将下载好的nginx软件压缩包直接拖入mobaxterm目录即可 tar zxf nginx-1.23.3.tar.gz cd nginx-1.23.3/ yum install -y gcc pcre-devel openssl-devel #安装依…

LInux系统架构----Nginx模块rewrite的规则与应用场景

LInux系统架构----Nginx模块rewrite的规则与应用场景 一.rewrite跳转实现 Nginx实现跳转通过ngx_http_rewrite_module模块支持URL重写、支持if条件判断&#xff0c;但是不支持else跳转时&#xff0c;循环最多可以执行10次&#xff0c;超过后nginx将返回500错误注&#xff1a;…

0基础使用dockerfile构建容器镜像

目录 一、使用dockerfile构建镜像 1.1、dockerfile指令 1.FROM 2.RUN 3.CMD 4.ENTRYPOINT 5.EXPOSR ​编辑 6.ADD和COPY ​编辑7.volume 8.USER 二、案例1&#xff1a;dockerfile构建httpd镜像 构建一个指定挂载点的httpd镜像 三、案例2&#xff1a;构建tomcat镜…

使用endnote插入引用文献导致word英文和数字变成符号的解决方案

使用endnote插入引用文献导致word英文和数字变成符号的解决方案 如图使用endnote插入引用文献导致word英文和数字变成符号字体Wingdings Wingdings 是一个符号字体系列&#xff0c;它将许多字母渲染成各式各样的符号&#xff0c;用途十分广泛。 **解决方法&#xff1a;**直接通…

【相关问题解答1】bert中文文本摘要代码:import时无法找到包时,几个潜在的原因和解决方法

【相关问题解答1】bert中文文本摘要代码 写在最前面问题1问题描述一些建议import时无法找到包时&#xff0c;几个潜在的原因和解决方法1. 模块或包的命名冲突解决方法&#xff1a; 2. 错误的导入路径解决方法&#xff1a; 3. 第三方库的使用错误解决方法&#xff1a; 4. 包未正…

gpt-4-all模型中转实现

最近才完成这个功能&#xff0c;相信知道这个模型的人&#xff0c;应该已经熟悉了。这是我的中转&#xff1a;openai-api Chatbox配置如下&#xff1a; 模型测试&#xff1a; 1&#xff09;图片生成 2&#xff09;文件分析&#xff0c;链接读取&#xff1a;

WPF实时时间显示demo(MVVM)

跟着b站的视频学习做一个界面,它里面的时间不能实时刷新,因此自己研究写一个,同时加深一下自己对MVVM的理解. 运行结果: 实现步骤: 1.界面 界面设计就是放置了一个TextBlock,它的text绑定了ViewModel层里面的公告属性CurrentTime. <Grid><TextBlock Text"{Bindi…

【Vite+Ts】自动按需引入Element-Plus

安装插件 cnpm i -D unplugin-vue-components unplugin-auto-import unplugin-element-plus修改vite.config.ts // vite.config.ts import AutoImport from "unplugin-auto-import/vite"; import Components from "unplugin-vue-components/vite"; impor…

白嫖AWS云服务器,验证、注册指南

背景 不知道你想不想拥有一台属于自己的云服务器呢&#xff0c;拥有一台自己的云服务器可以建站&#xff0c;可以在上面搭建个人博客&#xff0c;今天我就来教大家如何申请亚马逊 AWS 免费云服务器&#xff0c;这个云服务器可以长达12个月的免费。而且到期后可以继续换个账号继…

【Flink SQL】Flink SQL 基础概念:SQL 动态表 连续查询

Flink SQL 基础概念&#xff1a;SQL 动态表 & 连续查询 1.SQL 应用于流处理的思路2.流批处理的异同点及将 SQL 应用于流处理核心解决的问题3.SQL 流处理的输入&#xff1a;输入流映射为 SQL 动态输入表4.SQL 流处理的计算&#xff1a;实时处理底层技术 - SQL 连续查询5.SQL…

Arduino IDE的下载和安装

一、Arduino的介绍 Arduino是一款开源电子原型平台&#xff0c;主要包含两部分&#xff1a;硬件&#xff08;各种型号的Arduino板&#xff09;和软件&#xff08;Arduino IDE&#xff09;。这个平台由意大利的Massimo Banzi、David Cuartielles等人共同开发设计&#xff0c;并于…

OPPO后端二面,凉了!

这篇文章的问题来源于一个读者之前分享的 OPPO 后端凉经&#xff0c;我对比较典型的一些问题进行了分类并给出了详细的参考答案。希望能对正在参加面试的朋友们能够有点帮助&#xff01; Java String 为什么是不可变的? public final class String implements java.io.Seri…

【毕设级项目】基于嵌入式的智能家居控制板(完整工程资料源码)

基于嵌入式的智能家居控制板演示效果 基于嵌入式的智能家居控制板 前言&#xff1a; 随着科技的不断进步&#xff0c;物联网技术得到了突飞猛进的发展。智能家居是物联网技术的典型应用领域之一。智能家居系统将独立家用电器、安防设备连接成一个具有思想的整体&#xff0c;实现…