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

Question

我读过THIS和

并且理解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();
}
}

我收到的输出：

添加到阵列列表：9122

添加到链接列表：19859

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

Answer 1

这仅仅是由于实现。

看看ArrayList.add:的实现

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

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

如果是，则添加元素并返回方法。这是非常快的（并且-btw-是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），但创建节点对象比简单地存储引用需要更多的时间。

Answer 2

好吧，这取决于你在机器上有多少内存，假设你正在创建的ArrayList已经在内存中了，LinkedList必须分配新的内存。。试着用另一种方式运行它，看看结果。

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