【数据结构】带头双向循环链表及其实现

目录

1.带头双向循环链表

2.带头双向循环链表实现

2.1初始化

2.2销毁

2.3头插

2.4链表打印

2.5头删数据

2.6尾插数据

2.7尾删数据

2.8链表判空 

2.9查找一个数据

2.10在pos位置前插入数据

2.11删除pos位置

2.12求链表的长度

2.顺序表和链表的比较

1.带头双向循环链表

我们已经实现了无头单向循环链表

带头双向链表结构如下：

对于无头单向非循环链表，其具有以下特点：

  • 第一个节点即为存储有效数据的节点
  • 每个节点有包括数据域和指针域，这个指针指向下一个节点
  • 空链表为NULL

对于带头双向循环链表，其具有以下特点

  • 第一个节点为哨兵头节点，其数据域不存储有效数据
  • 每个节点包含数据域和两个指针域prev和next，prev指针指向后一个节点，next指针指向前一个节点，对于哨兵头节点，其prev指针指向链表的尾节点，对于尾节点，其next指针指向哨兵头节点，因此形成了一个循环的结构
  • 空链表时链表包含一个哨兵头节点，如下图：

2.带头双向循环链表实现

2.1初始化

对于一个带头双向循环链表，初始化后其为有一个哨兵头节点的结构

即初始化需要动态开辟一个节点作为哨兵头节点，其具有以下结构

//初始化
LTNode* ListInit(LTNode** pphead)
{LTNode* guard = (LTNode*)malloc(sizeof(LTNode));//哨兵头节点if (guard == NULL){perror("malloc fail");exit(-1);}else{guard->next = guard;guard->prev = guard;return guard;}
}

2.2销毁

因为链表所有节点的空间都是动态开辟的，因此对链表进行操作后，为了避免内存泄漏，需要释放这些节点所占用的空间，销毁链表遍历释放每个节点即可，需要注意哨兵头节点也是动态开辟的空间，也需要释放

//销毁
void ListDestroy(LTNode* phead)
{assert(phead);//遍历释放每个节点LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//保存下一个节点free(cur);cur = next;}//释放哨兵头节点free(phead);phead = NULL;//参数为一级指针，形参的改变不影响实参
}

2.3头插

头插数据有两种情况：

1️⃣空链表时头插

2️⃣非空链表时头插

由上图可以发现：由于带头双向循环链表结构的特殊性，空链表头插和非空链表头插时操作相同

//创建节点
LTNode* BuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->prev = newnode->next = NULL;return newnode;}
//头插数据
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;}

2.4链表打印

为了方便调试，可以编写打印函数展示我们所创建的链表，遍历打印每个节点的数据域即可

//打印链表
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

2.5头删数据

头删数据需要判断链表是否为空，空链表则不能进行数据的删除

特殊情况分析：只有一个节点时头删

 由上图可以发现：仅有一个节点时的头删操作和一般情况下头删操作步骤相同

//头删数据
void ListPopFront(LTNode* phead)
{assert(phead);//空链表则不能删除assert(!ListEmpty(phead));LTNode* first = phead->next;//first为第一个有效数据节点phead->next = first->next;first->next->prev = phead;free(first);first = NULL;}

2.6尾插数据

尾插数据有两种情况：

1️⃣空链表时尾插

2️⃣非空链表时头插

由上图可以发现：空链表尾插和非空链表尾插时操作相同，所以不用分情况讨论

//尾插数据
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;//tail为原尾节点LTNode* newnode = BuyNode(x);tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;
}

2.7尾删数据

尾删数据需要判断链表是否为空，空链表则不能进行数据的删除

非空链删除

特殊情况分析：只有一个节点时尾删

 由上图可以发现：仅有一个节点时的尾删操作和一般情况下尾删操作步骤相同

//尾删数据
void ListPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;//tail为尾节点phead->prev = tail->prev;tail->prev->next = phead;
}

2.8链表判空 

当链表中只有哨兵头节点时，链表即为空

//判空
bool ListEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.9查找一个数据

从存储有效数据的第一个节点开始遍历链表，查找所给数据

如果找到了，则返回该节点的地址，返回地址也可以对该节点进行修改

遍历结束，没找到，则返回NULL

//查找一个数据
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);//遍历查找LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;//返回节点地址，可以进行修改}cur = cur->next;}return NULL;}

2.10在pos位置前插入数据

在pos之前插入数据，需要直到pos前一个节点的地址。在带头双向循环链表中，pos节点中prev指针域存储了前一个节点的地址，使插入数据更加方便，步骤如下：

特殊情况：空链表时，只能在哨兵头节点之前插入，且步骤与上述相同

需要函数调用者保证pos的有效性

//在pos之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* front = pos->prev;LTNode* newnode = BuyNode(x);front->next = newnode;newnode->prev = front;newnode->next = pos;pos->prev = newnode;
}

2.11删除pos位置

pos节点中既存储了其前一个节点的位置，又存储了其后一个节点的位置

删除pos位置：链表不为空时才能删除，链接其前后节点并释放pos节点即可

//删除pos位置
void ListErase(LTNode* phead, LTNode* pos)
{assert(phead);assert(pos);assert(!ListEmpty(phead));LTNode* front = pos->prev;LTNode* rear = pos->next;front->next = rear;rear->prev = front;free(pos);pos = NULL;
}

2.12求链表的长度

遍历链表统计节点个数即可 

//求链表的长度
int ListSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;int size = 0;while (cur != phead){++size;cur = cur->next;}return size;
}

2.顺序表和链表的比较

不同点顺序表链表
存储空间物理上一定连续逻辑上连续，物理上不一定连续
随机访问支持，且时间复杂度为O(1)不支持，访问任意元素的时间复杂度为O(N)
任意位置插入或删除元素需要挪动元素，效率低只需要修改指针的方向，效率较高
插入动态顺序表，空间不够时需要扩容随用随取，不存在容量的概念
应用场景元素高效存储，需要随机访问任意位置频繁插入或删除
缓存利用率高低

总结：

顺序表的优点：

  • 尾插和尾删的效率高
  • 元素通过下标访问，物理存储空间连续，支持随机访问

顺序表的缺点：

  • 头部插入和中间位置插入需要挪动元素，效率低
  • 扩容操作存在性能消耗和空间浪费

链表的优点：

  • 任意位置插入和删除的时间复杂度为O(N)，效率高
  • 按需申请和释放内存，不存在空间浪费

链表的缺点：

  • 不支持随机访问

扩展：

顺序表的优点：相对链表，CPU高速缓存命中率高

CPU执行指令，不会直接访问内存，通常为以下两步：

  1. 数据在三级缓存，命中，直接访问
  2. 若数据不在三级缓存，则先加载到缓存，再访问

顺序表结构使用数组实现：

如上图：要访问0x11223344中的数据，则从0x11223344开始的一段数据都加载进去缓存，加载多少取决于硬件

对于链表，因为其物理存储空间不连续，因此加载到缓存中的这一段数据中可能存在无效数据，导致缓存污染

 

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【python爬虫】4.爬虫实操（菜品爬取）

【python爬虫】4.爬虫实操（菜品爬取）

文章目录 前言项目&#xff1a;解密吴氏私厨分析过程代码实现&#xff08;一&#xff09;获取与解析提取最小父级标签一组菜名、URL、食材写循环&#xff0c;存列表 代码实现&#xff08;二&#xff09;复习总结 前言 上一关&#xff0c;我们学习了用BeautifulSoup库解析数据和…
阅读更多...
matlab的基本使用

matlab的基本使用

matlab的基本使用&#xff0c;可以参考如下的教程&#xff1a;matlab教程 本文针对基本内容进行记录。 matlab简介 MATLAB是美国MathWorks公司出品的商业数学软件&#xff0c;用于数据分析、无线通信、深度学习、图像处理与计算机视觉、信号处理、量化金融与风险管理、机器人&…
阅读更多...
Python学习笔记：正则表达式、逻辑运算符、lamda、二叉树遍历规则、类的判断

Python学习笔记：正则表达式、逻辑运算符、lamda、二叉树遍历规则、类的判断

1.正则表达式如何写&#xff1f; 序号实例说明1.匹配任何字符(除换行符以外)2\d等效于[0-9]&#xff0c;匹配数字3\D等效于[^0-9]&#xff0c;匹配非数字4\s等效于[\t\r\n\f]&#xff0c;匹配空格字符5\S等效于[^\t\r\n\f]&#xff0c;匹配非空格字符6\w等效于[A-Za-z0-9]&…
阅读更多...
大数据Flink简介与架构剖析并搭建基础运行环境

大数据Flink简介与架构剖析并搭建基础运行环境

文章目录 前言Flink 简介Flink 集群剖析Flink应用场景Flink基础运行环境搭建Docker安装docker-compose文件编写创建并运行容器访问Flink web界面 前言 前面我们分别介绍了大数据计算框架Hadoop与Spark,虽然他们有的有着良好的分布式文件系统和分布式计算引擎&#xff0c;有的有…
阅读更多...
java基础-----第八篇

java基础-----第八篇

系列文章目录 文章目录 系列文章目录一、Java类加载器二、双亲委托模型 一、Java类加载器 JDK自带有三个类加载器&#xff1a;bootstrap ClassLoader、ExtClassLoader、AppClassLoader。 BootStrapClassLoader是ExtClassLoader的父类加载器&#xff0c;默认负责加载%JAVA_HOME…
阅读更多...
自动驾驶攻城战，华为小鹏先亮剑

自动驾驶攻城战，华为小鹏先亮剑

点击关注 文&#xff5c;刘俊宏 编&#xff5c;苏扬、王一粟 本文为光锥智能x腾讯科技联合出品 2023年过半&#xff0c;城市NOA&#xff08;城市领航辅助驾驶&#xff09;的元年如预期中到来了吗&#xff1f; 8月25日&#xff0c;成都车展开幕&#xff0c;与4个月之前的上海…
阅读更多...
PyTorch深度学习遥感影像地物分类与目标检测、分割及遥感影像问题深度学习优化实践技术应用

PyTorch深度学习遥感影像地物分类与目标检测、分割及遥感影像问题深度学习优化实践技术应用

我国高分辨率对地观测系统重大专项已全面启动&#xff0c;高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成&#xff0c;将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB&#xff0c;遥感大数据时…
阅读更多...
华为云云服务器评测｜华为云云耀云服务器L实例使用教学

华为云云服务器评测｜华为云云耀云服务器L实例使用教学

文章目录 教学小故事 教学 华为云云耀云服务器L实例是一款提供高效、可靠、安全的基础设施服务的云服务器。下面是使用教学&#xff1a; 登录华为云官网。 测评产品链接&#xff1a;https://www.huaweicloud.com/product/hecs-light.html 进入云耀云服务器管理控制台&#xf…
阅读更多...
Qt 查找文件夹下指定类型的文件及删除特定文件

Qt 查找文件夹下指定类型的文件及删除特定文件

一 查找文件 bool MyXML::findFolderFileNames() {//指定文件夹名QDir dir("xml");if(!dir.exists()){qDebug()<<"folder does not exist!";return false;}//指定文件后缀名&#xff0c;可指定多种类型QStringList filter("*.xml");//指定…
阅读更多...
算法竞赛备赛之数学知识训练提升，暑期集训营培训

算法竞赛备赛之数学知识训练提升，暑期集训营培训

1.质数 在大于1的整数&#xff0c;如果质包含1和本身这两个约数&#xff0c;就称之为素数/质数。 1.质数的判定&#xff08;试除法&#xff09; 优化后的&#xff1a; #include<iostream> #include<algorithm> ​ using namespace std; ​ bool is_prime(int n…
阅读更多...
Python基础篇（17）：模块与包

Python基础篇（17）：模块与包

一、as 关键字的使用 1、as 关键字的作用&#xff1a;给导入的模块取别名 import 测试1 as Test_1 import 测试2 as Test_2Test_1.say_hello() Test_2.say_hello() 二、if __name__ __main__ 1、作用 测试当前模块所编写的代码块&#xff0c;根据业务自主选择需要运行的代…
阅读更多...
二叉树的构建及遍历

二叉树的构建及遍历

目录 题目题目要求示例 解答方法一、实现思路时间复杂度和空间复杂度代码 方法二、实现思路时间复杂度和空间复杂度代码 题目 二叉树的构建及遍历 题目要求 题目链接 示例 解答 方法一、 先构建二叉树&#xff0c;再中序遍历。 实现思路 按照给出的字符串创建二叉树&am…
阅读更多...
华为云云服务器评测｜基于华为云云耀云服务器L实例开展性能评测，例如 MySQL、Clickhouse、Elasticsearch等等

华为云云服务器评测｜基于华为云云耀云服务器L实例开展性能评测，例如 MySQL、Clickhouse、Elasticsearch等等

在当今云计算时代&#xff0c;越来越多的企业和个人开始选择将应用部署在云服务器上&#xff0c;以便更好地满足高性能、可靠性和可扩展性等需求。而华为云云耀云服务器L实例不仅提供了高性能和可靠性的计算和存储资源&#xff0c;而且具有灵活和高效的成本控制&#xff0c;深受…
阅读更多...
C语言基础之——结构体

C语言基础之——结构体

前言&#xff1a;小伙伴们又见面啦&#xff0c;那么本篇文章&#xff0c;我们就将对C语言基础知识的最后一个章节——结构体展开讲解。 世上无难事&#xff0c;只要肯攀登&#xff01; 目录 一.什么是结构体 二.结构体讲解 1.结构体的声明和变量的定义 2.结构体成员的类型…
阅读更多...
8. 损失函数与反向传播

8. 损失函数与反向传播

8.1 损失函数 ① Loss损失函数一方面计算实际输出和目标之间的差距。 ② Loss损失函数另一方面为我们更新输出提供一定的依据。 8.2 L1loss损失函数 ① L1loss数学公式如下图所示&#xff0c;例子如下下图所示。 import torch from torch.nn import L1Loss inputs torch.tens…
阅读更多...
mysql‘逻辑删除‘和‘唯一索引‘冲突的解决方案

mysql‘逻辑删除‘和‘唯一索引‘冲突的解决方案

一、冲突出现原因 在user表中将name字段设置唯一索引&#xff0c;添加逻辑删除字段del_flag&#xff08;1为删除&#xff0c;0为未删除&#xff09;之后&#xff0c;将name张四的字段删除&#xff0c;再添加一个name张四的记录则会出现冲突 二、解决 1.设置唯一索引组&#x…
阅读更多...
【数学建模】清风数模正课7 多元线性回归模型

【数学建模】清风数模正课7 多元线性回归模型

多元线性回归分析 回归分析就是&#xff0c;通过研究自变量X和因变量Y的相关关系&#xff0c;来解释Y的形成机制&#xff0c;从而达到通过X去预测Y的目的。 所以回归分析需要完成三个使命&#xff0c;首先是识别重要变量&#xff0c;其次是判断正负相关&#xff0c;最后是估计…
阅读更多...
opencv-人脸识别

opencv-人脸识别

对https://blog.csdn.net/weixin_46291251/article/details/117996591这哥们代码的一些修改 import cv2 import numpy as np import os import shutil import threading import tkinter as tk from PIL import Image, ImageTkchoice 0# 首先读取config文件&#xff0c;第一行…
阅读更多...
反射、Class

反射、Class

Class 获取实例化的三种方式
阅读更多...
深入理解协同过滤算法及其实现

深入理解协同过滤算法及其实现

导语 个性化推荐系统在现代数字时代扮演着重要的角色&#xff0c;协助用户发现他们可能感兴趣的信息、产品或媒体内容。协同过滤是个性化推荐系统中最流行和有效的算法之一。 目录 协同过滤算法的原理 基于用户的协同过滤&#xff08;User-Based Collaborative Filtering&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023