Почему ArrayList итерируется быстрее, чем LinkedList?
С чем это связано?
ArrayList это массив вставка и доступ O(1)
LinkedList это связный список вставка и доступ O(n)
В вашем случае (суммирование) полный перебор это в любом случае O(n)
Значит все дело в вставке, чтобы вставить элемент в конец списка нужно добраться до конечного элемента. Каждый раз когда вы вставляете новый элемент, вы перебираете список от начала до конца, что в свою очередь в вашем цикле дает O(n log n n ^ 2)Хотя если следовать тому что написано в документации, LinkedList add эквивалентно addLast
тогда все немного иначе, тормоза появляются из-за большого количества выделений памяти (это дорогостоящая операция)
Потому как в ArrayList она выделяется с запасомEach ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation. , а в LinkedList каждый раз при добавлении нового элемента.
UPD:Вот так итерируется LinkedList
собственно обычный обход списка srcpublic ListIterator<E> listIterator(int index) {
  checkPositionIndex(index);
  return new ListItr(index);
}
// ...
private class ListItr implements ListIterator<E> {
  private Node<E> lastReturned = null;
  private Node<E> next;
  private int nextIndex;
  private int expectedModCount = modCount;
  ListItr(int index) {
    // assert isPositionIndex(index);
    next = (index == size) ? null : node(index);
    nextIndex = index;
  }
  public boolean hasNext() {
    return nextIndex < size;
  }
  public E next() {
    checkForComodification();
    if (!hasNext())
      throw new NoSuchElementException();
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}А так ArrayList
hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/sha...private class Itr implements Iterator<E> {
  int cursor;       // index of next element to return
  int lastRet = -1; // index of last element returned; -1 if no such
  int expectedModCount = modCount;
  public boolean hasNext() {
    return cursor != size;
  }
  @SuppressWarnings("unchecked")
  public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
      throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
      throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}
ArrayList практически(*) всегда быстрее чем LinkedList. Это связано с тем, что ArrayList хранит данные в непрерывном куске памяти. LinkedList же выделяет память для каждого узла и связывает их ссылками.
Современные процессоры хорошо работают с непрерывными данными. Это связано с работой кэша и суперскалярной архитектурой. Процессор может подгружать данные наперед, использовать векторные SSE инструкции и.т.д.
https://habr.com/en/post/312078/
В LinkedList каждая итерация вероятно приведет к обращению к памяти. Для массива это увеличение счетчика в регистре процессора. Разница по времени может достигать сотен раз.
*LinkedList асимптотически(при достаточно большом размере) быстрее при вставке и удалении элементов из средины, поскольку для массива нужен сдвиг элементов. Однако это можно заметить только на массивах с сотнями а то и тысячами элементов.