在初学Java的时候我们经常能看到这么一句话：ArrayList增删慢查询快，LinkedList增删快查询慢。但随着学习的不断深入，我们会发现这句话并不对，初学时看到这句话主要还是为了新手友好。
首先让我们了解一下为啥会有这个说法
ArrayList查询快：因为底层是数组，在查询的时候直接通过索引获取元素，所以查询快
ArrayList增删慢：往数组里某个位置增删元素的时候，是涉及元素的拷贝的，所以慢
LinkedList查询慢：要沿着链表上的节点慢慢找，当然慢
LinkedList增删快：只要断开改变链表中简单的改变节点指针的指向即可（如果对这里说的内容不太清楚，那你非常有必要好好学习一下数据结构）
嗯……，对于初学时来说听着简直太有道理了，感觉完全滴没有问题。终究还是当时太肤浅了。接下来看看具体哪些地方有问题。
到底是哪里不对呢？
以下就先来说说哪些地方不对。
ArrayList查询快，LinkedList查询慢
这一点比较简单，因为我们查询某一数据，我们根本就不会知道它那数据的索引，既然不知道索引，那ArrayList要查询某数据时一样得通过遍历去慢慢对比，这样的话就和 LinkedList 一样时间复杂度都为 O(N) 了。所以这句话是错的。
ArrayList 对所有位置元素的增删都要拷贝吗？
删除元素的时候必须传入索引，它的 remove 和 removeRange 方法都要传入索引，里面都用到了 System.arraycopy 这个方法
但是往最后末尾添加元素的时候，其实是不涉及拷贝的。
请看下面源码：
对于ArrayList来说，我们往里添元素的时候一般都是直接添，也就是直接添加到最后的，所以在我们使用的时候ArrayList的时候其实添加速度并不差。
简单的测试一下：
public static void main(String[] args) { ArrayList<String> arrayList = new ArrayList<>(); test(arrayList); LinkedList<String> linkedList = new LinkedList<>(); test(linkedList); } public static void test(List<String> list) { long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { list.add("哈哈哈"); } long end = System.currentTimeMillis(); System.out.println(end - start); }
结果发现，往尾部添加元素的时候 ArrayList 甚至比 LinkedList 的还要快，而且在以上代码中，我是把 test(arrayList); 放在 test(linkedList); 前面的，而代码刚开始执行时，JIT即时编译器还没有对 test 方法的代码进行处理，是跑的更慢的，但即使在这种情况下还是要远远快于 LinkedList （如果还没有学过 JVM 不知道啥是 JIT，上面那段话你就先理解成：在前面执行，还没预热好，发挥不出来，所以对于刚开始执行的代码来说会慢一些）
既然我们知道往尾部添加元素的时候 ArrayList 是比 LinkedList 快的，那我们就想啊，以后如果是基本往尾部加元素的话就用 ArrayList ，往中间部分加就用 LinkedList 好了。但是事情可能没有这么简单，让我们再测测：
public static void main(String[] args) { ArrayList<String> arrayList = new ArrayList<>(); test(arrayList); LinkedList<String> linkedList = new LinkedList<>(); test(linkedList); } public static void test(List<String> list) { long start = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { list.add(list.size() / 2, "哈哈哈"); } long end = System.currentTimeMillis(); System.out.println(end - start); }
这里我循环的次数比上一个测试多删了两个0，因为刚开始没删等了好久都没出结果
发现还是 ArrayList 完胜。离谱！！这 ArrayList 属实优点牛逼啊。
那这是为啥呢？（下面有一些是个人拙见，如有不对，希望大佬可以指教。）
对于 LinkedList 来说，它需要慢慢的沿着链表找到中间位置，再对相应节点（pre-cur-next 节点）指针进行调整，这个过程是比较费劲的。而且 LinkedList 还得把每个加入的数据包装成一个节点，相比于 ArrayList 来说也要麻烦一些
那 ArrayList 还要对添加位置前后的数据进行拷贝，那就不慢了吗？
确实是个问题，但是因为 ArrayList 底层是数组，它可以很好的配合 cpu 缓存 及 局部性原理来提高这个过程的速度。
- cpu 缓存：cpu 缓存的容量比内存小的多但是交换速度却比内存要快得多。cpu 缓存的出现主要是为了解决cpu 运算速度与内存读写速度不匹配的矛盾，因为cpu 运算速度要比内存读写速度快很多，这样会使cpu 花费很长时间等待数据到来或把数据写入内存。
- 局部性原理：当访问一块数据时，其相邻数据也很可能被访问，就一次性的把那一片的都读到 cpu 缓存中。
而链表就无法像数组那样利用这一点：就算会把你某个节点周围内存的数据一起读入，但你当前节点指向的空间可能并不是周围的数据，一起读进去的就不是你下次很可能用的数据了。所以它对于链表来说并无屁用。
而 ArrayList 正因为这个 cpu缓存+局部性原理 的帮助，使得数组拷贝的时候基本可以算是一大片一大片的拷贝的，所以速度非常地快。
到这里本文也就结束了，简单的总结一下：
- ArrayList 增删慢查询快，LinkedList增删快查询慢这句话可以说是不对的
- ArrayList 在很多方面都强于 LinkedList，即使是往中间部分加元素也是如此
