为什么 LinkedList 在添加到列表末尾时比 ArrayList 慢？

Question

我阅读了 THIS 和

并且了解到LinkedList add(E element)是O(1) 和 ArrayList add(E element) 是 O(1) 摊销的，但 O(n) 最坏的情况，因为数组必须调整大小和复制

但是，当我尝试检查它时

public class ArrayListVSLinkeedList {

public ArrayListVSLinkeedList() {

    final int COUNTER = 15000000;

    List<Integer> arrayList = new ArrayList<Integer>();

    long tStart_add = System.currentTimeMillis();

    for (int i = 0; i < COUNTER; i++) {
         arrayList.add(i);
    }
    long tEnd_add = System.currentTimeMillis();
    long tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to ArrayList: " +tDelta_add);


    List<Integer> linkedList = new LinkedList<Integer>();
    tStart_add = System.currentTimeMillis();
    for (int i = 0; i < COUNTER; i++) {
        linkedList.add(i);
    }
    tEnd_add = System.currentTimeMillis();
    tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to LinkedList: " +tDelta_add);
}

public static void main(String[] args) {
    new ArrayListVSLinkeedList();
}
}

我在输出时收到：

添加到 ArrayList：9122

添加到 LinkedList：19859

我知道，这不是真正的基准，但是... 最后，将元素添加到 ArrayList 的末尾比添加到 LinkedList 更快。为什么会这样？

Answer 1

好吧，这取决于你机器上有多少内存，认为你正在创建的 ArrayList 已经在内存中，而 LinkedList 必须分配新内存.. 尝试运行换一种方式看看结果。

更好的是 - 尝试运行它们在不同的方法中并看到一个公平的结果。

Answer 2

这仅仅是由于实施。

看看ArrayList.add的实现：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ArrayList 内部包含一个数组，其元素是对您使用该列表管理的对象的引用。 ensureCapacityInternal 方法简单地检查这个内部数组是否仍然足够大以添加另一个元素。

如果是，则添加元素和方法returns。这非常快（而且 - 顺便说一句 - 是 O(1)）。

如果数组已经满了，那么会分配一个更大的新数组，每个引用都会从旧数组复制到新数组。之后，将添加该元素。这当然是 O(n)。但是这种情况很少发生，而且由于resizing strategy（尺寸翻倍）会越来越少

另一方面，让我们看一下LinkedList.add的实现：

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

在这里您可以看到，对于每个添加的元素，都必须创建一个新的节点对象，然后将其添加为最后一个元素。没有调整大小，因此该方法始终为 O(1)，但创建节点对象比简单地存储引用花费更多时间。

为什么 LinkedList 在添加到列表末尾时比 ArrayList 慢？

Why LinkedList is slower then ArrayList when adding to the end of list?

java

collections

linked-list

arraylist