【面试：基础篇07:ArrayList与LinkedList源码分析及其性能对比】

【面试：基础篇07:ArrayList与LinkedList源码分析及其性能对比】

00.前言

如果有任何问题请指出，感谢。

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与LinkedListArrayList<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% LinkedList

000001200 013% ArrayList
000007700 087% LinkedList

000001300 010% ArrayList
000011600 090% LinkedList

000001500 013% ArrayList
000010300 087% LinkedList

000001000 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% LinkedList

000003700 073% ArrayList
000001400 027% LinkedList

000004200 078% ArrayList
000001200 022% LinkedList

000004300 077% ArrayList
000001300 023% LinkedList

000005000 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% LinkedLis

000001100 050% ArrayList
000001100 050% LinkedList

000001100 055% ArrayList
000000900 045% LinkedList

000001200 043% ArrayList
000001600 057% LinkedList

000001200 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% LinkedList

000003600 023% ArrayList
000011900 077% LinkedList

000003000 016% ArrayList
000015300 084% LinkedList

000006600 024% ArrayList
000020600 076% LinkedList

000005800 015% ArrayList
000032300 085% LinkedList

我们可以惊讶的看到ArrayList的速度明显优于LinkedList，这与我们的认知是不一样的。

04.ArrayList VS LinkedList

它们的优劣对比：

1.在查情况下明显 ArrayList要优于LinkedList

2.在头插入时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。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！