ArrayList Vs LinkedList

data-structures collections java arraylist linked-list

2022-08-31 14:59:50

对于链接列表

get 是 O（n）

添加为 O（1）

删除是 O（n）

Iterator.remove is O（1）

对于数组列表

get 是 O（1）

add 是 O（1）摊销的，但 O（n）最坏情况是，因为数组必须调整大小和复制

删除是 O（n）

因此，通过查看此内容，我得出的结论是，如果我必须在集合中对5000000个元素进行顺序插入，则会超过类。LinkedListArrayList

而且，如果我必须通过迭代从集合中获取元素，即不抓取中间的元素，仍然会超越class。LinkedListArrayList

现在为了验证我的上述两个陈述，我写了下面的示例程序...但我感到惊讶的是，我的上述陈述被证明是错误的。

ArrayList在这两种情况下都已超越。与从集合中添加和获取它们相比，它花费的时间更少。是我做错了什么，或者关于大小为5000000的集合的初始陈述和不适用于？LinkedlistLinkedListLinkedListArrayList

我提到了大小，因为如果我将元素的数量减少到50000，性能更好，并且初始语句成立。LinkedList

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for (int i = 0; i < 5000000; i++) {
    arr.add(i);
}
System.out.println(System.nanoTime() - nano1);

for (int j : arr) {
    // Do nothing
}
System.out.println(System.nanoTime() - nano1);

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for (int i = 0; i < 5000000; i++) {
    arrL.add(i);
}
System.out.println(System.nanoTime() - nano2);

for (int j : arrL) {
    // Do nothing
}
System.out.println(System.nanoTime() - nano2);

答案 1

请记住，大 O 复杂性描述渐近行为，可能无法反映实际的实现速度。它描述了每个操作的成本如何随着列表的大小而增长，而不是每个操作的速度。例如，以下实现是 O（1）但不快：add

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

我怀疑在你的情况下，ArrayList表现良好，因为它相当积极地增加了它的内部缓冲区大小，所以不会有大量的重新分配。当缓冲区不需要调整大小时，ArrayList将具有更快的s。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

（请注意，可能会溢出，您可能最好使用）。sumSystem.currentTimeMillis()

编译器也可能正在优化空循环。确保循环确实执行了一些操作，以确保调用正确的代码。get

答案 2

这是一个糟糕的基准IMO。

需要在循环中多次重复以预热jvm
需要在迭代循环中做一些事情，否则可以优化数组
ArrayList调整大小，成本高昂。如果你已经像一次一举构建的那样构建，那么所有分配都会非常便宜（一个预先分配支持的数组）ArrayListnew ArrayList(500000)
您没有指定内存 JVM - 它应该使用 -xMs == -Xmx（所有预分配内容）运行，并且足够高，以至于不会触发 GC
此基准测试并未涵盖LinkedList最令人不快的方面 - 随机访问。（迭代器不一定是一回事）。如果你说一个大集合大小的10%作为随机选择，你会发现链接列表对于抓取第一个或最后一个元素以外的任何东西都很糟糕。list.get

对于数组列表：jdk get 是你所期望的：

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

（基本上只返回索引数组元素。

对于链接列表：

public E get(int index) {
    return entry(index).element;
}

看起来很相似？差一点。entry 是一个方法，而不是一个基元数组，看看它必须做什么：

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

没错，如果你要求说，它必须从头部开始，反复迭代下一个元素。250000次左右的访问（代码中有一个优化，它从头或尾开始，这取决于哪个访问量会更少。list.get(250000)