java ArrayList和LinkedList最后添加数据效率问题

悠悠 2023-10-05 06:29 8阅读 0赞

#### 两个集合进行对比测试： ####

//添加方法
        public static void insertAfter(List<Integer> list,String type,int total){
            //常量
            final int num=5;
            //start
            long start =System.currentTimeMillis();
            for (int i = 0; i <total ; i++) {
                list.add(i,num);  //最后面插入100000条数据
            }
            //end
            long end = System.currentTimeMillis();
            System.out.printf("在%s 最后插入%d条数据，总共耗时 %d 毫秒 %n", type, total, end - start);
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70][]

#### 效果： ####

5w条

![20201027155334186.png][]

10w条

![2020102715525789.png][]

1000w条

![20201027155122544.png][]

当输入的数据一直是小于千万级别的时候，大部分是Linked效率高，我猜想应该是当出现ArrayList扩容的时候，会效率降低，所以ArrayList的效益比较低。而当数据量大于千万级别的时候，就会出现ArrayList的效率比较高了。为什么呢？

查看ArrayList源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 1][]

查看LinkedList源码:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 2][]

**linkLast方法：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 3][]

原来 LinkedList每次增加的时候，会new 一个Node对象来存新增加的元素，所以当数据量小的时候，这个时间并不明显，而ArrayList需要扩容，所以LinkedList的效率就会比较高，其中如果ArrayList出现不需要扩容的时候，那么ArrayList的效率应该是比LinkedList高的，当数据量很大的时候，**new对象的时间大于扩容的时间，那么就会出现ArrayList'的效率比Linkedlist高了**。

#### 注意：ArrayList默认的容量是10 ####

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 4][]

#### 扩容机制 乘于 1.5 +1 ####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020102715510671.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4,size_16,color_FFFFFF,t_70
[20201027155334186.png]: https://img-blog.csdnimg.cn/20201027155334186.png
[2020102715525789.png]: https://img-blog.csdnimg.cn/2020102715525789.png
[20201027155122544.png]: https://img-blog.csdnimg.cn/20201027155122544.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201027154107347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020102715414077.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201027154209153.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201027154526721.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hseDIwMDgwODA4,size_16,color_FFFFFF,t_70