Linkedlist与arraylist的比较

Question

我知道LinkedList是作为一个双链表实现的。它在add和remove上的性能优于Arraylist，但在get和set方法上的性能较差。

这是否意味着我应该选择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快。ArrayList有一个数组作为支持，因此插入一个元素是微不足道的。插入到LinkedList涉及创建一个新的Entry实例，这比较慢。

插入到ArrayList的唯一时间可能较慢，是当插入导致ArrayList容量增加时，这需要创建一个新阵列并将旧阵列复制到其中。

Answer 2

Linkedlist在插入时确实更快，问题在于您的示例。在您的代码中，您一直通过在末尾添加来插入。对于ArrayList，它和LinkedList一样简单。你应该做的是建立一个5000项的列表，然后开始插入在中间。这里数组变慢了——在插入位置之后，您必须一直移动数组的其余部分。这将显示差异。分析事物是如何运作的，不难理解为什么。这是修改后的代码：

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);
        }
}