数组和链表尾部插入数据那个效率高
2023-09-14 08:56:53 时间
在面试的时候遇到过这样一个问题,让我有点懵逼
相较之下,我们都知道数组的查询和替换的效率高,而链表的删除和增加效率高
数组查改效率高的原因是数组的内存地址是连续的,所以读取每个元素的时间周期更短、更快(还有一个原因是数组使用的内存是CPU缓存里面的,而链表使用
的是堆空间里面分散的内存,CPU缓存里面的时钟周期比堆空间里面的时钟周期小)
链表删除和增加效率高是因为因为链表的存储结构,数组增删需要把后面的所有元素都往后移一个位置,而链表不需要
但是,不管是数组还是链表,删除和增加一个元素之前都需要先使用查询操作,即先遍历一遍,确定元素的位置。
那么问题来了:
1、数组的查询效率高,但是插入一个元素效率低
2、链表的查询效率低,但是插入一个元素效率高
又怎么能肯定地说链表增删效率比数组高呢?
其实具体谁的效率高,和数组(链表)的长度有关系
在靠前的位置插入数据,链表效率较高,在靠后位置插入数据,数组效率较高
更具体的描述靠前和靠后的位置:
当数组(链表)的长度小于一万时,大概前20%的位置是属于靠前的,
当数组(链表)的长度达到百万级别时,大概前10%的位置是靠前的。
所以综合来说,在增删方面的效率比较上,数组有八九成胜算,而链表只有一到两成
现在再回答开头的问题:数组和链表尾部插入数据那个效率高?
答案是数组
相关文章
- 数组、链表、队列、栈的区别和联系
- Java实现 LeetCode 706 设计哈希映射(数组+链表)
- 【二叉树】LeetCode 114. 二叉树展开为链表【中等】
- 【数组&双指针】LeetCode 142. 环形链表 II【中等】
- LeetCode(86):分隔链表
- 21. 合并两个有序链表
- 1019. 链表中的下一个更大节点
- C语言快速解决反转链表
- 二叉树的二叉链表存储
- 【SystemVerilog 之数据类型】~ 数据类型、Logic 类型、数组(定宽数组、动态数组、队列、关联数组、链表)
- LeetCode 430. 扁平化多级双向链表
- 【LeetCode】148. 排序链表
- 【LeetCode】环形链表
- 数据结构和算法 二、数组和链表