ArrayList和LinkedList在中间开始插入的快慢比较

清疚 2022-05-24 06:40 142阅读 0赞

首先创建带数据的两个List, 然后在中间插入数据, 观察完成时间

public class Hero {
            public static void main(String[] args){
                listAndLink();
            }
                    public static void listAndLink(){
                List<String> list = new ArrayList<String>();
                LinkedList<String> link = new LinkedList<String>();
                //生产数据
                for(int i = 0; i < 100000; i ++){
                    list.add("dfghdffdhghdfghdfghians"+i);
                    link.add("dfghdffdhghdfghdfghians"+i);
                }
                //标记开始时间
                long startlist = System.currentTimeMillis();
                //在list中间插入数据
                for(int i = 0; i < 10000; i ++){
                    list.add((5000+i), "asdfasdfaasdf");
                }
                //标记结束时间
                long endlist = System.currentTimeMillis();
                System.out.println("list time==="+(endlist - startlist));
                
                //标记开始时间
                long startLink = System.currentTimeMillis();
                //在link中间插入数据
                for(int i = 0; i < 10000; i ++){
                    link.add((5000+i), "asdfasdfaasdf");
                }
                //标记结束时间
                long endLink = System.currentTimeMillis();
                System.out.println("link time -----"+(endLink - startLink));
                
            }
    }

结果

![1217818-20180521143210222-1214511810.png][]

怎么会这样, 不应该是LinkedList更快吗? ArrayList底层是数组, 添加数据需要移动后面的数据, 而LinkedList使用的是链表, 直接移动指针就行, 按理说应该是LinkedList更快.

原因先不说, 接着改变插入位置, 再来试试

public class Hero {
            public static void main(String[] args){
                listAndLink();
            }
                    public static void listAndLink(){
                List<String> list = new ArrayList<String>();
                LinkedList<String> link = new LinkedList<String>();
                //生产数据
                for(int i = 0; i < 100000; i ++){
                    list.add("dfghdffdhghdfghdfghians"+i);
                    link.add("dfghdffdhghdfghdfghians"+i);
                }
                //标记开始时间
                long startlist = System.currentTimeMillis();
                //在list中间插入数据
                for(int i = 0; i < 10000; i ++){
                    list.add((5+i), "asdfasdfaasdf");
                }
                //标记结束时间
                long endlist = System.currentTimeMillis();
                System.out.println("list time==="+(endlist - startlist));
                
                //标记开始时间
                long startLink = System.currentTimeMillis();
                //在link中间插入数据
                for(int i = 0; i < 10000; i ++){
                    link.add((5+i), "asdfasdfaasdf");
                }
                //标记结束时间
                long endLink = System.currentTimeMillis();
                System.out.println("link time -----"+(endLink - startLink));
                
            }
    }

结果

![1217818-20180521143626765-1068416786.png][]

从这里看确实是LinkedList比较快, 然后我又将插入位置改成9999, 结果如下

![1217818-20180521143819795-828327090.png][]

LinkedList的时间更长了, 现在大概知道了，插入位置的选取对LinkedList有很大的影响，

因为LinkedList在插入时需要向移动指针到指定节点， 才能开始插入,，一旦要插入的位置比较远，LinkedList就需要一步一步的移动指针， 直到移动到插入位置，这就解释了， 为什么节点值越大， 时间越长， 因为指针移动需要时间。

而ArrayList是数据结构， 可以根据下标直接获得位置， 这就省去了查找特定节点的时间，所以对ArrayList的影响不是特别大。

总结： 虽然会出现上面的情况， 可是因为ArrayList可以使用下标直接获取数据，所以在使用查询的时候一般选择ArrayList，而进行删除和增加时，LinkedList比较方便，所以一般还是使用LinkedList比较多。

[1217818-20180521143210222-1214511810.png]: /images/20220524/161dd89f252e443ca1713310fa29454b.png
[1217818-20180521143626765-1068416786.png]: /images/20220524/9cd49550fed6458795e8caeb1f883e39.png
[1217818-20180521143819795-828327090.png]: /images/20220524/da9bde398ba1428eb3ecb858096c2eda.png