ArrayList 和linkedList 是 List 接口的两种不同实现，并且两者都不是线程安全的。
在我们初学的时候，总是把这两个有以下的定义：
ArrayList底层是数组，增删慢，查找快。
linkedList底层是双向链表，增删快，查找慢。
可具体情况真的是这样吗，或者换句话说这样子描述真的准确么，其实不然，本篇文章将会带你仔细探讨二者的区别。
首先我们先来准确说一下两者的具体特点，然后再逐一分析：
ArrayList：
1.基于数组，需要连续内存
2. 随机访问快（可以根据下标访问）
3.尾部插入和删除性能可以，其他的头部中间插入删除慢（数组扩容的问题因为次数不多影响不大所以不考虑）
4.可以CPU缓存，利用局部性原理。
linkedList：
1.基于双向链表，不需要连续内存
2.随机访问慢（需要迭代遍历）
3.头尾插入删除性能高，中间插入删除性能慢，
4.占内存很多
以上就是二者分别的特点，二者底层数据结构数组和双向链表相信大家应该清楚其中的区别，那么接下来我们从随机访问开始进行描述，连续内存也会在下面提到。
随机访问：首先我们来解释，为什么ArrayList随机访问快而linkedList随机访问慢呢，这是因为连续内存的原因，ArrayList连续内存也就意味着如果知道了第一个值的内存地址时，那我们就可以很方便的计算出后面任意一个地址值的索引，我们通过一张图来理解：
我们假设ArrayList的1的元素地址是0，里面都是整数，整数的大小一个整数占四个字节，如果我们要访问第5个元素也就是索引为4的元素，我们可以直接计算出他的地址，4*5+0(一个整数四个字节，查找第五个整数所以4x5，0是初始值)。这样子直接去找20就可以找到5元素的地址了。
而链表则就不同了，它只能记录相邻的元素的索引，也就是next的指向值，所以想找5我们必须通过1找2，通过2找3，最后才能找到5，它需要去遍历每个元素从而找到我们需要找的值。同样我们也可以通过JAVA源代码去看一下二者的区别：
通过源代码我们可以看出，ArrayList中实现了一个RandomAccess的接口，而linkedList中并没有实现这个接口。当我们查看这个接口时会发现这个接口里面是没有任何方法的，那这个接口代表什么意思呢，书面翻译就是随机访问，jdk底层中它在读取的时候会看你有没有实现这个接口，如果实现的话就可以通过下标去找相应的值，如果没有实现此接口的话，那么就需要通过迭代器去一个一个的找。举个例子，如果我们的List实现了RandomAccess接口的话我们可以通过一下方式去得到：
for (int i = 0; i < arrayList.size(); i++) {
arrayList.get(i);
}
但如果没有实现此接口的话就需要通过迭代器代码实现：
for(Iterator i =linkedList.iterator();i.hasNext()){
i.next();
}
如果你们想测试一下二者具体的随机访问快慢的差距，可以自己写代码去测试一下，这里我就不一一描述了，ArrayList速度比linkedList快的还是挺多的。
关于二者的查询和插入删除：为什么在文章开头说查询快慢是错的呢，这是因为查询代表的是指通过内容去查找相对应的位置，而不是通过随机访问去查找，所以如果通过内容去查找的话，二者的时间是一样的，都需要去遍历，时间复杂度都是O(N)，换句话说其实它俩都不适合做查找(不如HashMap，TreeMap)。
再来说删除和插入：ArrayList如果仅仅是尾部的插入和删除的话，速度是非常快的，因为不需要去 修改其它值，直接在后面插入即可，如果遇到扩容的时候就会稍微慢一些，因为涉及到拷贝数组，但其实从整体上去看，影响也是微乎其微，所以也是我们所说的不考虑的原因。而如果在头部中部插入的话，它会涉及到数据的移动，有一个copy的操作，越靠近头部需要copy的数组越多，所以这就是它慢的原因。而linkedList它是头尾插入快，中间插入非常的慢，甚至比ArrayList还要慢，所以其实我们用ArrayList的次数要比linkedList要多的多。下图是二者插入10000个数据的时间：
我用的系统计时来对比二者的区别，可以看出头部插入linkedList要比ArrayList快的多，但中间插入却比ArrayList慢更多，而尾部插入二者相差不大。代码如下：
import java.util.ArrayList;
import java.util.linkedList;
public class Test {
public static void main(String[] args) {
extracted();
extracted1();
extracted2();
}
private static void extracted2() {
ArrayList arrayList = new ArrayList<>();
linkedList linkedList = new linkedList<>();
System.out.println("中间插入:");
long l = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
int b = i >> 1;
arrayList.add(b, i);
}
long end = System.currentTimeMillis() - l;
System.out.println("ArrayList: " + end);
long l1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
int b = i >> 1;
linkedList.add(b, i);
}
long end1 = System.currentTimeMillis() - l1;
System.out.println("linkedList: " + end1);
}
private static void extracted1() {
ArrayList arrayList = new ArrayList<>();
linkedList linkedList = new linkedList<>();
System.out.println("尾插:");
long l = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long end = System.currentTimeMillis() - l;
System.out.println("ArrayList: " + end);
long l1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.addLast(i);
}
long end1 = System.currentTimeMillis() - l1;
System.out.println("linkedList: " + end1);
}
private static void extracted() {
ArrayList arrayList = new ArrayList<>();
linkedList linkedList = new linkedList<>();
System.out.println("头插:");
long l = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(0, i);
}
long end = System.currentTimeMillis() - l;
System.out.println("ArrayList: " + end);
long l1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.addFirst(i);
}
long end1 = System.currentTimeMillis() - l1;
System.out.println("linkedList: " + end1);
}
}
关于CPU缓存和局部原理：
在讲局部原理之前我们先来介绍一下CPU缓存的作用：
当我们在计算a+b的值的时候，如果直接给CPU操作的话，它会涉及到一个读取和写入的过程，它会先读取a和b的值，在进行写入，也就是说把1和2传递给CPU，CPU通过计算后才可以把3传给c这个值，这个过程是非常耗时间的，所以才会在CPU和内存之间加一个CPU缓存。那么CPU缓存是如何提高性能的呢，首先CPU缓存也会去把a和b的值拿过来，这一步是没有任何节省时间的，但当a和b的值存进CPU缓存中时，下一次在用到a和b就不需要再去内存中读取a和b的值了，就可以直接从CPU缓存中拿来用，同时CPU拿到CPU缓存里的值，计算完也是写入CPU缓存，等待CPU缓存集合起来一起返还给内存，这就是节省时间的原因。接下来我们介绍局部原理。
在内存往CPU缓存里存储的时候，内存会把需要存储的数据以及该数据相邻的数据都存入缓存中去，这也是为什么局部原理可以节省时间的原因：如下图
那为什么链表没有局部原理呢？如下图：这是因为当链表要往缓存里存数据时，可能此时加载了1和其相邻的数据，但因为链表中并不是连续内存，整数1和2的地址值相差较远，所以当你想访问2的地址值时，你可能需要重新存一次2的数据。
如图所示，当1存入CPU缓存时，它相邻的数据并没有对应的值，所以当我们需要使用2时还需要重新存入CPU缓存一次。在代码中同样我们可以调用第三方库jol-core来测试二者的占用内存情况，这里就不实现说明了。结果大家也是清楚明了的。
小结：当我们在讲述描述二者不同时就不要再说增删慢查找快等类似的话了，随机访问，头尾，CPU，连续内存，局部原理等特点才是大家需要掌握的。另外大家也要明白RandomAccess接口的作用，当看到实现该接口后就要知道可以通过下标去找相应的值。再有随机访问和查询是两个不一样的方式，查询是通过具体数据的值查找，随机访问是通过索引查找。所以ArrayList整体来讲在速度和性能上都有优于linkedList的，也是为什么我们平时大多数都在用ArrayList的原因，它是连续内存，并且随机访问快，尾部增删快，可以利用CPU缓存，局部原理来减少内存使用。
以上则是ArrayList和linkedList的区别，在记忆过程中可以配合着代码的调式来记忆，更加巩固
