Why index accessing is faster than link access in Java?

Question

I'm comparing the perfomance of contains method in ArrayList and LinkedList on a sequence of digits from 0 to 1000.

For both lists, I do a contains(400). ArrayList performance is always 3 times higher than LinkedList. Comparison is made using JMH.

The ArrayList took 329,642 nanoseconds

The LinkedList took 945,881 nanoseconds

If both lists have O(n) performance of contains method, why is the LinkedList 3 times worse?

Comparation class:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class Comparation {
    @State(Scope.Thread)
    public static class MyState {
        private List<Integer> arrayList = new ArrayList<>();
        private List<Integer> linkedList = new LinkedList<>();
        private int iterations = 1000;

        @Setup(Level.Trial)
        public void setUp() {
            for (int i = 0; i < iterations; i++) {
                arrayList.add(i);
                linkedList.add(i);
            }
        }
    }

    @Benchmark
    public boolean testLinkedListContains(MyState state) {
        return state.linkedList.contains(400);
    }
    @Benchmark
    public boolean testArrayListContains(MyState state) {
        return state.arrayList.contains(400);
    }
}

Result:

Benchmark                           Mode  Cnt    Score    Error  Units
Comparation.testArrayListContains   avgt   20  329,642 ± 20,709  ns/op
Comparation.testLinkedListContains  avgt   20  945,881 ± 43,621  ns/op

Answer 1

In ArrayList, data is backed by an array whose elements are laid out contiguously in memory. So it is very fast to increment the iterator -> Just go to the next address in memory.

In LinkedList, this is not necessarily the case, the memory needn't be contiguous the elements may be randomly placed in memory, so going from one element to other is a bit slower.