Why index accessing is faster than link access in Java?

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

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.

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

It is not against the rule of O(n) complexity, consider O(n) as something that describes an algorithm with linear time. Contrary to what you believe It does not mean all implementations of those algorithm have the same speed. It means time that they take is a linear function of their inputs, here ArrayList is three times faster, but if you increase the number of element in List you can see ArrayList is still three time faster, and the time to iterate both of them grows as a liner function of the number of elements in List. So if you say Arraylist takes 2n to execute that functionality and LinkedList takes 10000n to execute that functionality, you can say they both run in O(n).

Here you exactly came to this conclusion that LikedList is three times worse, it means they have the same complexity O(n).

But If by increasing the number of input you find that it is not 3 times worse any more and it is getting 5 times worse or 30 times worse and this number grows based on the number of input(which is n), they don't have the same complexity O(n).

Very simply: different data structures have different performance trade-offs.

> https://dzone.com/articles/arraylist-vs-linkedlist-vs
>
> LinkedList is implemented as a double linked list. Its performance on
> add and remove is better than Arraylist, but worse on get and set
> methods.

In other words, if your motivation was to continuously modify the list, LinkedList might be a better choice. But to simply create and traverse the list, ArrayList "wins".

To continue:

> As more elements are added to ArrayList, its size is increased
> dynamically. It's elements can be accessed directly by using the get
> and set methods, since ArrayList is essentially an array.
> ...
>
> Vector and ArrayList require space as more elements are added. Vector
> each time doubles its array size, while ArrayList grow 50% of its size
> each time.
> ...
>
> LinkedList, however, also implements Queue interface which adds more
> methods than ArrayList and Vector, such as offer(), peek(), poll(),
> etc.
> ...
>
> Note: The default initial capacity of an ArrayList is pretty
> small. It is a good habit to construct the ArrayList with a higher
> initial capacity. This can avoid the resizing cost.

In this case, an array is faster .. but less flexible.