探索数据结构：便捷的双向链表

🔑🔑博客主页：阿客不是客

🍓🍓系列专栏：渐入佳境之数据结构与算法

欢迎来到泊舟小课堂

😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注

​​

前言

前面我们学习了单链表，它解决了顺序表中插入删除需要挪动大量数据的缺点，使单链表解决顺序表缺陷时，我们发现作为另一种形态出现的单链表似乎也有明显的缺陷。

  1. 在部分功能实现时因为头结点的改变需要引进二级指针（或者采用返回等更为复杂的方法）导致代码更加复杂。
  2. 寻找某个节点的前一个节点，对于单链表而言只能遍历，这样就可能造成大量时间的浪费。
  3. 尾部以及指定位置插入、删除数据的时间复杂度为O(N) ，效率低下。

为了解决这个问题，我们就要学习今天的主角——双向链表。

一、带头双向循环链表的介绍

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构，虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：无头单向不循环链表，带头双向循环链表。

对比单链表来了解，带头双向循环链表：结构复杂，一般单独存储数据。凭着其复杂的结构我们可以做到快速管理数据，实现对数据的操作。

​

带头双向循环链表具有以下特点：

  1. 头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前指针指向尾节点，头节点的后指针指向第一个实际数据节点。
  2. 循环连接：尾节点的后指针指向头节点，而头节点的前指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。
  3. 双向连接：每个节点都有一个前指针和一个后指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。

总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。

二、带头双向循环双链表的实现

2.1 创建链表

双向链表的定义结构体需要包含三个成员，一个成员存储数值，一个成员存储前一个节点的地址，最后一个成员存储下一个节点的地址。

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}LTN;

2.2 初始化链表

在初始化双向链表时，我们需要创建一个头节点，也就是我们常说的哨兵位头节点。

这里需要注意一下：创建头结点的时候，因为链表中没有其它的数据，我们在初始化的时候让guard的next和prev都要指向自己，这样才是一个循环链表（如下图所示 ↓↓↓ ）

​

LTN* LTinit()
{
	LTN* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

2.3 创建新结点

跟之前的一样就不过多介绍了

LTN* CreateLTNode(LTDataType x)
{
	LTN* newnode = (LTN*)malloc(sizeof(LTN));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

2.4 打印链表

这个链表中的结点是没有NULL的，因此在判断循环是否要结束的条件应该是判断tail是否等于phead

void LTprint(LTN* phead)
{
	assert(phead);

	printf("哨兵位 <--> ");
	LTN* tail = phead->next;
	while (tail != phead)
	{
		printf("%d <--> ",tail->val);
		tail = tail->next;
	}
	printf("哨兵位\n");
}

2.5 双向链表的查找

和单链表一样，我们也可以对双向链表进行查找。如果找到就返回该节点的地址，否则返回NULL。

LTN* LTFind(LTN* phead, LTDataType x)
{
	assert(phead);

	LTN* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

2.6 双向链表的插入

2.5.1 尾插

单链表尾插结点需要遍历全链表，当指针走到链表最后一个结点的时候，判断tail->next是否为NULL，若为NULL，则跳出遍历的循环，尾插新结点。然而带头双向循环链表不需要遍历链表，只需要对哨兵位的头节点的prev域解引用，直接找到带头双向循环链表的尾节点，尾插新节点。

​

头指针的区别:带头双向循环链表不需要判断头指针是否指向NULL，因为哨兵位的头节点也是有它的地址的,添加新节点时只需要直接在尾节点尾插。然而单链表却需要判断头指针是否指向NULL，而且需要用到二级指针，比较棘手。

 ​

void LTpushback(LTN* phead, LTDataType x)
{
	assert(phead);
	//带哨兵位头结点，只改变了结构体成员，不需要二级指针
	LTN* tail = phead->prev;
	LTN* newnode = CreateLTNode(x);

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

2.5.2 头插

void LTpushfront(LTN* phead, LTDataType x)
{
	assert(phead);
	LTN* tail = phead->next;
	LTN* newnode = CreateLTNode(x);

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

2.5.3 任意位置插入

void LTInsert(LTN* pos, LTDataType x)
{
	assert(pos);
	LTN* newnode = CreateLTNode(x);
	LTN* tail = pos->prev;

	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = tail;
	tail->next = newnode;
}

和单链表不同，双向链表头尾操作完全可以用任意位置操作替代。 

LTInsert实现尾插：
LTInsert(phead, x);
LTInsert实现头插:
LTInsert(phead->next, x);

2.7 双向链表的删除

2.6.1 尾删

 当链表只有一个节点（哨兵位不算）时:

若链表为NULL(只剩哨兵位就是链表为NULL)时，再尾删就被assert会出错：

void LTpopback(LTN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTN* tail = phead->prev;
	LTN* tailprev = tail->prev;
	
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;
}

2.6.2 头删

链表不止一个结点时:

链表为一个结点时:

代码示例如下： 

void LTpopfront(LTN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTN* tail = phead->next;
	LTN* tailnext = tail->next;

	tailnext->prev = phead;
	phead->next = tailnext;
	free(tail);
	tail = NULL;
}

2.6.3 任意位置删除

void LTErase(LTN* pos)
{
	assert(pos);
	LTN* tailnext = pos->next;
	LTN* tailprev = pos->prev;

	tailnext->prev = tailprev;
	tailprev->next = tailnext;
	free(pos);
	pos = NULL;
}
LTErase实现尾删:
LTErase(phead->prev);

 LTErase实现头删：

LTErase(phead->next);

2.8 销毁链表

void LTDestroy(LTN* phead)
{
	assert(phead);
 
	LTN* cur = phead->next;
	while (cur != phead)
	{
		LTN* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

三、完整代码

3.1 LTN.h

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

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}LTN;

LTN* LTinit();//初始化链表

void LTprint(LTN* phead);

void LTpushback(LTN* phead, LTDataType x);
void LTpushfront(LTN* phead, LTDataType x);
void LTpopback(LTN* phead);
void LTpopfront(LTN* phead);

LTN* LTFind(LTN* phead, LTDataType x);

void LTInsert(LTN* pos, LTDataType x);
void LTErase(LTN* pos);

3.2 LTN.c

#include"SLTN.h"

LTN* CreateLTNode(LTDataType x)
{
	LTN* newnode = (LTN*)malloc(sizeof(LTN));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

LTN* LTinit()
{
	LTN* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void LTprint(LTN* phead)
{
	assert(phead);

	printf("哨兵位 <--> ");
	LTN* tail = phead->next;
	while (tail != phead)
	{
		printf("%d <--> ",tail->val);
		tail = tail->next;
	}
	printf("哨兵位\n");
}

void LTpushback(LTN* phead, LTDataType x)
{
	assert(phead);
	//带哨兵位头结点，只改变了结构体成员，不需要二级指针
	LTN* tail = phead->prev;
	LTN* newnode = CreateLTNode(x);

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

	//LTInsert(phead->prev, x);
}

void LTpushfront(LTN* phead, LTDataType x)
{
	assert(phead);
	LTN* tail = phead->next;
	LTN* newnode = CreateLTNode(x);

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

	//LTInsert(phead->next, x);
}

void LTpopback(LTN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTN* tail = phead->prev;
	LTN* tailprev = tail->prev;
	
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;

	//LTErase(phead->prev);
}

void LTpopfront(LTN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTN* tail = phead->next;
	LTN* tailnext = tail->next;

	tailnext->prev = phead;
	phead->next = tailnext;
	free(tail);
	tail = NULL;

	//LTErase(phead->next);
}

LTN* LTFind(LTN* phead, LTDataType x)
{
	assert(phead);

	LTN* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

void LTInsert(LTN* pos, LTDataType x)
{
	assert(pos);
	LTN* newnode = CreateLTNode(x);
	LTN* tail = pos->prev;

	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = tail;
	tail->next = newnode;
}

void LTErase(LTN* pos)
{
	assert(pos);
	LTN* tailnext = pos->next;
	LTN* tailprev = pos->prev;

	tailnext->prev = tailprev;
	tailprev->next = tailnext;
	free(pos);
	pos = NULL;
}

四、顺序表与链表优缺点分析

  • 链表（双向）优势：
  1. 任意位置插入删除都是O(1)
  2. 按需申请释放，合理利用空间，不存在浪费
  • 问题：
  1. 下标随机访问不方便
  • 顺序表问题：
  1. 头部或中间插入删除效率低，要挪动数据O(N)
  2. 空间不够要扩容，扩容有一定消耗，且可能存在一定的空间浪费
  3. 只适合尾插尾删
  • 优势： 
  1. 支持下标随机访问O(1)，可以进行排序操作。

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

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

相关文章

微服务中feign远程调用相关的各种超时问题

微服务中feign远程调用相关的各种超时问题

1. 引言 在spring cloud微服中&#xff0c;feign远程调用可能是大家每天都接触到东西&#xff0c;但很多同学却没咋搞清楚这里边的各种超时问题&#xff0c;生产环境可能会蹦出各种奇怪的问题。 首先说下结论&#xff1a; 1)只使用feign组件&#xff0c;不使用ribbion组件&…
阅读更多...
FuTalk设计周刊-Vol.045

FuTalk设计周刊-Vol.045

#AI漫谈 热点捕手 1、新模型 Stable Diffusion 3 与 Stable Cascade 全面解析 最近 Stability AI 又接连推出了 2 个新的模型&#xff1a;Stable Diffusion 3 和 Stable Cascade&#xff0c;在图像生成效率和质量上比半年前推出的 SDXL 1.0 有了明显提升&#xff0c;今天就为…
阅读更多...
PyQt5学习系列之ui转py报错问题

PyQt5学习系列之ui转py报错问题

PyQt5学习系列之ui转py报错问题 前言解决步骤一步骤二步骤三 总结 前言 设计好的界面出现ui转py问题&#xff0c;一直出现报错。 一开始通过pycharm进行转化&#xff0c;采用tool工具&#xff0c;一直报错。后用vscode进行转化&#xff0c;转化成功。最终发现问题是语句问题。…
阅读更多...
关于恶意软件、行为透明度和移动恶意软件的最新审核变动

关于恶意软件、行为透明度和移动恶意软件的最新审核变动

关于隐私权、欺骗行为和设备滥用这块，谷歌官方政策一直在改动，最新政策更新出来了，2024 年 8 月 31 日才会进行实施，希望在这期间，开发者们能早点修改重新提包，避免过期后被扫荡下架。 目录 变动新增关于 - 敏感信息访问权限和 API修改范围拒审解决变动新增 关于 - 敏感…
阅读更多...
Linux 僵尸进程和孤儿进程

Linux 僵尸进程和孤儿进程

一.Z(zombie)-僵尸进程 1.僵死状态&#xff08;Zombies&#xff09;是一个比较特殊的状态。当进程退出并且父进程&#xff08;使用wait()系统调用后&#xff09;没有读取到子进程退出的返回代码时就会产生僵死(尸)进程 2.僵死进程会以终止状态保持在进程表中&#xff0c;并且会…
阅读更多...
二进制文件（.bin等文件）转C语言数组形式hex文件（.c等文件）

二进制文件（.bin等文件）转C语言数组形式hex文件（.c等文件）

使用python脚本把二进制文件&#xff08;.bin等文件&#xff09;转C语言数组形式hex文件&#xff08;.c等文件&#xff09;&#xff0c;具体代码如下&#xff1a; &#xff08;1&#xff09;读取.bin文件数据 &#xff08;2&#xff09;生成C语言数组定义 &#xff08;3&…
阅读更多...
中国高分辨率土壤质地数据（1KM）

中国高分辨率土壤质地数据（1KM）

土壤中各粒级占土壤重量的百分比组合&#xff0c;叫做土壤质地。土壤质地是土壤的最基本物理性质之一&#xff0c;对土壤的各种性状&#xff0c;如土壤的通透性、保蓄性、耕性以及养分含量等都有很大的影响是评价土壤肥力和作物适宜性的重要依据。 中国土壤质地空间分布数据是根…
阅读更多...
基于全志T507-H的Igh EtherCAT主站案例分享

基于全志T507-H的Igh EtherCAT主站案例分享

基于全志T507-H的Linux-RT IgH EtherCAT主站演示 下文主要介绍基于全志T507-H&#xff08;硬件平台&#xff1a;创龙科技TLT507-EVM评估板&#xff09;案例&#xff0c;按照创龙科技提供的案例用户手册进行操作得出测试结果。 本次演示的开发环境&#xff1a; Windows开发环…
阅读更多...
岩土工程监测中振弦采集仪数据处理与解读的挑战与方法

岩土工程监测中振弦采集仪数据处理与解读的挑战与方法

岩土工程监测中振弦采集仪数据处理与解读的挑战与方法 岩土工程监测是确保工程安全的重要环节&#xff0c;而振弦采集仪是岩土工程监测中常用的一种设备。振弦采集仪通过测量土体的振动响应&#xff0c;可以获取土体的力学性质和结构特征&#xff0c;为工程设计和施工提供重要…
阅读更多...
【MySQL】MySQL Connect -- 详解

【MySQL】MySQL Connect -- 详解

一、Connector / C 使用 要使用 C 语言连接 MySQL&#xff0c;需要使用 MySQL 官网提供的库&#xff0c;可以去官网进行下载&#xff1a;MySQL :: MySQL Community Downloads 我们使用 C 接口库来进行连接&#xff0c;要正确使用&#xff0c;还需要做一些准备工作&#xff1a…
阅读更多...
计算机视觉与模式识别实验1-4 图像的傅立叶变换

计算机视觉与模式识别实验1-4 图像的傅立叶变换

文章目录 &#x1f9e1;&#x1f9e1;实验流程&#x1f9e1;&#x1f9e1;1. 傅立叶变换1.a 绘制一个二值图像矩阵,并将其傅立叶函数可视化。1.b 利用傅立叶变换分析两幅图像的相关性&#xff0c;定位图像特征。读入图像‘text.png&#xff0c;抽取其中的字母‘a’ 2. 离散余弦…
阅读更多...
操作字符串获取文件名字（包含类型）

操作字符串获取文件名字（包含类型）

记录一种操作字符串获取文件名字的操作方式&#xff0c;方便后期的使用。示例&#xff1a; 输入&#xff1a;"D:/code/Test/Test.txt" 输出&#xff1a;"Test.txt" 设计思路&#xff1a; 首先查找路径中最后一个”/“&#xff0c;然后再通过字符串截取的…
阅读更多...
Flutter开发效率提升1000%，Flutter Quick教程之对写好的Widget进行嵌套

Flutter开发效率提升1000%，Flutter Quick教程之对写好的Widget进行嵌套

通常写代码的时候&#xff0c;我们是先写好外面的Widget&#xff0c;再写里面的Widget。但是&#xff0c;也有的时候&#xff0c;我们写好了一个Widget&#xff0c;但是我们觉得有必要再在外面嵌套一个Widget&#xff0c;这时候应该怎么做呢&#xff1f;&#xff08;还有其他方…
阅读更多...
NVIDIA发布重磅AI创新，黄仁勋在COMPUTEX大会预示计算未来

NVIDIA发布重磅AI创新，黄仁勋在COMPUTEX大会预示计算未来

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
coredns 被误删了，可以通过重新应用 coredns 的 Deployment 或 DaemonSet 配置文件来恢复

coredns 被误删了，可以通过重新应用 coredns 的 Deployment 或 DaemonSet 配置文件来恢复

如果 coredns 被误删了&#xff0c;可以通过重新应用 coredns 的 Deployment 或 DaemonSet 配置文件来恢复。以下是恢复 coredns 的步骤&#xff1a; 1. 下载 coredns 配置文件 你可以从 Kubernetes 的官方 GitHub 仓库下载 coredns 的配置文件。以下是下载并应用配置文件的步…
阅读更多...
Android开机动画，framework修改Bootanimation绘制文字。

Android开机动画，framework修改Bootanimation绘制文字。

文章目录 Android开机动画&#xff0c;framework修改Bootanimation动画绘制文字。 Android开机动画&#xff0c;framework修改Bootanimation动画绘制文字。 frameworks/base/cmds/bootanimation/bootanimation.cpp 绘制时间的一个方法 // We render 12 or 24 hour time. void…
阅读更多...
使用Landsat的NDVI和NDWI阈值法土地分类

使用Landsat的NDVI和NDWI阈值法土地分类

目录 分类效果源代码分类效果 创建一个包含多个层的影像合成：水体（NDWI > 0.5），植被（NDVI > 0.2），阴影区域的裸地（bare2但不包括bare1），和其他裸地（bare1）。然后，使用mosaic()方法合并这些层，并用clip(hh)方法裁剪到研究区域的范围。 源代码 var hh = ee.…
阅读更多...
linux 内核映像差异介绍：vmlinux、zImage、zbImage、image、uImage等

linux 内核映像差异介绍：vmlinux、zImage、zbImage、image、uImage等

一、背景 Linux内核是整个Linux操作系统的核心部分&#xff0c;它是一个负责与硬件直接交互的软件层&#xff0c;并且提供多种服务和接口&#xff0c;让用户程序能够方便地使用硬件资源。 当我们编译自定义内核时&#xff0c;可以将其生成为以下内核映像之一&#xff1a;vmli…
阅读更多...
【Matplotlib作图-3.Ranking】50 Matplotlib Visualizations, Python实现，源码可复现

【Matplotlib作图-3.Ranking】50 Matplotlib Visualizations, Python实现，源码可复现

目录 03 Ranking 3.0 Prerequisite 3.1 有序条形图(Ordered Bar Chart) 3.2 棒棒糖图(Lollipop Chart) 3.3 点图(Dot Plot) 3.4 斜率图(Slope Chart) 3.5 杠铃图(Dumbbell Plot) References 03 Ranking 3.0 Prerequisite Setup.py # !pip install brewer2mpl import n…
阅读更多...
短视频拍摄的几个必要手法！

短视频拍摄的几个必要手法！

如果说视频脚本是制作视频的基础&#xff0c;那么视频拍摄则是视频制作的关键。有了清晰稳定的视频素材&#xff0c;我们才能创作出清晰完整的视频画面。 那么如何拍摄出一个优质清晰稳定的视频画面呢&#xff1f;接下来带大家来学习下视频拍摄的五大技巧。 一、构图是关键 …
阅读更多...
最新文章

Copyright @ 2022~2023