【面试：基础篇07:ArrayList与LinkedList源码分析及其性能对比】
01.简介
我们知道ArrayList是基于数组创建的，LinkedList是基于链表创建的，那么程序是如何判断并运行他们的呢，他们之间的性能对比又是怎么样的。
02.源码比较
ArrayList
我们查看ArrayList的源码
这里面==RandomAccess==接口值得我们注意，查看RandomAccess
我们发现RandomAccess接口没有任何内容
LinkedList
我们查看LinkedList的源码
我们发现LinkedList并没有实现RandomAccess接口
分析：
我们发现了 ArrayList源码中实现了RandomAccess接口，但是LinkedList并没有实现它。我们可以看到RandomAccess没有任何内容，它仅仅是作为ArrayList与LinkedList区分标记
如果实现了RandomAccess 则说明是ArrayList 程序会按照下标+1去寻值，如果没有实现则说明是LinkedList 程序就会按照指针寻址寻值
03.ArrayList性能与LinkedList性能对比
ArrayList与LinkedList的查性能对比：
代码：
public static void main(String[] args) {
int n = 1000;
for (int i=0;i<5;i++){
int[] list = new int[1000];
for (int j=0;j<n;j++){
list[j]= (int) (Math.random()*n);
}
// 把list数组的值存入 ArrayList与LinkedList
ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
LinkedList<Integer> Linked = new LinkedList<>(array);
//查性能
randomAccess(array,Linked,n/2);
// 插头部性能
// addFirst(array,Linked);
// 插尾部性能
// addLast(array,Linked);
// 插中间性能
// addMiddle(array,Linked,n/2);
}
}
// 获取ArrayLis与LinkedList的查方法 执行时间
private static void randomAccess(ArrayList<Integer> array, LinkedList<Integer> linked, int mid) {
StopWatch sw = new StopWatch();// spring的StopWatch类 用于获取程序执行时间
sw.start("ArrayList");
array.get(mid);
sw.stop();
sw.start("LinkedList");
linked.get(mid);
sw.stop();
System.out.println(sw.prettyPrint());
}结果
000005900 023% ArrayList
000020100 077% LinkedList000001200 013% ArrayList
000007700 087% LinkedList000001300 010% ArrayList
000011600 090% LinkedList000001500 013% ArrayList
000010300 087% LinkedList000001000 011% ArrayList
000008200 089% LinkedList
可以看出查的时候 ArrayList的速度明显比LinkedList要快的多
ArrayList与LinkedList的增性能对比：
因为增与删运行路径差不多 故我们只比较增方法
头部插入代码
public static void main(String[] args) {
int n = 1000;
for (int i=0;i<5;i++){
int[] list = new int[1000];
for (int j=0;j<n;j++){
list[j]= (int) (Math.random()*n);
}
ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
LinkedList<Integer> Linked = new LinkedList<>(array);
//查性能
// randomAccess(array,Linked,n/2);
// 插头部性能
addFirst(array,Linked);
// 插尾部性能
// addLast(array,Linked);
// 插中间性能
// addMiddle(array,Linked,n/2);
}
}
private static void addFirst(ArrayList<Integer> array,LinkedList<Integer> linked){
StopWatch sw = new StopWatch();
sw.start("ArrayList");
array.add(0,100);
sw.stop();
sw.start("LinkedList");
linked.addFirst(100);
sw.stop();
System.out.println(sw.prettyPrint());
}结果
000046500 072% ArrayList
000018400 028% LinkedList000003700 073% ArrayList
000001400 027% LinkedList000004200 078% ArrayList
000001200 022% LinkedList000004300 077% ArrayList
000001300 023% LinkedList000005000 078% ArrayList
000001400 022% LinkedList
我们可以看出在往头部插入数据时，LinkedList的速度明显优于ArrayList
尾部插入代码
public static void main(String[] args) {
int n = 1000;
for (int i=0;i<5;i++){
int[] list = new int[1000];
for (int j=0;j<n;j++){
list[j]= (int) (Math.random()*n);
}
ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
LinkedList<Integer> Linked = new LinkedList<>(array);
//查性能
// randomAccess(array,Linked,n/2);
// 插头部性能
// addFirst(array,Linked);
// 插尾部性能
addLast(array,Linked);
// 插中间性能
// addMiddle(array,Linked,n/2);
}
}
private static void addLast(ArrayList<Integer> array,LinkedList<Integer> linked){
StopWatch sw = new StopWatch();
sw.start("ArrayList");
array.add(100);
sw.stop();
sw.start("LinkedList");
linked.add(100);
sw.stop();
System.out.println(sw.prettyPrint());
}结果
000010400 066% ArrayList
000005300 034% LinkedLis000001100 050% ArrayList
000001100 050% LinkedList000001100 055% ArrayList
000000900 045% LinkedList000001200 043% ArrayList
000001600 057% LinkedList000001200 050% ArrayList
000001200 050% LinkedList
可以看出在尾部插入时 ArrayList的速度与LinkedList的速度差不多
中间插入代码
==注意==：在大家刚学链表时一定听过 数组查询块增删慢，链表查询慢增删快，但事实可能不是这样的
public static void main(String[] args) {
int n = 1000;
for (int i=0;i<5;i++){
int[] list = new int[1000];
for (int j=0;j<n;j++){
list[j]= (int) (Math.random()*n);
}
ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
LinkedList<Integer> Linked = new LinkedList<>(array);
//查性能
// randomAccess(array,Linked,n/2);
// 插头部性能
// addFirst(array,Linked);
// 插尾部性能
// addLast(array,Linked);
// 插中间性能
addMiddle(array,Linked,n/2);
}
}
private static void addMiddle(ArrayList<Integer> array,LinkedList<Integer> linked,int mid){
StopWatch sw = new StopWatch();
sw.start("ArrayList");
array.add(mid,100);
sw.stop();
sw.start("LinkedList");
linked.add(mid,100);
sw.stop();
System.out.println(sw.prettyPrint());
}结果
000031800 040% ArrayList
000047300 060% LinkedList000003600 023% ArrayList
000011900 077% LinkedList000003000 016% ArrayList
000015300 084% LinkedList000006600 024% ArrayList
000020600 076% LinkedList000005800 015% ArrayList
000032300 085% LinkedList
我们可以惊讶的看到ArrayList的速度明显优于LinkedList，这与我们的认知是不一样的。
04.ArrayList VS LinkedList
它们的优劣对比：
1.在查情况下明显 ArrayList要优于LinkedList2.在头插入时LinkedList要优于ArrayList
3.在尾插入时ArrayList和LinkedList差不多
4.在中间插入时ArrayList要优于LinkedList，原因也非常简单，因为如果要插入则一定要查询 很明显ArrayList查询要快于LinkedList，虽然ArrayList在插入时 会往后整体移动数组，但还是优于LinkedList的查询速度
补充：缓存一致性原理
我们的cpu直接读写内存数据速度很慢 所有我们通常采用把数据存入缓存 再由cpu读写，而缓存采用的策略是缓存一致性原理：把数据需要的数据的相邻地址也存入缓存 ，例如一个数组是 {1 2 3 4 5 6} 现在我们想要读写1，则会把2 3 4也放入缓存 这样的好处是我们如果读写1 大概率也会读写 2 3 4 所以更能加快读写速度，对于ArrayList来说可以完美适应缓存一致性原理，但对于LinkedList来说 它是又链表实现的 所以相邻地址不同 不能完美的适应缓存一致性 导致同样的读写操作 ArrayList速度更快。
综上
我们大多数情况应该采用ArrayList，它的增删改查操作大多数情况都优于LinkedList。
