What is the time complexity of operations in LinkedList?

🟢 Junior Level

LinkedList — doubly-linked list where each element is a separate object.

Operation	Complexity	Explanation
`get(index)`	O(n)	Need to iterate through elements
`add(e)`	O(1)	Append to end
`addFirst(e)`	O(1)	Add to beginning
`add(index, e)`	O(n)	Need to find position
`remove(index)`	O(n)	Need to find position
`iterator.remove()`	O(1)	If iterator already reached the element (i.e., you’re traversing and removing current)

Important: get(index) is slow!

// ❌ Slow: O(n²)
for (int i = 0; i < list.size(); i++) {
    list.get(i);  // Traversal each time!
}

// ✅ Fast: O(n)
for (String s : list) {
    // One traversal
}

🟡 Middle Level

Operation details

// get(index): O(n)
// → Traversal from head OR tail (whichever closer)
// → No random access!

// add(e): O(1)
// → Append to end
// → No resizes (unlike ArrayList)

// add(0, e): O(1)
// → Add to beginning
// → Faster than ArrayList (no shift)

// add(index, e): O(n)
// → O(n) to find position
// → O(1) to insert
// → Total: O(n)

// iterator.remove(): O(1)
// → The only advantage!
// → If iterator already at element

Iteration trap

// ❌ O(n²) — classic mistake!
LinkedList<String> list = ...;
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);  // O(n) each time!
    // Total: n × n = n²
}

// ✅ O(n) — use foreach
for (String s : list) {
    // One traversal
}

// ✅ O(n) — use iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
}

Memory

LinkedList Node: 32 bytes
  → Object Header: 12 bytes
  → item reference: 4 bytes
  → next reference: 4 bytes
  → prev reference: 4 bytes
  → Padding: 8 bytes

ArrayList: 4 bytes per reference
  → Only reference in array

→ LinkedList uses 8x more memory!

🔴 Senior Level

When NOT to use LinkedList

If performance matters — ArrayList or ArrayDeque always faster
If cache locality needed — LinkedList nodes scattered across heap
If memory limited — LinkedList wastes 24+ bytes per node (prev + next + item)

Cache Locality catastrophe

CPU Cache Line: 64 bytes

ArrayList:
  [ref1][ref2][ref3][ref4]...
  → 1 read → 8 refs in L1
  → Iteration: minimum cache misses

LinkedList:
  [Node1]...[Node2]...[Node3]
  → Each next = cache miss
  → RAM wait: 100+ cycles
  → Pipeline stall — CPU forced to wait for RAM data, entire instruction pipeline stops. Costs 100-300 CPU cycles.

GC Pressure

LinkedList: 1M elements
  → 1M Node objects
  → 32 MB overhead
  → Minor GC: scan 1M objects

ArrayList: 1M elements
  → 1 Object[] array
  → 4 MB
  → GC: one ref

When is LinkedList O(1) actually faster?

Theory: LinkedList.add(0, e) = O(1)
Reality: ArrayList faster up to ~10-20k elements!

Why?
  LinkedList: new Node() → allocation → 3 refs
  ArrayList: System.arraycopy() → SIMD

→ Object allocation MORE EXPENSIVE than array shift!

For small lists (< 10-20k elements). On large lists with frequent head insertions, LinkedList may win.

The only case for LinkedList

// VERY large list + removal via iterator
LinkedList<String> list = new LinkedList<>();

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // O(1) — just relinking refs
    }
}

// ArrayList: O(n) — shift array each time
// BUT! removeIf() in ArrayList also O(n) once!
list.removeIf(e -> shouldRemove(e));  // Use this!

Java 21: SequencedCollection

// LinkedList now SequencedCollection
list.getFirst();   // O(1)
list.getLast();    // O(1)
list.reversed();   // O(1) — view

// ArrayDeque supports too
// And faster!

Best Practices

Avoid LinkedList — in vast majority ArrayList or ArrayDeque work better
Never use get(index) in loop
ArrayDeque > LinkedList for queues/stacks
removeIf() > iteration with removal
foreach > for-i for LinkedList
Memory: LinkedList 8x larger
GC: LinkedList creates millions of objects

Summary for Senior

get(index) = O(n) — main disadvantage
add/remove(0) = O(1) — but ArrayList faster on small
iterator.remove() = O(1) — only real advantage
Cache Miss on every element → pipeline stalls
GC Pressure = 32 bytes × N objects
O(n²) trap — use foreach, not for-i
removeIf() > iteration with removal
ArrayDeque > LinkedList always for stacks/queues

🎯 Interview Cheat Sheet

Must know:

get(index) = O(n) — traversal from head or tail (whichever closer), no random access
add(e)/addFirst(e) = O(1), but ArrayList faster on small lists thanks to SIMD
iterator.remove() = O(1) — only real advantage of LinkedList
Memory: 32 bytes per element (Object header + item + next + prev + padding) — 8x more than ArrayList
Cache Miss catastrophe: each next = 100+ cycles RAM wait, pipeline stalls
O(n²) trap: for-i with get(i) = n × O(n) = O(n²), use foreach or iterator
GC Pressure: 1M elements = 1M Node objects = 32 MB overhead
ArrayDeque > LinkedList for stacks/queues — faster and less GC pressure

Common follow-up questions:

Why LinkedList.add(0,e) = O(1) but slower than ArrayList? — Node object allocation more expensive than System.arraycopy() for small lists
When is iterator.remove() = O(1) actually useful? — When removing via iterator in VERY large lists (100k+), where removeIf() can’t be used
What is O(n²) trap? — for-i loop with get(i): each get(i) = O(n), total n×n = O(n²)
Why LinkedList bad for cache? — Nodes scattered across heap, each next = cache miss → RAM wait

Red flags (NOT to say):

❌ “LinkedList faster than ArrayList for insertion” — only on lists >10-20k, and not always
❌ “Use for-i for LinkedList” — that’s O(n²), use foreach/iterator
❌ “LinkedList saves memory” — opposite, 32 bytes vs 4 bytes per element
❌ “LinkedList — good choice for queue” — ArrayDeque always better

Related topics:

[[What is the difference between ArrayList and LinkedList]]
[[When to use ArrayList vs LinkedList]]
[[What is the time complexity of operations in ArrayList]]
[[What is Deque]]