LinkedList over ArrayList的比较

Question

我知道LinkedList是作为双链表实现的。它在添加和删除方面的性能优于Arraylist，但在获取和设置方法上更差。

这是否意味着我应该选择LinkedList而不是Arraylist来插入？

我写了一个小测试，发现ArrayList插入速度更快。那么链表如何比ArrayList更快？

请参考下面的例子，我已经做了。

import java.util.Date; 
    import java.util.LinkedList; 
    import java.util.List; 

    public class TestLinkedList { 

     public static void main(String[] args) { 

      long lStartTime = new Date().getTime(); 
      System.out.println("lStartTime:: " + lStartTime); 
      List<Integer> integerList = new LinkedList<Integer>(); 
      for (int i = 0; i < 10000000; i++) { 
       integerList.add(i); 
      } 

      long lEndTime = new Date().getTime(); 
      System.out.println("lEndTime:: " + lEndTime); 

      long difference = lEndTime - lStartTime; 

      System.out.println("Elapsed milliseconds: " + difference); 

     } 

    } 

Answer 1

Linkedlist确实插入速度更快，问题出在你的例子上。在你的代码中，你通过追加到所有的时间来插入。对于ArrayList，它和LinkedList一样简单。你应该做的是建立一个说5000个项目的清单，然后开始插入中间。这里array变慢 - 你必须在插入位置之后将整个数组的其余部分全部移位。这是什么将显示差异。分析事情的工作原理，不难理解为什么。下面是修改后的代码：

import java.util.Date; 
    import java.util.LinkedList; 
    import java.util.ArrayList; 
    import java.util.List; 

    public class Prob { 

     public static void main(String[] args) { 

      long lStartTime = new Date().getTime(); 
      System.out.println("lStartTime:: " + lStartTime); 
      List<Integer> integerList = new LinkedList<Integer>(); 
      for (int i = 0; i < 5000; i++) { 
       integerList.add(0, i); 
      } 
      for (int i = 0; i < 100000; i++) { 
       integerList.add(1000, i); 
      } 

      long lEndTime = new Date().getTime(); 
      System.out.println("lEndTime:: " + lEndTime); 

      long difference = lEndTime - lStartTime; 

      System.out.println("Elapsed milliseconds: " + difference); 

     } 
} 

Answer 2

LinkedList并不比插入ArrayList更快。 ArrayList由数组支持，因此插入元素很简单。插入到LinkedList涉及创建新的Entry实例，该实例较慢。

插入到ArrayList的唯一时间可能会比较慢，因为插入导致容量增加，这需要创建新阵列并将旧阵列复制到该阵列。