Using a LinkedList or ArrayList for iteration

Okay Its been already answered but I will still try to put my point. ArrayList is faster in iteration than LinkedList. The reason is same because arrayList is backed by an array. Lets try to understand whay array iteration is faster then linkedList.

There are 2 factors that work for it

• Array is stored as contiguous memory locations (You can say then
  what?)
• System cache is much faster then accessing memory

But you can ask how Cache fits here. Well check here, CPU tries to take leverage of caches by storing data in cache. It uses Locality of refrence.Now there are 2 techniques which are

Reference Locality of refrence

Temporal locality If at one point a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future. There is a temporal proximity between the adjacent references to the same memory location. In this case it is common to make efforts to store a copy of the referenced data in special memory storage, which can be accessed faster. Temporal locality is a special case of spatial locality, namely when the prospective location is identical to the present location.

Spatial locality If a particular storage location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future. In this case it is common to attempt to guess the size and shape of the area around the current reference for which it is worthwhile to prepare faster access.

So if one array location is accessed at a time it will load the adjacent memory locations in cache too. But wait it will not load all. It depends on CACHE_LINES. Well CACHE_LINES define how much bits can be loaded in cache at a time.

So before diving further lest remind what we know

• Array is contiguous memory locations
• When one memory location of array is accessed adjacent also loaded in memory
• How much array memory locations are loaded in memory is defined by CACHE-LINES capacity

SO whenever CPU tries to access a memory location it check if that memory is already in cache. If its present it match else its cache miss.

So from what we know in case of array there will be less cache_miss as compared to random memory locations as in linked list. So it makes sense

and finally from here Array_data_structure from Wikipedia it says

In an array with element size k and on a machine with a cache line size of B bytes, iterating through an array of n elements requires the minimum of ceiling(nk/B) cache misses, because its elements occupy contiguous memory locations. This is roughly a factor of B/k better than the number of cache misses needed to access n elements at random memory locations. As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of refrence

I guess that answers your question.

public List<Integer> generateArrayList(int n) {
    long start = System.nanoTime();
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        result.add(i);
    }
    System.out.println("generateArrayList time: " + (System.nanoTime() - start));
    return result;
}

public List<Integer> generateLinkedList(int n) {
    long start = System.nanoTime();
    List<Integer> result = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        result.add(i);
    }
    System.out.println("generateLinkedList time: " + (System.nanoTime() - start));
    return result;
}

public void iteratorAndRemove(List<Integer> list) {
    String type = list instanceof ArrayList ? "ArrayList" : "LinkedList";
    long start = System.nanoTime();
    Iterator<Integer> ite = list.iterator();
    while (ite.hasNext()) {
        int getDataToDo = ite.next();
        ite.remove();
    }
    System.out.println("iteratorAndRemove with " + type + " time: " + (System.nanoTime() - start));
}

@org.junit.Test
public void benchMark() {
    final int n = 500_000;
    List<Integer> arr = generateArrayList(n);
    List<Integer> linked = generateLinkedList(n);
    iteratorAndRemove(linked);
    iteratorAndRemove(arr);

}

Arraylist is useful for get random position value, linkedlist useful for insert, remove operate. Above code will show linkedlist very faster than ArrayList, in remove function linkedlist faster than arraylist 1000 times, OMG!!!

generateArrayList time: 15997000
generateLinkedList time: 15912000
iteratorAndRemove with LinkedList time: 14188500
iteratorAndRemove with ArrayList time: 13558249400

For iterating both will have the same O(n) complexity on iterating, ArrayList will take less memory BTW.

The performance trade-offs between ArrayList and LinkedList have been discussed before, but in short: ArrayList tends to be faster for most real-life usage scenarios. ArrayList will cause less memory fragmentation and will play nicer with the Garbage Collector, it will use up less memory and allow for faster iteration, and it will be faster for insertions that occur at the end of the list.

So, as long as the insertions in the list always occur at the last position, there's no reason to pick LinkedList - ArrayList is the clear winner.