ArrayList与LinkedList性能分析

一. 面试题

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

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<String> 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);
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

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

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

数量级（万）	ArrayList	LinkedList
10	520 ms	21ms
30	4006 ms	28 ms
50	13099 ms	21 ms
100	57205 ms	600 ms

结果：头部插入法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<String> 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);
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

测试结果：

----------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的尾部新增耗时：120ms

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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<String> 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);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

测试结果：

----------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.0ms

Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

结果：从数据测试来看，头部删除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<String> 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

测试结果：

----------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.0ms

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结果：从数据测试来看，尾部删除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<String> 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

测试结果：

----------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.0ms

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结果：从数据测试来看，通过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<String> 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

测试结果：

----------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.0ms

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

三. 总结

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

新增元素：

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

删除元素：

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

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

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

相关阅读:
使用c:forEach出现页面空白,没有数据
 Go语言知识查漏补缺｜基本数据类型
 python爬取网站数据，作为后端数据
 linux-awk命令
 港科夜闻｜香港科大近百名创新企业家回归母校庆祝大学首个「独角兽日」
Java程序猿搬砖笔记(十)
“元宇宙”虚拟世界的营销法则 “品牌元宇宙空间”算什么?
vue实战-路由传递参数
 专业/户籍不限！腾讯/华为招聘提到的PMP证书！多行业适用
 kafka消费/发送消息，消息过大报错解决whose size is larger than the fetch size 1048576
原文地址：https://blog.csdn.net/qq_44936392/article/details/127918091