Why ArrayList Beats LinkedList with RandomAccess: Performance Insights

In Java development the List interface is used constantly, but ArrayList implements the RandomAccess marker interface while LinkedList does not, which raises the question of why.

Class Declarations

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

The RandomAccess interface is empty; it simply marks a list as supporting fast random access.

How Collections Uses RandomAccess

The Collections.binarySearch method checks whether the supplied list is an instance of RandomAccess (or is small) and then calls either indexedBinarySearch or iteratorBinarySearch.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

indexedBinarySearch

traverses the list by index, while iteratorBinarySearch uses a ListIterator to reach the middle element.

Performance Test Code

public class CollectionTest {
    public static void main(String[] args) {
        long arrayListIndexedTime = arrayListIndexed();
        long arrayListIteratorTime = arrayListIterator();
        long linkedListIndexedTime = linkedListIndexed();
        long linkedListIteratorTime = linkedListIterator();
        System.out.println("ArrayList for-loop time: " + arrayListIndexedTime);
        System.out.println("ArrayList iterator time: " + arrayListIteratorTime);
        System.out.println("LinkedList for-loop time: " + linkedListIndexedTime);
        System.out.println("LinkedList iterator time: " + linkedListIteratorTime);
    }
    // ... methods arrayListIndexed, arrayListIterator, linkedListIndexed, linkedListIterator ...
}

Test Results

ArrayList for-loop time: 1
ArrayList iterator time: 2
LinkedList for-loop time: 47
LinkedList iterator time: 1

The results show that ArrayList traversed with a simple for loop is slightly faster than using an iterator, whereas LinkedList is dramatically faster when traversed with an iterator instead of a for loop.

Therefore, when choosing a List implementation for a specific scenario, consider whether it implements RandomAccess. Lists that implement RandomAccess (like ArrayList) are best traversed by index, while non‑ RandomAccess lists (like LinkedList) should be traversed with an iterator for optimal performance.

In short: Implementing RandomAccess means index‑based loops are more efficient; without it, iterator‑based loops win.