数据结构:带索引的双链表IDL

IDL=indexed double list
在这里插入图片描述
如图,下方是一个双链表,上方是索引。索引储存为结构体数组,结构体内包括一个指针,和长度。

假设索引只有一个,这时,它应该指向双链表的中间,这样才能提高搜索效率。称为1/2索引。

索引数增加到两个,它们应该指向1/3处。

索引数为N,指向1/(N+1)处。

经过上述设计后,索引速度不会达到O(logn),但是却能提高不少。

设双链表的最大长度为100万,则索引长1000,每个索引项中的长度为1000。即,隔一千多项有一个指针。

增加数据时,重新计算索引数组中的指针和长度,这需要产生2K次修改。相比使用数组,对于有1M个元素的数组,在首部增加1项,会产生1M个数据移动。2K比1M小很多。

举例来说,索引中储存的长度是6-6-5-6,插入一项之后变成6-7-5-6。总长度为24,分4段,平均每段长度为6,所以,修改为6-6-6-6。这一过程可以叫做“索引的均衡化”。

查找数据时,在索引数组中采用二分法,先找到双链表的中间位置,比大小。然后在前半段或后半段之中继续查找。当索引数组中的前后两项相邻时,就启用双链表的遍历,一项接一项地查找。

上文中计算过,隔一千个元素有一个索引,所以,遍历的过程会持续1000次。这仍然比遍历整个双链表的100万次小很多。

总之,带索引的双链表和跳表相比,它们都能维持序列,进行范围搜索。IDL占用的空间比跳表少,速度也慢,这是“空间换时间”策略的折中方案。

之前的博客描述过“延迟序列”,这是另一个处理序列的方案。它更省内存,可以用于从内存里的红黑树,到硬盘上的数据结构(如B+树),的转换过程中的替代品。但是延迟序列不能访问相邻元素,IDL却可以。

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

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

相关文章

MyBatis 框架的两大缺点及解决方案

MyBatis 框架的两大缺点及解决方案 1. SQL 编写负担重1.1 缺点概述1.2 解决方案 2. 数据库移植性差2.1 缺点概述2.2 解决方案 💖The Begin💖点点关注,收藏不迷路💖 MyBatis 作为一款广受欢迎的 Java 持久层框架,尽管其…

吴恩达机器学习作业-ex7(主成分分析)

data1 导入库,读取数据,并进行可视化数据 import numpy as np import scipy.io as sio import matplotlib.pyplot as plt#读取数据 path "./ex7data1.mat" data sio.loadmat(path) # print(data.keys()) X data.get("X") # pri…

『C++实战项目 负载均衡式在线OJ』一、项目介绍与效果展示(持续更新)

文章目录 一、项目介绍二、开发环境三、第三方库四、相关技术五、项目整体框架代码目录框架 代码仓库连接 点击这里✈ 一、项目介绍 本项目是实现一个仿 leetcode 的 OJ (Online-Judge)系统。更准确的说应该称之为leetcode 的裁剪版。因为本项目只实现了leetcode中…

《计算机网络》(第8版)第9章 无线网络和移动网络 复习笔记

第 9 章 无线网络和移动网络 一、无线局域网 WLAN 1 无线局域网的组成 无线局域网提供移动接入的功能,可分为两大类:有固定基础设施的和无固定基础设 施的。 (1)IEEE 802.11 IEEE 802.11 是无线以太网的标准,是有固定…

【保姆级系列:锐捷模拟器的下载安装使用全套教程】

保姆级系列:锐捷模拟器的下载安装使用全套教程 1.介绍2.下载3.安装4.实践教程5.验证 1.介绍 锐捷目前可以通过EVE-NG来模拟自己家的路由器,交换机,防火墙。实现方式是把自己家的镜像导入到EVE-ng里面来运行。下面主要就是介绍如何下载镜像和…

【初阶数据结构题目】10. 链表的回文结构

链表的回文结构 点击链接做题 思路1:创建新的数组,遍历原链表,遍历原链表,将链表节点中的值放入数组中,在数组中判断是否为回文结构。 例如: 排序前:1->2->2->1 设置数组来存储链表&a…

1、爬⾍概述

1. 什么是爬虫? 爬虫(Web Crawler)是一种通过编写程序自动访问并提取互联网上数据的技术。爬虫可以帮助我们在浏览网页时自动收集和保存一些有用的数据,例如图片、视频和文本信息。简单来说,爬虫就是自动化的浏览器。…

react-native从入门到实战系列教程-React Native Elements

react-native的ui框架内网真的是屈指可数,能用的成熟的几乎找不到。不像web端的繁荣景象,可以用荒凉来形容不为过。 京东的nutui说也支持react-native,官网及其简陋。尝试了未成功运行,可能是项目类型不同,对比其他类型的ui库都分…

Flink中上游DataStream到下游DataStream的内置分区策略及自定义分区策略

目录 全局分区器GlobalPartitioner 广播分区器BroadcastPartitioner 哈希分区器BinaryHashPartitioner 轮询分区器RebalancePartitioner 重缩放分区器RescalePartitioner 随机分区器ShufflePartitioner 转发分区器ForwardPartitioner 键组分区器KeyGroupStreamPartitio…

【java基础】徒手写Hello, World!程序

文章目录 前提:java环境变量配置使用vscode编写helloworld解析 前提:java环境变量配置 https://blog.csdn.net/xzzteach/article/details/140869188 使用vscode编写helloworld code .为什么用code看下图 报错了!!!&…

样式与特效(3)——实现一个测算页面

这次我们使用前端实现一个简单的游戏页面,理论上可以增加很多玩法,,但是这里为了加深前端的样式和JS点击事件,用该案例做练习。 首先需要掌握手机端的自适应,我们是只做手机端玩家页面 。需要允许自适应手机端页面, 用…

24年电赛——自动行驶小车(H题)MSPM0G3507-编码电机驱动与通用PID

一、编码电机驱动 编码电机的详情可以查看此篇文章: stm32平衡小车--(1)JGB-520减速电机tb6612(附测试代码)_jgb520-CSDN博客 简单来说,编码电机的驱动主要是给一个 PWM 和一个正负级就能驱动。PWM 的大小…

9-springCloud集成nacos config

本文介绍spring cloud集成nacos config的过程。 0、环境 jdk 1.8maven 3.8.1Idea 2021.1nacos 2.0.3 1、项目结构 根项目nacos-config-sample下有两个module,这两个module分别是两个springboot项目,都从nacos中获取连接mysql的连接参数。我们开工。 …

羌活基因组--文献精读-36

The chromosome-scale assembly of the Notopterygium incisum genome provides insight into the structural diversity of coumarins 羌活(Notopterygium incisum)基因组的染色体级别组装为香豆素的结构多样性提供了新的见解 摘要 香豆素是由苯丙素途…

学生信息管理系统(Python+PySimpleGUI+MySQL)

吐槽一下 经过一段时间学习pymysql的经历,我深刻的体会到了pymysql的不靠谱之处; 就是在使用int型传参,我写的sql语句中格式化%d了之后,我在要传入的数据传递的每一步的去强制转换了,但是他还是会报错,说我…

决策树可解释性分析

决策树可解释性分析 决策树是一种广泛使用的机器学习算法,以其直观的结构和可解释性而闻名。在许多应用场景中,尤其是金融、医疗等领域,模型的可解释性至关重要。本文将从决策路径、节点信息、特征重要性等多个方面分析决策树的可解释性&…

k8s集群的资源发布方式(滚动/蓝绿/灰度发布)及声明式管理方法

目录 1.常见的发布方式 2.滚动发布 3.蓝绿发布 4.实现金丝雀发布(Canary Release) 5.声明式管理方法 1.常见的发布方式 蓝绿发布:两套环境交替升级,旧版本保留一定时间便于回滚优点:用户无感知,部署和回滚速度较…

如何通过前端表格控件实现自动化报表?

背景 最近伙伴客户的项目经理遇见一个问题,他们在给甲方做自动化报表工具,项目已经基本做好了,但拿给最终甲方,业务人员不太买账,项目经理为此也是天天抓狂,没有想到合适的应对方案。 现阶段主要面临的问…

chrome/edge浏览器插件开发入门与加载使用

同学们可以私信我加入学习群! 正文开始 前言一、插件与普通前端项目二、开发插件——manifest.json三、插件使用edge浏览器中使用/加载插件chrome浏览器中使用/加载插件 总结 前言 chrome插件的出现,初衷可能是为了方便用户更好地控制浏览器&#xff0c…

C++ | 类和对象(下)(static成员、友元、内部类、匿名对象)

目录 ​编辑 static成员 static性质简介 static属于整个类,属于所有对象 static成员的声明与定义 static函数 友元friend 友元特性简介 友元关系讲解 内部类 特性一 特性二 匿名对象 结语 static成员 static性质简介 static成员在类里面是非常独特的…