在面试的时候遇到过这样一个问题，让我有点懵逼
相较之下，我们都知道数组的查询和替换的效率高，而链表的删除和增加效率高
数组查改效率高的原因是数组的内存地址是连续的，所以读取每个元素的时间周期更短、更快（还有一个原因是数组使用的内存是CPU缓存里面的，而链表使用
的是堆空间里面分散的内存，CPU缓存里面的时钟周期比堆空间里面的时钟周期小）
链表删除和增加效率高是因为因为链表的存储结构，数组增删需要把后面的所有元素都往后移一个位置，而链表不需要
但是，不管是数组还是链表，删除和增加一个元素之前都需要先使用查询操作，即先遍历一遍，确定元素的位置。
那么问题来了：
1、数组的查询效率高，但是插入一个元素效率低
2、链表的查询效率低，但是插入一个元素效率高
又怎么能肯定地说链表增删效率比数组高呢？
其实具体谁的效率高，和数组（链表）的长度有关系
在靠前的位置插入数据，链表效率较高，在靠后位置插入数据，数组效率较高
更具体的描述靠前和靠后的位置：
当数组（链表）的长度小于一万时，大概前20%的位置是属于靠前的，
当数组（链表）的长度达到百万级别时，大概前10%的位置是靠前的。
所以综合来说，在增删方面的效率比较上，数组有八九成胜算，而链表只有一到两成
现在再回答开头的问题：数组和链表尾部插入数据那个效率高？
答案是数组
原文：https://www.cnblogs.com/-citywall123/p/12747069.html