探索数据结构：双向链表的灵活优势


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 前言

前面我们学习了单链表，它解决了顺序表中插入删除需要挪动大量数据的缺点。但同时也有仍需改进的地方，比如说：我们有时候需要寻找某个节点的前一个节点，对于单链表而言只能遍历，这样就可能造成大量时间的浪费。为了解决这个问题，我们就要学习今天的主角——带头双向循环链表。

2. 双向链表的功能

  1. 初始化顺序表中的数据。
  2. 对顺序表进行尾插(末尾插入数据)。
  3. 对顺序表进行头插(开头插入数据)。
  4. 对顺序表进行头删(开头删除数据)。
  5. 对顺序表进行尾删(末尾删除数据)。
  6. 对顺序表就像查找数据。
  7. 对顺序表数据进行修改。
  8. 任意位置的删除和插入数据。
  9. 打印顺序表中的数据。
  10. 销毁顺序表。

3. 双向链表的定义

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

typedef int LTDataType;
typedef struct DoubleList
{
	struct DoubleList* prev;//指向前一个节点
	LTDataType data;
	struct DoubleList* next;//指向下一个节点
}DListNode;

4. 双向链表的功能

4.1 初始化双向链表

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

(1) 创建头结点
DListNode* DLNodeCreat(LTDataType x)
{
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		return NULL;
	}
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
(2) 初始化

初始化将头节点的前后指针都指向自己，并将数值至为-1。

DListNode* InitDList()
{
	DListNode* phead = DLNodeCreat(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
(3) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.2 双向链表尾插

因为我们实现的双向链表存在头节点，所以我们不需要像实现单链表一样先判断链表是否为空。

(1) 代码实现
void DListPushBack(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* tail = ptr->prev;
	DListNode* newnode = DLNodeCreat(x);
	tail->next = newnode;
	newnode->prev = tail;
	ptr->prev = newnode;
	newnode->next = ptr;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.3 双向链表头插

因为带头双向循环链表的特性，即使只有头节点进行头插，代码实现也是相同的。

(1) 代码实现
void DListPushFront(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* next = ptr->next;
	DListNode* newnode = DLNodeCreat(x);
	ptr->next = newnode;
	newnode->prev =ptr;
	newnode->next = next;
	next->prev = newnode;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.4 双向链表尾删

有了循环找尾节点也十分容易，双向链表尾删自然并不困难。但是需要防止删除头节点。

(1) 代码实现
void DListPopBack(DListNode* ptr)
{
	assert(ptr);
	assert(ptr->next != ptr);//放置删除头节点
	DListNode* tail = ptr->prev;
	DListNode* tailprev = tail->prev;
	free(tail);
	tail == NULL;
	tailprev->next = ptr;
	ptr->prev = tailprev;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.5 双向链表头删

头删与尾删一样，都需要防止删除头节点。

(1) 代码实现
void DListPopFront(DListNode* ptr)
{
	assert(ptr);
	assert(ptr->next != ptr);
	DListNode* phead = ptr->next;
	DListNode* pheadnext = phead->next;
	free(phead);
	ptr->next = pheadnext;
	pheadnext->prev = ptr;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.6 双向链表查找

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

(1) 代码实现
DListNode* DListFind(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.7 修改双向链表

我们可以结合双向链表的查找，对双向链表进行修改。

(1) 代码实现
void DListModify(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	assert(ptr != pos);//防止对头节点操作
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		if (cur == pos)
		{
			cur->data = x;
		}
		cur = cur->next;
	}
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.8 双向链表指定插入数据

随机插入数据可以分为：向前插入与向后插入。

(1) 向前插入
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	DListNode* newnode = DLNodeCreat(x);
	DListNode* prev = pos->prev;
	newnode->prev = prev;
	newnode->next = pos;
	prev->next = newnode;
	pos->prev = newnode;
}
(2) 向后插入
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	DListNode* newnode = DLNodeCreat(x);
	DListNode* next = pos->next;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;
	pos->next = newnode;
}
(3) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.9 指定位置删除数据

任意删除也需要放置删除头节点，并且因为其特点只需要一个参数就能完成该操作。

(1) 代码实现
void DListErase(DListNode* pos)
{
	assert(pos);
	assert(pos != pos->next);
	pos->prev->next = pos -> next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.10 打印双向链表

打印双向链表只需将循环之前的数据全部打印即可。

(1) 代码实现
void DLTPrint(DListNode* ptr)
{
	assert(ptr);
	printf("guard");
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		printf("<==>%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.11 销毁双向链表

(1) 代码实现
void DListDestroy(DListNode* ptr)
{
	assert(ptr);
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		DListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(ptr);
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

5. 完整代码

5.1 DList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct DoubleList
{
	struct DoubleList* prev;//指向前一个节点
	LTDataType data;
	struct DoubleList* next;//指向下一个节点
}DListNode;
DListNode* InitDList();//初始化
void DListPushBack(DListNode* ptr, LTDataType x);//尾插
void DLTPrint(DListNode* ptr);//打印
void DListPushFront(DListNode* ptr, LTDataType x);//头插
void DListPopBack(DListNode* ptr);//尾删
void DListPopFront(DListNode* ptr);//头删
DListNode*DListFind(DListNode* ptr, LTDataType x);//查找
void DListModify(DListNode* ptr, DListNode* pos);//修改
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x);//任意位置之前插入
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x);//任意位置之后插入
void DListErase(DListNode* pos);//任意位置删除
void DListDestroy(DListNode* ptr);//销毁双向链表

5.2 DList.c

#include"DoubleList.h"
DListNode* DLNodeCreat(LTDataType x)
{
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		return NULL;
	}
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
DListNode* InitDList()
{
	DListNode* phead = DLNodeCreat(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
void DListPushBack(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* tail = ptr->prev;
	DListNode* newnode = DLNodeCreat(x);
	tail->next = newnode;
	newnode->prev = tail;
	ptr->prev = newnode;
	newnode->next = ptr;
}
void DListPushFront(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* next = ptr->next;
	DListNode* newnode = DLNodeCreat(x);
	ptr->next = newnode;
	newnode->prev =ptr;
	newnode->next = next;
	next->prev = newnode;
}
void DListPopBack(DListNode* ptr)
{
	assert(ptr);
	assert(ptr->next != ptr);//放置删除头节点
	DListNode* tail = ptr->prev;
	DListNode* tailprev = tail->prev;
	free(tail);
	tail == NULL;
	tailprev->next = ptr;
	ptr->prev = tailprev;
}
void DListPopFront(DListNode* ptr)
{
	assert(ptr);
	assert(ptr->next != ptr);
	DListNode* phead = ptr->next;
	DListNode* pheadnext = phead->next;
	free(phead);
	ptr->next = pheadnext;
	pheadnext->prev = ptr;
}
DListNode* DListFind(DListNode* ptr, LTDataType x)
{
	assert(ptr);
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void DListModify(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	assert(ptr != pos);//防止对头节点操作
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		if (cur == pos)
		{
			cur->data = x;
		}
		cur = cur->next;
	}
}
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	DListNode* newnode = DLNodeCreat(x);
	DListNode* prev = pos->prev;
	newnode->prev = prev;
	newnode->next = pos;
	prev->next = newnode;
	pos->prev = newnode;
}
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x)
{
	assert(ptr);
	DListNode* newnode = DLNodeCreat(x);
	DListNode* next = pos->next;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;
	pos->next = newnode;
}
void DListErase(DListNode* pos)
{
	assert(pos);
	assert(pos != pos->next);
	pos->prev->next = pos -> next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
void DLTPrint(DListNode* ptr)
{
	assert(ptr);
	printf("guard");
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		printf("<==>%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void DListDestroy(DListNode* ptr)
{
	assert(ptr);
	DListNode* cur = ptr->next;
	while (cur != ptr)
	{
		DListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(ptr);
}

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

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

相关文章

第110讲：Mycat实践指南：指定Hash算法分片下的水平分表详解

第110讲：Mycat实践指南：指定Hash算法分片下的水平分表详解

文章目录 1.应用指定Hash算法分片的概念2.使用应用指定Hash算法分片对某张表进行水平拆分2.1.在所有的分片节点中创建表结构2.2.配置Mycat实现应用指定Hash算法分片的水平分表2.2.1.配置Schema配置文件2.2.2.配置Rule分片规则配置文件2.2.3.配置Server配置文件2.2.4.重启Mycat …
阅读更多...
什么牌子的蓝牙耳机质量好？2024年精选机型，真实体验分享

什么牌子的蓝牙耳机质量好？2024年精选机型，真实体验分享

​对于新手来说&#xff0c;真无线蓝牙耳机的选购可能显得有些复杂。网络上有许多关于蓝牙耳机品牌、音质、舒适度的讨论。我整理了五款佩戴舒适且音质表现不错的真无线蓝牙耳机&#xff0c;希望能为你提供有价值的参考&#xff0c;不要错过哦&#xff01; 一、蓝牙耳机选购技巧…
阅读更多...
训练YOLOv8m时AMP显示v8n

训练YOLOv8m时AMP显示v8n

在训练Yolov8模型时&#xff0c;使用AMP&#xff08;Automatic Mixed Precision&#xff09;可以加速训练过程并减少显存的使用。AMP是一种混合精度训练技术&#xff0c;它通过将模型参数的计算转换为低精度&#xff08;如半精度&#xff09;来提高训练速度&#xff0c;同时保持…
阅读更多...
es 分词器详解

es 分词器详解

基本概念 分词器官方称之为文本分析器&#xff0c;顾名思义&#xff0c;是对文本进行分析处理的一种手段&#xff0c;基本处理逻辑为按照预先制定的分词规则&#xff0c;把原始文档分割成若干更小粒度的词项&#xff0c;粒度大小取决于分词器规则。 分词器发生的时期 1、分词…
阅读更多...
pytorch之诗词生成6--eval

pytorch之诗词生成6--eval

先上代码&#xff1a; import tensorflow as tf from dataset import tokenizer import settings import utils# 加载训练好的模型 model tf.keras.models.load_model(r"E:\best_model.h5") # 随机生成一首诗 print(utils.generate_random_poetry(tokenizer, model)…
阅读更多...
微信公众号测试号里面显示若依前端页面

微信公众号测试号里面显示若依前端页面

内网穿透 注册购买内网穿透隧道 https://natapp.cn/ 启动成功 这样就绑定你的本地启动项目 微信公众测试号配置 注册微信公众号测试号 获取access_token&#xff0c;AppID与appsecret 调用微信官方接口生成access_token&#xff08;AppID和AppSecret可在“微信公众平台-设置…
阅读更多...
C++ STL库的基本用法

C++ STL库的基本用法

目录 vector set queue priority_queue(堆)优先队列 大根堆 小根堆 map unordered_map vector vector<int> heap;//一维数组 for(int i1;i<10;i){heap.push_back(i); } heap.push_back();//元素插入尾部 heap.pop_back();//弹出尾部元素 heap.empty();// 判…
阅读更多...
StarRocks——滴滴的极速多维分析实践

StarRocks——滴滴的极速多维分析实践

背景 滴滴集团作为生活服务领域的头部企业&#xff0c;其中橙心优选经过一年多的数据体系建设&#xff0c;逐渐将一部分需要实时交互查询&#xff0c;即席查询的多维数据分析需求由ClickHouse迁移到了StarRocks中&#xff0c;接下来以StarRocks实现的漏斗分析为例介绍StarRocks…
阅读更多...
kafka 管理工具 Offset Explorer 使用

kafka 管理工具 Offset Explorer 使用

一、连接 二、查询数据 三、插入测试数据
阅读更多...
突飞猛进，智能饮品机器人如何助力实体经济？

突飞猛进，智能饮品机器人如何助力实体经济？

近日&#xff0c;财务部公布了2024年第一季度及全年财报。数据显示&#xff0c;连锁品牌增长速度惊人&#xff0c;这其中不得不提到智能饮品机器人的使用&#xff0c;为不同的品牌门店拼速度、抢点位立下了不小的功劳&#xff0c;那么智能饮品机器人到底如何助力各门店&#xf…
阅读更多...
工作中Git如何切换远程仓库地址

工作中Git如何切换远程仓库地址

工作中Git如何切换远程仓库地址 部门之前的仓库不用了&#xff0c;重新建了一个仓库&#xff0c;但是上传代码还是上传到了之前的仓库里面了&#xff0c;所以得进行修改&#xff0c;下面将修改地址的方法进行操作。 方法一、直接修改远程仓库地址 查看当前远程仓库地址 git …
阅读更多...
LLM - 大语言模型(LLM) 概述

LLM - 大语言模型(LLM) 概述

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://blog.csdn.net/caroline_wendy/article/details/136617643 大语言模型(LLM, Large Language Model)的发展和应用是一个非常广泛的领域&#xff0c;涉及从早期的统计模型到现代基于深度学…
阅读更多...
Bugku MISC做题笔记

Bugku MISC做题笔记

简单套娃DX 这一题需要对png图片的结构有所了解。详细可参考https://www.w3.org/TR/png/ 幸好每一张图片只有一个错误&#xff0c;逐步调试&#xff0c;就可以发现所有错误&#xff0c;修正即可。具体错误参看python程序中的注释&#xff1a; import ossrc_dir .\\XD\\ de…
阅读更多...
鸿蒙开发（八）添加常用控件（下）

鸿蒙开发（八）添加常用控件（下）

添加控件的文章分成了上下两篇&#xff0c;上篇介绍了文本显示、文本输入、按钮、图片、单选框、切换按钮这六种常用控件&#xff0c;本篇继续介绍其他几种很重要但略微复杂的控件。 鸿蒙系列上一篇&#xff1a; 鸿蒙开发&#xff08;七&#xff09;添加常用控件&#xff08;…
阅读更多...
【数据结构】串 解析+完整代码（求子串、比大小、定位操作）

【数据结构】串 解析+完整代码（求子串、比大小、定位操作）

1.串的实现 1.1 串的定义 定义 串&#xff0c;即字符串&#xff0c;是由零个或多个字符组成的有限序列。 串是一种特殊的线性表&#xff0c;数据元素间呈线性关系。 空串&#xff1a;串长度为0时&#xff1b;子串&#xff1a;串中任意个连续的字符组成的子序列&#xff1b;主串…
阅读更多...
ConcurrentHashMap 为什么不能插入 null？

ConcurrentHashMap 为什么不能插入 null？

1、典型回答 简单来说&#xff0c;ConcurrentHashMap 不允许插入 null 值是JDK 源码规定的&#xff0c;如下源码所示(此源码基于JDK 1.8)&#xff1a; 从上述源码可以看出&#xff0c;在添加方法的第一句就加了判断&#xff1a;如果 key 值为 null 或者是 value 值为 null&…
阅读更多...
Spring Cloud Alibaba微服务从入门到进阶（一）（SpringBoot三板斧、SpringBoot Actuator）

Spring Cloud Alibaba微服务从入门到进阶（一）（SpringBoot三板斧、SpringBoot Actuator）

Springboot三板斧 1、加依赖 2、写注解 3、写配置 Spring Boot Actuator Spring Boot Actuator 是 Spring Boot 提供的一系列用于监控和管理应用程序的工具和服务。 SpringBoot导航端点 其中localhost:8080/actuator/health是健康检查端点&#xff0c;加上以下配置&#xf…
阅读更多...
基于PHP构建的HTML5点餐系统的设计13.91

基于PHP构建的HTML5点餐系统的设计13.91

随着互联网时代的发展&#xff0c;人们的生活方式正在发生改变。传统的餐饮行业也正在发生变革。人们不再满足过去的点餐方式&#xff0c;需要更好的体验。本课题旨在结合点餐系统的技术优势&#xff0c;设计一个能够方便顾客与商家&#xff0c;并且节约人力成本以及可以很好地…
阅读更多...
中国金融统计年鉴、中国保险统计年鉴、中国人口与就业统计年鉴、国民经济和社会发展公报、中国劳动统计年鉴

中国金融统计年鉴、中国保险统计年鉴、中国人口与就业统计年鉴、国民经济和社会发展公报、中国劳动统计年鉴

数据下载链接&#xff1a;百度云下载链接 统计年鉴是指以统计图表和分析说明为主&#xff0c;通过高度密集的统计数据来全面、系统、连续地记录年度经济、社会等各方面发展情况的大型工具书来获取统计数据资料。 统计年鉴是进行各项经济、社会研究的必要前提。而借助于统计年…
阅读更多...
Java代码基础算法练习---2024.3.14

Java代码基础算法练习---2024.3.14

其实这就是从我学校的资源&#xff0c;都比较基础的算法题&#xff0c;先尽量每天都做1-2题&#xff0c;练手感。毕竟离我真正去尝试入职好的公司&#xff08;我指的就是中大厂&#xff0c;但是任重道远啊&#xff09;&#xff0c;仍有一定的时间&#xff0c;至少要等我升本之后…
阅读更多...
最新文章

Copyright @ 2022~2023