ArrayList与LinkList性能分析

一. 面试题

作为程序员来说，这道面试题基本上都逃不过面试官的提问，而我们给出的答案基本上都是千篇一律，，看到这个面试题的时候我们也请扪心自问一下，我们该如何去回答，我们的答案自己都去验证了吗？

ArrayList和LinkedList的区别?

基本回答：

• ArrayList底层是数组，增删慢，查找快。
• LinkedList底层是双向链表，增删快，查找慢。

然后再去解释一下的数据结构以及存储原理，基本上认知也就结束了。

其实这只是片面的回答，它的具体性能还得用数据来说话，接下来我们从头部，中间，及尾部多个维度来探索以下ArrayList和LinkedList的性能问题。

二. 性能对比

接下来我们将用数据的量级测试ArrayList和LinkList的性能。

1. 数据插入

1. 头部插入法

代码演示：

package com.student.studentserver.test.list.add;import com.student.studentserver.test.list.AddListUtil;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class HeaderAdd {public static void main(String[] args) {System.out.println("----------10w----------");useTime(100000);System.out.println("----------30w----------");useTime(300000);System.out.println("----------50w----------");useTime(500000);System.out.println("----------100w----------");useTime(1000000);}public static void useTime(int count){System.out.println("从ArrayList的头部新增耗时：" + addHeader(new ArrayList<>(), count) + "ms");System.out.println("从LinkedList的头部新增耗时：" + addHeader(new LinkedList<>(), count) + "ms");}/*** 从List的头部新增元素* @param list list* @param count 新增元素的个数* @return 所耗费的时间（单位：ms）*/public static long addHeader(List list, int count) {long start = System.currentTimeMillis();for (int i = 0; i < count; i++) {list.add(0, "onemore-" + i);}long end =  System.currentTimeMillis();return (end - start);}
}

数据统计：数据量/w , 耗时/ms

----------10w----------
从ArrayList的头部新增耗时：520ms
从LinkedList的头部新增耗时：21ms
----------30w----------
从ArrayList的头部新增耗时：4006ms
从LinkedList的头部新增耗时：28ms
----------50w----------
从ArrayList的头部新增耗时：13099ms
从LinkedList的头部新增耗时：21ms
----------100w----------
从ArrayList的头部新增耗时：57205ms
从LinkedList的头部新增耗时：600msProcess finished with exit code 0

结果：头部插入法LinkedList效率远高于ArrayList

2. 尾部插入法

代码演示：

package com.student.studentserver.test.list.add;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;package com.student.studentserver.test.list.add;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class TailAdd {public static void main(String[] args) {System.out.println("----------1w----------");useTime(10000);System.out.println("----------5w----------");useTime(50000);System.out.println("----------10w----------");useTime(100000);System.out.println("----------15w----------");useTime(150000);System.out.println("----------20w----------");useTime(200000);System.out.println("----------30w----------");useTime(300000);System.out.println("----------50w----------");useTime(500000);System.out.println("----------70w----------");useTime(700000);System.out.println("----------100w----------");useTime(1000000);}public static void useTime(int count){System.out.println("从ArrayList的尾部新增耗时：" + addTail(new ArrayList<>(), count) + "ms");System.out.println("从LinkedList的尾部新增耗时：" + addTail(new LinkedList<>(), count) + "ms");}/*** 从List的尾部新增元素* @param list list* @param count 新增元素的个数* @return 所耗费的时间（单位：ms）*/public static long addTail(List list, int count) {long start = System.currentTimeMillis();for (int i = 0; i < count; i++) {list.add("tail-" + i);}long end = System.currentTimeMillis();return (end - start);}
}

测试结果：

----------1w----------
从ArrayList的尾部新增耗时：5ms
从LinkedList的尾部新增耗时：4ms
----------5w----------
从ArrayList的尾部新增耗时：10ms
从LinkedList的尾部新增耗时：4ms
----------10w----------
从ArrayList的尾部新增耗时：15ms
从LinkedList的尾部新增耗时：4ms
----------15w----------
从ArrayList的尾部新增耗时：5ms
从LinkedList的尾部新增耗时：23ms
----------20w----------
从ArrayList的尾部新增耗时：7ms
从LinkedList的尾部新增耗时：9ms
----------30w----------
从ArrayList的尾部新增耗时：11ms
从LinkedList的尾部新增耗时：27ms
----------50w----------
从ArrayList的尾部新增耗时：13ms
从LinkedList的尾部新增耗时：68ms
----------70w----------
从ArrayList的尾部新增耗时：23ms
从LinkedList的尾部新增耗时：379ms
----------100w----------
从ArrayList的尾部新增耗时：48ms
从LinkedList的尾部新增耗时：120msProcess finished with exit code 0

结果：从数据测试来看， 对于尾插法而言，不是说ArrayList就一定比Linked效率高，经过大量的数据测试，发现10以内Linked比ArrayList快，100w以上ArrayList明显比Linked快。

2. 数据删除

1. 头部删除法

代码演示：

package com.student.studentserver.test.list.del;import com.student.studentserver.test.list.DeleteListUtil;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class DelList {public static void main(String[] args) {System.out.println("----------1w----------");delToList(10000);System.out.println("----------5w----------");delToList(50000);System.out.println("----------10w----------");delToList(100000);System.out.println("----------15w----------");delToList(150000);System.out.println("----------20w----------");delToList(200000);System.out.println("----------30w----------");delToList(300000);System.out.println("----------50w----------");delToList(500000);System.out.println("----------70w----------");delToList(700000);System.out.println("----------100w----------");delToList(1000000);}public static void delToList(int count){System.out.println("从ArrayList的头部删除元素：" + deleteHeader(new ArrayList<>(), count) + "ms");System.out.println("从LinkedList的头部删除元素：" + deleteHeader(new LinkedList<>(), count) + "ms");}/*** 从List的头部删除元素* @param list list* @param count 删除元素的个数* @return 所耗费的时间（单位：ms）*/public static double deleteHeader(List list, int count) {for (int i = 0; i < count; i++) {list.add("del-" + i);}long start = System.currentTimeMillis();for (int i = 0; i < count; i++) {list.remove(0);}long end = System.currentTimeMillis();return (end - start);}}

测试结果：

----------1w----------
从ArrayList的头部删除元素：6.0ms
从LinkedList的头部删除元素：1.0ms
----------5w----------
从ArrayList的头部删除元素：79.0ms
从LinkedList的头部删除元素：2.0ms
----------10w----------
从ArrayList的头部删除元素：416.0ms
从LinkedList的头部删除元素：4.0ms
----------15w----------
从ArrayList的头部删除元素：875.0ms
从LinkedList的头部删除元素：2.0ms
----------20w----------
从ArrayList的头部删除元素：1587.0ms
从LinkedList的头部删除元素：5.0ms
----------30w----------
从ArrayList的头部删除元素：3623.0ms
从LinkedList的头部删除元素：6.0ms
----------50w----------
从ArrayList的头部删除元素：11891.0ms
从LinkedList的头部删除元素：8.0ms
----------70w----------
从ArrayList的头部删除元素：26807.0ms
从LinkedList的头部删除元素：15.0ms
----------100w----------
从ArrayList的头部删除元素：56940.0ms
从LinkedList的头部删除元素：30.0msProcess finished with exit code 0

结果：从数据测试来看，头部删除LinkedList比ArrayList快

2. 尾部删除法

代码演示：

package com.student.studentserver.test.list.del;import com.student.studentserver.test.list.DeleteListUtil;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class DelList {public static void main(String[] args) {System.out.println("----------1w----------");delToList(10000);System.out.println("----------5w----------");delToList(50000);System.out.println("----------10w----------");delToList(100000);System.out.println("----------15w----------");delToList(150000);System.out.println("----------20w----------");delToList(200000);System.out.println("----------30w----------");delToList(300000);System.out.println("----------50w----------");delToList(500000);System.out.println("----------70w----------");delToList(700000);System.out.println("----------100w----------");delToList(1000000);}public static void delToList(int count){System.out.println("从ArrayList的尾部删除元素：" + deleteTail(new ArrayList<>(), count) + "ms");System.out.println("从LinkedList的尾部删除元素：" + deleteTail(new LinkedList<>(), count) + "ms");}/*** 从List的尾部删除元素* @param list list* @param count 删除元素的个数* @return 所耗费的时间（单位：ms）*/public static double deleteTail(List list, int count) {for (int i = 0; i < count; i++) {list.add("del-" + i);}long start = System.currentTimeMillis();;for (int i = 0; i < count; i++) {list.remove(list.size() - 1);}long end = System.currentTimeMillis();;return (end - start);}
}

测试结果：

----------1w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：2.0ms
----------5w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：8.0ms
----------10w----------
从ArrayList的尾部删除元素：0.0ms
从LinkedList的尾部删除元素：6.0ms
----------15w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：4.0ms
----------20w----------
从ArrayList的尾部删除元素：0.0ms
从LinkedList的尾部删除元素：4.0ms
----------30w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：14.0ms
----------50w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：57.0ms
----------70w----------
从ArrayList的尾部删除元素：2.0ms
从LinkedList的尾部删除元素：29.0ms
----------100w----------
从ArrayList的尾部删除元素：4.0ms
从LinkedList的尾部删除元素：27.0msProcess finished with exit code 0

结果：从数据测试来看，尾部删除ArrayList比LinkedList快

3. 数据检索

1. for 循环遍历List

代码演示：

package com.student.studentserver.test.list.query;import com.student.studentserver.test.list.IterationListUtil;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class QueryList {public static void main(String[] args) {System.out.println("----------1w----------");IteratToList(10000);System.out.println("----------5w----------");IteratToList(50000);System.out.println("----------10w----------");IteratToList(100000);System.out.println("----------15w----------");IteratToList(150000);}public static void IteratToList(int count){System.out.println("通过for循环遍历ArrayList：" + getByFor(new ArrayList<>(count), count) + "ms");System.out.println("通过for循环遍历LinkedList：" + getByFor(new LinkedList<>(), count) + "ms");}/*** 通过for循环遍历List** @param list  list* @param count 遍历元素的个数* @return 所耗费的时间（单位：ms）*/public static double getByFor(List list, int count) {for (int i = 0; i < count; i++) {list.add("for-" + i);}String name = "本草中国";long start = System.currentTimeMillis();for (int i = 0; i < count; i++) {if (name.equals(list.get(i))) {System.out.println(name);}}long end = System.currentTimeMillis();return (end - start);}
}

测试结果：

----------1w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：43.0ms
----------5w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：1924.0ms
----------10w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：11731.0ms
----------15w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：13699.0msProcess finished with exit code 0

结果：从数据测试来看，通过for循环遍历时，ArrayList的效率高于LinkedList,而且LinkedList的效率极低。

2. foreach 循环遍历List

代码演示：

package com.student.studentserver.test.list.query;import com.student.studentserver.test.list.IterationListUtil;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** @author gf* @date 2022/11/18*/
public class QueryList {public static void main(String[] args) {System.out.println("----------1w----------");IteratToList(10000);System.out.println("----------5w----------");IteratToList(50000);System.out.println("----------10w----------");IteratToList(100000);System.out.println("----------50w----------");IteratToList(500000);System.out.println("----------100w----------");IteratToList(1000000);}public static void IteratToList(int count){System.out.println("通过foreach遍历ArrayList：" + getByForeach(new ArrayList<>(count), count) + "ms");System.out.println("通过foreach遍历LinkedList：" + getByForeach(new LinkedList<>(), count) + "ms");}/*** 通过foreach遍历List** @param list  list* @param count 遍历元素的个数* @return 所耗费的时间（单位：ms）*/public static double getByForeach(List list, int count) {for (int i = 0; i < count; i++) {list.add("foreach-" + i);}String name = "本草中国";long start = System.currentTimeMillis();for (String str : list) {if (name.equals(str)) {System.out.println(name);}}long end = System.currentTimeMillis();return (end - start);}
}

测试结果：

----------1w----------
通过foreach遍历ArrayList：2.0ms
通过foreach遍历LinkedList：2.0ms
----------5w----------
通过foreach遍历ArrayList：1.0ms
通过foreach遍历LinkedList：5.0ms
----------10w----------
通过foreach遍历ArrayList：2.0ms
通过foreach遍历LinkedList：10.0ms
----------50w----------
通过foreach遍历ArrayList：4.0ms
通过foreach遍历LinkedList：7.0ms
----------100w----------
通过foreach遍历ArrayList：5.0ms
通过foreach遍历LinkedList：9.0msProcess finished with exit code 0

结果：从数据测试来看，通过foreach遍历时，ArrayList的效率和LinkedList相差不大。

三. 总结

ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

新增元素：

• 头插法：LinkedList效率远高于ArrayList
• 尾插法：对于尾插法而言，不是说ArrayList就一定比Linked效率高，经过大量的数据测试，发现10以内Linked比ArrayList快，100w以上ArrayList明显比Linked快。

删除元素：

• 头部删除：头部删除LinkedList比ArrayList快
• 尾部删除：尾部删除ArrayList比LinkedList快

通过for循环遍历时，ArrayList的效率高于LinkedList，而且LinkedList的效率极低；通过foreach遍历时，ArrayList的效率和LinkedList相差不大。所以请避免使用for循环遍历LinkedList集合。

思考：java中的for循环和foreach循环有什么区别呢？