数组与链表,性能到底差多少?
2023-04-18 15:47:21 时间
本文转载自微信公众号「活在信息时代」,作者活在信息时代。转载本文请联系活在信息时代公众号。
同为基础的数据结构,数组与链表是最为常用的两个大类之一。
所谓数组,就是在内存中连续存储多个元素的结构,在内存中的分配也是连续的。数组中的元素通过数组下标进行访问,数组下标从0开始。
而链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。
根据两者的不同特点,我们可以看到,对于数组而言,数据是可以直接访问的,也就是说如果我想访问排序为6的数据,只需要眼看着访问地址为6的内存,就可以得到结果了。
而如果想访问链表中排序为6的数据,则需要从头开始,查找到第六个,才能获取到结果。
而插入数据的话,在数组中插入一条数据,则需要把插入之后的数据全部往后挪一遍。
而对于链表来说,插入一条数据,只需要将要插入位置的链解开,将前一节的下一个指针指向插入的节点,而将新节点的下一个指针指向原来的后一节就行了。非常简单。
那么,两者的效率空间会差多少呢?我们可以写个代码来验证一下。
我们知道,在Java中,ArrayList是基于数组实现的List,而LinkedList则是基于链表而实现的。那么,我们就可以写一段代码来测试一下他们的效率了。
插入代码如下:
数组:
链表:
查询代码如下:
数组:
链表:
在将index设置为100000的情况下,结果如下:
可见差距还是很明显的。
相关文章
- XAF新手入门 - XAF设计模式探讨
- XAF新手入门 - 数据字典示例
- XAF新手入门 - 类型信息子系统(Types Info Subsystem)
- Socket的长连接和短连接
- HTTP和HTTPS的区别
- 腾讯云简单使用
- SQL封装库学习笔记1.0
- C#解析mdb文件
- 使用EF Core更新与修改生产数据库
- .NET 6 跨服务器联表查询, MySql、Oracle、SqlServer等相互联表
- .NET下数据库的负载均衡(有趣实验)
- 002从零开始入门Entity Framework Core——DbContext生存期、配置和初始化
- 记一次EF+Mysql所遇到的事务不生效的的坑
- 根据温度、气压计算海拔高度
- .NET ORM 操作ClickHouse数据库
- 利用C#传输Json数据
- dotnet OpenXML 解析 PPT 图表 面积图入门
- 基于WPF重复造轮子,写一款数据库文档管理工具(一)
- net core天马行空系列-各大数据库快速批量插入数据方法汇总
- Winui3 FFmpeg.autogen 解析音频,使用NAudio播放;