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

Question

我读这和

并且理解LinkedList add(E元素)是O(1)和ArrayList add(E元素)是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.add:

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

一个ArrayList内部拥有一个数组,其元素是您正在使用列表管理对象的引用.该方法ensureCapacityInternal只是检查此内部数组是否仍然足够大以添加另一个元素.

如果是,则添加元素并返回方法.这非常快(而且 - 顺便说一下 - 是O(1)).

如果数组已满,则将分配具有更大大小的新数组,每个引用将从旧数组复制到新数组.之后,将添加元素.这当然是O(n).但这种情况很少发生,并且由于调整大小的策略(尺寸加倍),它将变得越来越少.

另一方面,让我们来看看实现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),但创建节点对象比简单地存储引用需要更多时间.