ArrayList vs LinkedList get(index) Time Complexity
Fast recall
Quick revision
Core answer
ArrayList.get(index) is O(1) because it uses direct indexed access in its backing array. LinkedList.get(index) is O(n) in the worst case because it follows links from the nearer end. Repeated indexed access over a LinkedList can therefore make an otherwise linear-looking loop O(n²).Whether you know why array indexing is constant time and node traversal is linear
Thinking LinkedList.get is fast, or not spotting the O(n^2) trap of indexed loops over a LinkedList
Note LinkedList.get optimizes by starting from whichever end is closer, but it's still O(n)
Interview-ready guide
Interview answer
ArrayList's get with an index is constant time, O(1), and LinkedList's get is linear time, O(n).
The reason comes down to how each stores data. ArrayList is backed by an array, and arrays are contiguous in memory. So to find element i, the JVM just does a quick calculation — direct indexed access in the backing array — and jumps straight there.
No searching at all. LinkedList stores each element in a node scattered somewhere on the heap, and the nodes are connected by pointers. There's no index, so to reach position i the list has to follow the next references one node at a time, starting from the head.
The JDK does add a small optimization — it checks whether i is in the first half or second half and starts from whichever end is closer — but that's still linear in the worst case. The really important consequence is what happens in a loop.
If you write a normal for-loop that calls get(i) for every index, that's fine on an ArrayList because each call is constant time, so the whole loop is linear. But on a LinkedList, each get(i) re-walks the chain, so the loop becomes quadratic, O(n squared). For a large list that's a real performance bug.
The fix is simple: when you traverse a LinkedList, use a for-each loop or an iterator, which moves one node forward each step and stays linear overall. This constant-time indexing is a big part of why ArrayList is the default list in Java.
ArrayList vs LinkedList get(index) Time Complexity
Direct Answer
ArrayList.get(index) is O(1) because it uses direct indexed access in its backing array. LinkedList.get(index) is O(n) in the worst case because it follows links from the nearer end. Repeated indexed access over a LinkedList can therefore make an otherwise linear-looking loop O(n²).
Code Example
import java.util.*;
public class GetComplexity {
public static void main(String[] args) {
int n = 50_000;
List<Integer> arr = new ArrayList<>();
List<Integer> lnk = new LinkedList<>();
for (int i = 0; i < n; i++) { arr.add(i); lnk.add(i); }
// ArrayList: O(1) per get -> O(n) total
long s1 = 0; for (int i = 0; i < n; i++) s1 += arr.get(i);
// LinkedList: O(n) per get -> O(n^2) total (slow!)
long s2 = 0; for (int i = 0; i < n; i++) s2 += lnk.get(i);
// Correct way to traverse a LinkedList: for-each is O(n)
long s3 = 0; for (int v : lnk) s3 += v;
}
}
Common Mistakes & Pitfalls
- Indexed loop on a LinkedList.
for (i...) list.get(i)is O(n^2). Use a for-each or iterator. - Assuming all
getis O(1). It's only O(1) for array-backed lists like ArrayList. - Ignoring the RandomAccess marker. ArrayList implements
RandomAccess; well-written library code checks this to pick index vs iterator access. - Forgetting the nearest-end optimization. LinkedList.get(size-1) is cheap-ish, but middle indices are the worst case.
Check your understanding
Answer these without looking back at the article.
- What happens if you call get(i) in a for loop on a LinkedList?
- How does Iterator avoid the O(n²) problem?
- Does ArrayList.get ever throw an exception?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.