数组与链表,性能到底差多少?

同为基础的数据结构,数组链表是最为常用的两个大类之一。,所谓数组,就是在内存中连续存储多个元素的结构,在内存中的分配也是连续的。数组中的元素通过数组下标进行访问,数组下标从0开始。,数组与链表,性能到底差多少?,而链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。,数组与链表,性能到底差多少?,根据两者的不同特点,我们可以看到,对于数组而言,数据是可以直接访问的,也就是说如果我想访问排序为6的数据,只需要眼看着访问地址为6的内存,就可以得到结果了。,而如果想访问链表中排序为6的数据,则需要从头开始,查找到第六个,才能获取到结果。,而插入数据的话,在数组中插入一条数据,则需要把插入之后的数据全部往后挪一遍。,数组与链表,性能到底差多少?,而对于链表来说,插入一条数据,只需要将要插入位置的链解开,将前一节的下一个指针指向插入的节点,而将新节点的下一个指针指向原来的后一节就行了。非常简单。,数组与链表,性能到底差多少?,那么,两者的效率空间会差多少呢?我们可以写个代码来验证一下。,我们知道,在Java中,ArrayList是基于数组实现的List,而LinkedList则是基于链表而实现的。那么,我们就可以写一段代码来测试一下他们的效率了。,插入代码如下:,数组:,链表:,查询代码如下:,数组:,链表:,在将index设置为100000的情况下,结果如下:,数组与链表,性能到底差多少?,可见差距还是很明显的。

文章版权声明

 1 原创文章作者:cmcc,如若转载,请注明出处: https://www.52hwl.com/22515.html

 2 温馨提示:软件侵权请联系469472785#qq.com(三天内删除相关链接)资源失效请留言反馈

 3 下载提示:如遇蓝奏云无法访问,请修改lanzous(把s修改成x)

 免责声明:本站为个人博客,所有软件信息均来自网络 修改版软件,加群广告提示为修改者自留,非本站信息,注意鉴别

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年3月5日 上午12:00
下一篇 2023年3月7日 下午10:34