Why is ArrayList iterable faster than LinkedList?

Chik-2019-10-07 16:33:15

Java

Chik-, 2019-10-07 16:33:15

I have run these tests several times. Swap who starts first.
For all four tests, ArrayList had a clear advantage over iteration. What is it connected with?

Answer the question

In order to leave comments, you need to log in

2 answer(s)

Roman, 2019-10-07
@myjcom

What is it connected with?

ArrayList is an array insertion and O(1) access
LinkedList is a linked list insertion and O(n) access
In your case (summation) brute force is O(n) anyway
So it's all about insertion, to insert an element at the end of the list you need get to the final element. Every time you insert a new element, you iterate over the list from beginning to end, which in turn gives O( ~~n log n~~ n ^ 2) in your loop , brakes appear due to a large number of memory allocations (this is an expensive operation) Because in 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.

, but in LinkedList every time a new element is added.
UPD:
собственно обычный обход списка src

public 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;
}

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];
}

tsarevfs, 2019-10-07
@tsarevfs

ArrayList is practically(*) always faster than LinkedList. This is because ArrayList stores data in a contiguous chunk of memory. LinkedList allocates memory for each node and connects them with links.
Modern processors work well with continuous data. This is due to the operation of the cache and the superscalar architecture. The processor can load data ahead, use vector SSE instructions, etc.
https://habr.com/en/post/312078/
In LinkedList, each iteration will probably result in a memory access. For an array, this is incrementing a counter in a processor register. The time difference can reach hundreds of times.
*LinkedList is asymptotically (given a large enough size) faster at inserting and removing elements from the middle, since the array needs to shift elements. However, this can only be seen on arrays with hundreds or even thousands of elements.