LinkedList

LinkedList as both a List and a Deque — when it actually beats ArrayList and when to use ArrayDeque instead.

Last reviewed: January 2025

·Java 8Java 11Java 17Java 21
✅
Quick Understanding: LinkedList is a doubly-linked list that implements both List and Deque. Its main advantage over ArrayList is O(1) insert/remove at both ends and O(1) insert/remove at a known iterator position. However, due to poor cache locality, ArrayList is faster in practice for most operations. Use LinkedList mainly when you need a Deque (double-ended queue) — or better yet, use ArrayDeque instead.

🔍 What Is It?

LinkedList implements both java.util.List and java.util.Deque:

As a List:

  • →All List operations available
  • →get(index): O(n) — must traverse from head or tail
  • →add(index, element): O(n) to find position + O(1) to insert
  • →remove(index): O(n) to find + O(1) to remove

As a Deque (double-ended queue):

  • →addFirst/offerFirst: O(1)
  • →addLast/offerLast: O(1)
  • →removeFirst/pollFirst: O(1)
  • →removeLast/pollLast: O(1)
  • →peekFirst/peekLast: O(1)

Memory:

Each element is a Node object with:

  • →Object item (the element)
  • →Node next (pointer to next)
  • →Node prev (pointer to previous)

Overhead: ~40 bytes per element (vs ~4-8 bytes for ArrayList)

🎯 Why Do We Need It?

LinkedList is the right choice when: (1) you need a queue or stack with O(1) operations at both ends, (2) you are using an Iterator and need O(1) insert/delete at the current position. In most other cases, ArrayList is better.

🏗️ What Happens in Real Projects?

Real use cases:

  • →Task queue: add tasks to end, process from front
  • →Undo/redo stack: add to front, remove from front
  • →Browser history: deque where you add pages and navigate back/forward
  • →LRU cache implementation: move accessed nodes to front efficiently

In practice, most of these use cases are better served by ArrayDeque.

⚙️ How It Works

Node Structure:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

add(index, element):

  1. If index == 0: addFirst (O(1))
  2. If index == size: addLast (O(1))
  3. Otherwise: traverse to index (O(n)), then insert (O(1))

Why cache locality matters:

ArrayList stores elements in one contiguous memory block. When you iterate, the CPU prefetches the next elements. LinkedList nodes are scattered — each node access is likely a cache miss. This makes LinkedList iteration 3-10x slower than ArrayList in practice.

💻 Example

LinkedList as a Deque — The main legitimate use case for LinkedList in enterprise code.

java
// LinkedList as a Queue (FIFO)
Queue<String> taskQueue = new LinkedList<>();
taskQueue.offer("task1");  // add to end
taskQueue.offer("task2");
taskQueue.offer("task3");

String next = taskQueue.poll();   // remove from front: "task1"
String peek = taskQueue.peek();   // look at front without removing: "task2"

// LinkedList as a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("first");   // addFirst
stack.push("second");  // addFirst
stack.push("third");   // addFirst

String top = stack.pop();   // removeFirst: "third"
String look = stack.peek(); // peekFirst: "second"

// BUT: ArrayDeque is faster for both Queue and Stack!
// Prefer ArrayDeque over LinkedList for queue/stack use cases
Deque<String> betterStack = new ArrayDeque<>();
Queue<String> betterQueue = new ArrayDeque<>();

// When LinkedList wins: O(1) insert at iterator position
List<String> list = new LinkedList<>(List.of("a", "b", "c", "d", "e"));
ListIterator<String> it = list.listIterator(2);  // position at index 2
it.add("X");  // O(1) insert at current position
// [a, b, X, c, d, e]
it.remove();  // O(1) remove current element

🤔 Common Confusions

❓ Is LinkedList really O(1) for insert in the middle?

Only if you already have an iterator/reference at the insertion point. Finding the position is O(n). So add(index, element) is O(n) overall because you must traverse to the index first. The O(1) advantage only applies when you already have a ListIterator positioned at the right place.

❓ Should I use LinkedList or ArrayDeque for a queue?

ArrayDeque. It is faster than LinkedList for queue/stack operations because of better cache locality (circular array vs scattered nodes). ArrayDeque also uses less memory. LinkedList has no advantage over ArrayDeque for queue/stack use cases. The Java documentation itself recommends ArrayDeque over LinkedList for stacks.

🚨 Common Production Issues

Using LinkedList.get(index) in a loop — this is O(n) per call, making the loop O(n²). If you need index access, use ArrayList.

High memory overhead — each LinkedList node uses ~40 bytes. For 1 million elements, that is 40MB just for node overhead. ArrayList uses ~8MB for the same elements.

✅ Best Practices

Use ArrayDeque instead of LinkedList for queue and stack use cases.

Use ArrayList instead of LinkedList for general-purpose lists.

Use LinkedList only when you need O(1) insert/delete at an iterator position in a large list.

Never use LinkedList.get(index) in a loop — it is O(n²).

🏛️ Architect's Note

Senior Architect's Perspective

LinkedList is one of those data structures that looks good in theory (O(1) insertions) but underperforms in practice due to CPU cache effects. Modern CPUs are so fast at sequential memory access that ArrayList's O(n) shift is often faster than LinkedList's O(1) pointer update when the list fits in cache. Always benchmark before assuming LinkedList is faster.

💬 Frequently Asked Questions

What is the difference between Queue and Deque?

Queue is single-ended: you add to the back and remove from the front (FIFO). Deque (Double-Ended Queue) supports add/remove from both ends — it can be used as a FIFO queue or LIFO stack. LinkedList implements both. ArrayDeque implements Deque but not Queue directly (though it can be used as one).

🎯 Key Takeaways

1LinkedList implements both List and Deque
2O(1) add/remove at both ends; O(n) random access by index
3Poor cache locality makes it slower than ArrayList for most real workloads
4Use ArrayDeque instead for queue/stack — it is faster and uses less memory
5Only advantage: O(1) insert/delete at a known iterator position in a large list
6Never use get(index) in a loop with LinkedList — it is O(n²)

🎯 Practice this topic in interviews

↗ Where this topic fits

Sources

Sources / References

Use these Core Java references to verify the concept in official docs and continue into the most relevant SplashRide pages.