java - 为什么在插入 LinkedList 和 ArrayList 时得到关于时间的不同输出

Question

我正在使用 LinkedList 和 ArrayList，我知道将元素添加到 ArrayList 和 LinkedList 的概念，但是当我运行检查插入时间的代码时，我得到了LinkedList 和 ArrayList 一次又一次地插入不同的时间。

有时LinkedList的插入时间来得比较好，反之亦然，具体是怎么回事，谁能告诉我。

import java.util.ArrayList;

public class Time
   {

   public static void main(String args[])

    {

       int n=100000;
       long milis = System.currentTimeMillis();
       ArrayList obj=new ArrayList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert arraylist takes "
            +(System.currentTimeMillis()-milis)+" ms");
}

  }

这个程序的输出是

1) 插入数组列表需要 13 毫秒2)插入arraylist需要9毫秒

第二个代码是

 import java.util.LinkedList;

  public class Time1 
  {

        public static void main(String args[])
{
      int n=100000;
      long milis = System.currentTimeMillis();
      LinkedList obj=new LinkedList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert linklist takes "
           +(System.currentTimeMillis()-milis)+" ms");
}

 }

这个的输出

1)插入链表需要8毫秒

2)插入链表需要17毫秒

Answer 1

一般来说，链表在除列表末尾以外的任何地方添加和删除元素时效率更高，但在列表中查找任意索引时会慢得多。要在 LinkedList 的任何位置添加或删除元素，只需更改几个引用，但在 ArrayList 中，该点之后的所有内容都需要移动。在查找任意索引方面，ArrayList 只是跳转到内存中的那个位置，LinkedList 必须遍历每个项目直到那个点。

这是一个微不足道的例子。您没有在上方看到此内容的主要原因有两个:

• 首先，微基准测试在最好的时候很糟糕，但在 Java 这样的语言中尤其如此，在这种语言中，您有一个 JIT 可以“预热”并在此过程中改变性能。要么在真实场景中对其进行基准测试，要么您几乎可以告别任何真实的性能指标。

• 其次，ArrayList 多年来经历了很多优化，以至于我什至注意到它在某些您通常期望 LinkedList 的情况下执行得更快 胜出。

就我个人而言，我会将 ArrayList 放在我正在使用的实际应用程序中，而不是微型基准测试中，并测量性能。如果性能 Not Acceptable ，我会将实现切换到 LinkedList(这应该是一行更改)，然后再次运行基准测试以进行检查。如果没有这些检查，几乎不可能说出在您的场景中什么会表现得更好。