ArrayList与LinkedList

请记住，big-
O复杂性描述的是渐近行为，可能无法反映实际的实现速度。它描述了每个操作的成本如何随列表的大小而增加，而不是每个操作的速度。例如，下面的实现

add

public class MyList extends linkedList {    public void add(Object o) {        Thread.sleep(10000);        super.add(o);    }}

我怀疑在您的情况下ArrayList表现良好，因为它相当大地增加了其内部缓冲区的大小，因此不会有大量的重新分配。当不需要调整缓冲区大小时，ArrayList将具有更快的

add

在进行此类分析时，还需要非常小心。我建议您更改配置文件代码以进行预热阶段（这样，JIT就有机会进行一些优化而不影响您的结果），并在多次运行中平均结果。

private final static int WARMUP = 1000;private final static int TEST = 1000;private final static int SIZE = 500000;public void perfTest() {    // Warmup    for (int i = 0; i < WARMUP; ++i) {        buildArrayList();    }    // Test    long sum = 0;    for (int i = 0; i < TEST; ++i) {        sum += buildArrayList();    }    System.out.println("Average time to build array list: " + (sum / TEST));}public long buildArrayList() {    long start = System.nanoTime();    ArrayList a = new ArrayList();    for (int i = 0; i < SIZE; ++i) {        a.add(i);    }    long end = System.nanoTime();    return end - start;}... same for buildlinkedList

（请注意，

sum

System.currentTimeMillis()

编译器也有可能正在优化空

get