add方法的时间比较:ArrayList、LinkedList、ArrayList（用某个值初始化）

Question

我希望了解更多关于数据结构和它们的实现（在JAVA语言中）。今天我写了一个测试来比较ADT列表的不同实现（时间比较）。具体来说，我比较了add方法，下面是我的测试：

@Test
public void testTime() {
    long i = 10000000;
    long INITIALIZED_VALUE=5000000;
    List<Integer> arrayBasedList = new ArrayList<Integer>();
    List<Integer> linkedBasedList = new LinkedList<Integer>();
    List<Integer> arrayBasedInitialedSizeList = new ArrayList<Integer> (INITIALIZED_VALUE);

    long t1 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedList.add(index);
    }
    long t1End = System.currentTimeMillis() - t1;

    long t2 = System.currentTimeMillis();

    for (int index = 0; index <= i; index++) {
        linkedBasedList.add(index);
    }
    long t2End = System.currentTimeMillis() - t2;

    long t3 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedInitialedSizeList.add(index);
    }
    long t3End = System.currentTimeMillis() - t3;

    System.out.println("ArrayBased: " + t1End);
    System.out.println("LinkedList:" + t2End);
    System.out.println("ArrayBasedInitializedSize: " + t3End);

    System.out.println("End");
}

我得到了这个结果：

ArrayBased:5681 LinkedList：12830 ArrayBasedInitializedSize：858

Answer 1

这里有两件事。

首先，您的时间安排是不可靠的，因为您没有在每次运行之前“预热”代码。Java在运行代码时会优化和编译代码，所以最初几次通过代码要比后面运行慢得多。您应该运行数百次测试循环，扔掉这些结果，然后进行计时。

不过要回答这个问题：

O(1)所说的是，无论列表中有多少对象，它仍然需要相同的时间。在10个项目列表，100个项目列表，10000个项目列表的末尾添加一些东西仍然需要同样的时间。

不过，LinkedList比ArrayList花费更多的时间--尽管它们仍然具有相同的O(1)顺序。

事实上，速度上的差异是如此之大，即使将LinkedList为O(1)，ArrayList为O(n)，ArrayList对于小列表仍然更快！