LinkedList和ArrayList在尾部插入数据效率对比

亦凉 2022-03-18 07:14 256阅读 0赞

转载于：[https://blog.csdn.net/qq\_34144916/article/details/81154528][https_blog.csdn.net_qq_34144916_article_details_81154528]

做这个实验之前，我的猜想的是：因为每次都是在尾部插入数据，而LinkedLiist里面有一个last指针一直指向最后一个元素，而ArrayList则根据索引来找到最后一个元素，那么，这两个方式中，效率应该是差不多的；

但是实验结果却不是这样的；

先看代码：

package 源码测试;  
   
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.Scanner;  
   
public class arraylist\_linkedlist \{  
    public static void main(String\[\] args) \{  
        Scanner sc=new Scanner(System.in);  
        while(sc.hasNext())\{  
            int num=sc.nextInt();  
            ArrayList alist=new ArrayList();  
            LinkedList llist=new LinkedList();  
            long startTime = System.currentTimeMillis();    //获取开始时间  
              
            for(int i=0;i<num;i++)\{  
                alist.add(i);  
            \}   //测试的代码段  
              
            long endTime = System.currentTimeMillis();    //获取结束时间  
              
            System.out.println("ArrayList程序运行时间：" + (endTime - startTime) + "ms");    //输出程序运行时间  
              
            long startTime1 = System.currentTimeMillis();    //获取开始时间  
              
            for(int i=0;i<num;i++)\{  
                llist.add(i);  
            \}   //测试的代码段  
              
            long endTime1 = System.currentTimeMillis();    //获取结束时间  
              
            System.out.println("LinkedList程序运行时间：" + (endTime1 - startTime1) + "ms");    //输出程序运行时间  
        \}  
    \}  
\}

![70][]

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

比较源码：

![70 1][]

![70 2][]

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

arraylist 默认初始容量为 10 ，扩容机制 乘于 1.5 +1

[https_blog.csdn.net_qq_34144916_article_details_81154528]: https://blog.csdn.net/qq_34144916/article/details/81154528
[70]: /images/20220318/04d42a46ed1d422ab4266eb92bf07325.png
[70 1]: /images/20220318/b301aeba2fc64314ac5d5e02f4954b8c.png
[70 2]: /images/20220318/db1dc7ed8b5b4f858a37236a683f5494.png