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

链接列表的插入速度确实更快，问题出在你的例子上。在您的代码中，您始终通过附加到末尾来插入。对于 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);

        }
}