数据结构【双链表】

前言

我们前面学习了单链表(点击这里跳转到单链表博客)，那么应该发现了一个问题，就是我每次尾插和尾删都需要先把链表遍历一遍，这样是不是过于麻烦了，这时候我们就可以使用双向链表。

1. 链表的分类

  • 带头和不带头

首先带头就是在链表的头节点前面再添加一个节点，这个节点的next指针指向的是头节点并且不存储任何的数据，就像一个哨兵一样(所以我们也把这个节点成为哨兵位)。
不带头就是我的链表的第一个节点就会存储数据。
在这里插入图片描述

  • 单向和双向

单向就是我只有一个指针变量，只用来存放我下一个节点的地址。
双向就是我在单向的基础上，再加一个指针变量，这个指针变量是用来存放前一个节点的地址。
在这里插入图片描述

  • 循环和不循环

是否循环是看你最后一个节点的next的指向；如果指向NULL，就为不循环；如果指向的是我的头节点或者链表的其他节点，就为循环链表。
在这里插入图片描述

一个链表都是包含这三个元素的，这样下来，前前后后能组成八种链表，其中单链表和双链表是两个极端。
单链表的全名是不带头单向不循环链表。
双链表的全名是带头双向循环链表。
在这里插入图片描述

2. 双链表的结构

typedef int LTDATATYPE;

typedef struct ListNode
{
	LTDATATYPE data;
	struct ListNode* next; //指向下一个节点
	struct ListNode* prev; //指向前一个节点 prev(previous的缩写)
}LTNode;

3. 双链表接口的实现

头文件(List.h)

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDATATYPE;

typedef struct ListNode
{
	LTDATATYPE data;
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向前一个 prev(previous的缩写)
}LTNode;

//初始化
LTNode* LTInit();
void LTDesTroy(LTNode* phead);

void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDATATYPE x);
//头插
void LTPushFront(LTNode* phead, LTDATATYPE x);

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


//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDATATYPE x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDATATYPE x);

3.1 创建新节点

LTNode* BuyNode(LTDATATYPE x)
{
	LTNode* Node = (LTNode*)malloc(sizeof(LTNode));
	if(Node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	Node->data = x;
	Node->next = Node->prev = Node;
	return Node;
}

由于这段函数只用来服务该文件内的函数，所以不需要再头节点声明；如果后面需要再其他文件内使用，则再声明到头文件即可。

3.2 双链表的初始化

由于我们这个双链表是带头的，所以我们可以使用函数(创建新节点)来解决

//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyNode(-1);//这里可以传任意的值，我们要使用双链表的时候并不会使用哨兵位的数据
	return phead;
}

创建哨兵位节点时，我们可以给随机的值，我们在使用双链表的时候并不会使用哨兵位的数据。

3.3 尾插

由于我们并不改变哨兵位的地址，因此传一级即可！！！

void LTPushBack(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	LTNode* NewNode = BuyNode(x);
	
	//用来存放当前链表的尾节点
	LTNode* pcur = phead->prev;

	//改变新节点的指向
	NewNode->prev = pcur;
	NewNode->next = phead;

	pcur->next = NewNode;
	phead->prev = NewNode;
}

具体如下图
在这里插入图片描述

3.4 头插

//头插
void LTPushFront(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	//头插是在插入在哨兵位的后面，成为哨兵位后的第一个节点
	//不是插入到哨兵位的前面

	LTNode* NewNode = BuyNode(x);
	
	LTNode* ptmp = phead->next;

	NewNode->prev = phead;
	NewNode->next = ptmp;

	ptmp->prev = NewNode;
	phead->next = NewNode;

}

原理和尾插大致相同，但要注意的是头插是在插入在哨兵位的后面，成为哨兵位后的第一个节点，而不是在链表的前面插入节点。
具体如下图：
在这里插入图片描述

3.5 尾删

我们除了判断phead是否为空以外，我们还要判断phead是否只有哨兵位。

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->prev != phead);

	LTNode* del = phead->prev;

	phead->prev = del->prev;
	del->prev->next = phead;

	free(del);
	del = NULL;
}

我们先创建一个del来储存链表的尾节点，将del的前节点的next指针指向phead，再将phead的prev的指针指向del的前一个节点。在这里插入图片描述

3.6 头删

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->prev != phead);

	LTNode* del = phead->next;

	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

逻辑如下图
在这里插入图片描述

3.7 查找节点

根据节点的数据进行查找，如果找到了，返回被找到的节点；如果找不到，就返回NULL

LTNode* LTFind(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

3.8 在指定节点后插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDATATYPE x)
{
	assert(pos);

	LTNode* NewNode = BuyNode(x);

	NewNode->prev = pos;
	NewNode->next = pos->next;

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

注意：改变原链表的顺序不能变
假设我是先改变了pos的next指针，再改变原pos的下一个节点的指向就会很麻烦
在这里插入图片描述
所以我们先改变pos的下一个节点的prev，再改变pos的next
在这里插入图片描述

3.9 删除指定节点

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos && pos->next != pos);

	LTNode* del = pos;

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(del);
	del = NULL;

}

大致和头删一样，先改变前一个节点的指向和先改变后一个节点的指向都可以。

3.10 打印双链表

void LTPrint(LTNode* phead)
{
	assert(phead != NULL);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
}

3.11 销毁双链表

void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* del = phead->next;
	while (del != phead)
	{
		LTNode* pcur = del->next;
		free(del);
		del = pcur;
	}
	//跳出循环后，phead只剩下哨兵位
	free(phead);
	phead = NULL;
}

大体和单链表的销毁类似，就是要在循环结束后把哨兵位给释放掉。

4. 完整代码

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDATATYPE;

typedef struct ListNode
{
	LTDATATYPE data;
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向前一个 prev(previous的缩写)
}LTNode;


//初始化
LTNode* LTInit();
//销毁
void LTDesTroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDATATYPE x);
//头插
void LTPushFront(LTNode* phead, LTDATATYPE x);

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


//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDATATYPE x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDATATYPE x);

源文件

#include"List.h"
//创建新节点
LTNode* BuyNode(LTDATATYPE x)
{
	LTNode* Node = (LTNode*)malloc(sizeof(LTNode));
	Node->data = x;
	Node->next = Node->prev = Node;
	return Node;
}
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit()
{
	LTNode* phead = BuyNode(-1);
	return phead;
}

//销毁
void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* del = phead->next;
	while (del != phead)
	{
		LTNode* pcur = del->next;
		free(del);
		del = pcur;
	}

	free(phead);
	phead = NULL;
}

//打印
void LTPrint(LTNode* phead)
{
	assert(phead != NULL);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
}


//尾插
void LTPushBack(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	LTNode* NewNode = BuyNode(x);

	LTNode* pcur = phead->prev;

	NewNode->prev = pcur;
	NewNode->next = phead;

	pcur->next = NewNode;
	phead->prev = NewNode;

}
//头插
void LTPushFront(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	//头插是在插入在哨兵位的后面，成为哨兵位后的第一个节点
	//不是插入到哨兵位的前面

	LTNode* NewNode = BuyNode(x);
	
	LTNode* ptmp = phead->next;

	NewNode->prev = phead;
	NewNode->next = ptmp;

	ptmp->prev = NewNode;
	phead->next = NewNode;

}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->prev != phead);

	LTNode* del = phead->prev;

	phead->prev = del->prev;
	del->prev->next = phead;

	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->prev != phead);

	LTNode* del = phead->next;

	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}


//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDATATYPE x)
{
	assert(pos);

	LTNode* NewNode = BuyNode(x);

	NewNode->prev = pos;
	NewNode->next = pos->next;

	pos->next->prev = NewNode;
	pos->next = NewNode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos && pos->next != pos);

	LTNode* del = pos;

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(del);
	del = NULL;

}

LTNode* LTFind(LTNode* phead, LTDATATYPE x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

结语

最后感谢您能阅读完此片文章，如果有任何建议或纠正欢迎在评论区留言，也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
如果您认为这篇文章对您有所收获，点一个小小的赞就是我创作的巨大动力，谢谢！！！

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

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

相关文章

【计算机视觉 Mamba】MambaOut: Do We Really Need Mamba for Vision?

【计算机视觉 Mamba】MambaOut: Do We Really Need Mamba for Vision?

MambaOut: Do We Really Need Mamba for Vision? 在视觉任务上我们需要Mamba吗? 论文地址 代码地址 知乎解读&#xff1a;王牌飞行员申请出战&#xff01; 知乎解读&#xff1a;Mamba 模型解读 (一)&#xff1a;MambaOut&#xff1a;在视觉任务中&#xff0c;我们真的需要 …
阅读更多...
JRebel 激活及使用

JRebel 激活及使用

插件下载 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 从磁盘安装下载的插件 windows下载激活服务 Releases ilanyu/ReverseProxy GitHub mac没有对应版本&#xff0c;需要Docker搭建本地激活服务 docker pull qierkang/golang-reverseproxy docker run -d -…
阅读更多...
私域如何高效管理多微信并实现聚合聊天？

私域如何高效管理多微信并实现聚合聊天？

在私域经营中&#xff0c;管理多个微信号是一项具有挑战性的任务。为了提高工作效率&#xff0c;辅助工具成为必不可少的一部分。而个微管理系统将为大家带来高效的多微信号管理体验&#xff0c;让大家能够更好地聚合聊天。 首先&#xff0c;个微管理系统提供了一个统一的界面…
阅读更多...
C++ STL 中的自定义比较：深入理解相等和等价

C++ STL 中的自定义比较：深入理解相等和等价

STL 中的自定义比较、相等和等价 一、简介二、STL 的排序部分三、STL 的未排序部分四、比较元素五、实现比较器六、总结 一、简介 本文主要讨论了在 STL 中使用自定义比较函数&#xff0c;以及比较操作中的相等和等价概念。 有如下的代码&#xff1a; std::vector< std::…
阅读更多...
代码文本编辑器-小白教程（Sublime text, Notepad++ Acode下载安装与使用）

代码文本编辑器-小白教程（Sublime text, Notepad++ Acode下载安装与使用）

代码文本编辑器-小白教程&#xff08;Sublime text, Notepad Acode下载安装与使用&#xff09; 1. Windows平台和Linux平台1.1 Sublime text1.2 Notepad 2. 安卓平台 Acode参考资料 1. Windows平台和Linux平台 1.1 Sublime text 一、安装教程 1、打开Sublime Text官网下载安…
阅读更多...
Python知识详解【1】~{正则表达式}

Python知识详解【1】~{正则表达式}

正则表达式是一种用于匹配字符串模式的文本工具&#xff0c;它由一系列普通字符和特殊字符组成&#xff0c;可以非常灵活地描述和处理字符串。以下是正则表达式的一些基本组成部分及其功能&#xff1a; 普通字符&#xff1a;大多数字母和数字在正则表达式中表示它们自己。例如…
阅读更多...
【全开源】民宿酒店预订管理系统（ThinkPHP+uniapp+uView）

【全开源】民宿酒店预订管理系统（ThinkPHP+uniapp+uView）

民宿酒店预订管理系统 特色功能&#xff1a; 客户管理&#xff1a;该功能可以帮助民宿管理者更加有效地管理客户信息&#xff0c;包括客户的姓名、电话、地址、身份证号码等&#xff0c;并可以在客户的订单中了解客户的消费情况&#xff0c;从而更好地满足客户的需求&#xff…
阅读更多...
【C++】数据结构：哈希桶

【C++】数据结构：哈希桶

哈希桶&#xff08;Hash Bucket&#xff09;是哈希表&#xff08;Hash Table&#xff09;实现中的一种数据结构&#xff0c;用于解决哈希冲突问题。哈希表是一种非常高效的数据结构&#xff0c;它通过一个特定的函数&#xff08;哈希函数&#xff09;将输入数据&#xff08;通常…
阅读更多...
[Android]将私钥（.pk8）和公钥证书（.pem/.crt）合并成一个PKCS#12格式的密钥库文件

[Android]将私钥（.pk8）和公钥证书（.pem/.crt）合并成一个PKCS#12格式的密钥库文件

如下&#xff0c;我们有一个platform.pk8和platform.x509.pem。为了打包&#xff0c;需要将私钥&#xff08;.pk8&#xff09;和公钥证书&#xff08;可能是.pem或.crt文件&#xff09;合并成一个PKCS#12 格式的密钥库文件 1.准备你的私钥和证书文件 确保你有以下两个文件&…
阅读更多...
【静态分析】在springboot使用太阿（Tai-e）02

【静态分析】在springboot使用太阿（Tai-e）02

参考&#xff1a;使用太阿&#xff08;Tai-e&#xff09;进行静态代码安全分析&#xff08;spring-boot篇二&#xff09; - 先知社区 本文章使用的被分析代码为GitHub - JoyChou93/java-sec-code: Java web common vulnerabilities and security code which is base on springb…
阅读更多...
【Linux】Linux基本指令1

【Linux】Linux基本指令1

1.软件&#xff0c;OS&#xff0c;驱动 我们看看计算机的结构层次 1.1.操作系统 操作系统是一款做 软硬件管理 的软件 操作系统&#xff08;计算机管理控制程序&#xff09;_百度百科 (baidu.com) 操作系统&#xff08;英语&#xff1a;Operating System&#xff0c;缩写&a…
阅读更多...
做视频号小店遇到差评怎么处理？如何规避差

做视频号小店遇到差评怎么处理？如何规避差

大家好&#xff0c;我是喷火龙。 大家在做店的时候应该都会遇到品退、中差评这些问题&#xff0c;这对我们的店铺影响还是非常大的&#xff0c;差评过多就会影响店铺的体验分&#xff0c;从而影响店铺的流量&#xff0c;还会间接的影响商品的转化率&#xff0c;如果太低的话&a…
阅读更多...
nginx的常用配置与命令相关硬核干货

nginx的常用配置与命令相关硬核干货

今天小晨跟大家分享Nginx常用配置与命令相关的硬核干货&#xff0c;可以说运维工作中基本都会用到这些&#xff0c;掌握它&#xff0c;你可以不用求人&#xff01; Nginx特点 高并发、高性能&#xff1b; 模块化架构使得它的扩展性非常好&#xff1b; 异步非阻塞的事件驱动模…
阅读更多...
如何使用java设计出一款可以玩的数独游戏！

如何使用java设计出一款可以玩的数独游戏！

要用Java设计一个数独游戏，你可以按照以下步骤进行： 创建一个9x9的二维数组来表示数独的棋盘。生成一个有效的数独解作为游戏的答案。随机地从答案中移除一些数字，以创建游戏的难度等级。创建一个图形用户界面（GUI）来显示棋盘和与用户的交互。检测用户输入的数字是否正确，…
阅读更多...
流水账（CPU设计实战）——lab3

流水账（CPU设计实战）——lab3

Lab3 Rewrite V1.0 版本控制 版本描述V0V1.0相对V0变化&#xff1a; 修改了文件名&#xff0c;各阶段以_stage结尾&#xff08;因为if是关键词&#xff0c;所以module名不能叫if&#xff0c;遂改为if_stage&#xff0c;为了统一命名&#xff0c;将所有module后缀加上_stage&a…
阅读更多...
设计模式 22 访问者模式 Visitor Pattern

设计模式 22 访问者模式 Visitor Pattern

设计模式 22 访问者模式 Visitor Pattern 1.定义 访问者模式是一种行为型设计模式&#xff0c;它允许你在不改变已有类结构的情况下&#xff0c;为一组对象添加新的操作。它将算法与对象结构分离&#xff0c;使你能够在不修改现有类的情况下&#xff0c;为这些类添加新的操作。…
阅读更多...
Autosar Dcm配置-特定NRC实现方式-基于ETAS软件

Autosar Dcm配置-特定NRC实现方式-基于ETAS软件

文章目录 前言工具配置代码编写总结 前言 项目开发过程中&#xff0c;诊断服务一般客户需求或系统需求都会有特定NRC(一般为NRC22-条件不满足)&#xff0c;也就会有特定的条件&#xff0c;需要手动加代码实现。本文介绍ETAS工具中配置的接口及简单实现。 工具配置 对于每一个…
阅读更多...
【高阶数据结构】 B树 -- 详解

【高阶数据结构】 B树 -- 详解

一、常见的搜索结构 适合做内查找&#xff1a; 以上结构适合用于数据量相对不是很大&#xff0c;能够一次性存放在内存中&#xff0c;进行数据查找的场景。如果数据量很大&#xff0c;比如有 100G 数据&#xff0c;无法一次放进内存中&#xff0c;那就只能放在磁盘上了。 如果…
阅读更多...
坦克飞机大战项目详解：从包结构到测试发布

坦克飞机大战项目详解：从包结构到测试发布

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、项目初始化与包结构构建 代码案例&#xff1a; 二、资源文件与配置文件管理 代码案例…
阅读更多...
关于NLTK

关于NLTK

一、NLTK简介 下图来自NLTK官网&#xff1a;https://www.nltk.org/index.html NLTK&#xff0c;全称为Natural Language Toolkit&#xff0c;是一个用于处理和分析自然语言文本的Python库。它提供了一系列丰富的工具和资源&#xff0c;包括词汇资源&#xff08;如WordNet&am…
阅读更多...
最新文章

Copyright @ 2022~2023