Course contentsShow
← Java
Lesson 1029 of 2,87024. List ImplementationsFree lesson

Why No Index-Based Access Optimization

LinkedList must traverse from head or tail to reach any index, resulting in O(n) get() performance.

Why No Index-Based Access Optimization

You'll learn why LinkedList struggles with indexed operations, making get(index) surprisingly slow.

The Fundamental Problem

Unlike ArrayList, which stores elements in a contiguous array allowing instant jumps to any position, LinkedList uses a chain of nodes connected by references. There's no way to "jump" directly to the 100th element—you must walk through the chain, one node at a time, following the next or prev references.

When you call get(5) on a LinkedList, Java must start at either the head or tail reference and traverse through the nodes, counting as it goes, until it reaches the 5th position. This makes every indexed access an O(n) operation in the worst case.

Why This Matters

The doubly-linked structure that makes insertions and deletions efficient at known positions becomes a liability for random access:

  • ArrayList.get(index): O(1) — direct array lookup
  • LinkedList.get(index): O(n) — must traverse up to n nodes

Java does optimize slightly: if the requested index is closer to the tail than the head, it starts from the tail and works backward. But this only halves the average traversal distance—it's still linear.

The Analogy

Think of ArrayList as a numbered parking lot where you can drive directly to space #47. LinkedList is like a train: to reach car #47, you must walk through cars 1, 2, 3... all the way to 47. No shortcuts exist.

This is why loops like for (int i = 0; i < list.size(); i++) { list.get(i); } are catastrophically slow with LinkedList—each get() repeats the traversal from scratch, resulting in O(n²) overall performance.

Key Takeaway:
LinkedList has no index-based access optimization because its node structure requires sequential traversal, making get(index) an O(n) operation unsuitable for random access patterns.