Linkedlist与arraylist的比较[duplicate]

Question

我了解到LinkedList是作为双链表实现的，它在添加和删除上的性能比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来说，这和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);

        }
}

Answer 2

LinkedList的插入速度不快于ArrayListArrayList由数组支持，因此插入元素非常简单。插入到链接列表需要创建一个新的条目实例，这会更慢。

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