Java With Us

<code>LinkedList</code> in Java — Doubly Linked List

Updated on 2026-04-21 Reviewed by the Java With Us editorial team

LinkedList is a doubly-linked list that also implements Deque. On paper, that's attractive: O(1) insert/remove at both ends. In practice, cache locality kills it — ArrayList beats LinkedList at almost every real workload, including head and tail operations for small lists.

API (when you insist)

var list = new LinkedList<String>();
list.addFirst("a");               // at head — O(1)
list.addLast("b");                // at tail — O(1)
list.add("c");                    // same as addLast
list.get(0);                      // O(n) — random access is SLOW
list.peekFirst();                 // head, or null
list.pollLast();                  // remove and return tail
list.removeFirst();               // throws if empty

Why it's rarely the right choice

OperationArrayListLinkedList
Random access get(i)O(1) — cache-friendlyO(n)
Add at endAmortised O(1)O(1)
Add at startO(n)O(1)
Memory overhead per element~4-8 bytes~32-48 bytes (two pointers + object header)
Cache localityExcellentPoor — every node allocated separately

Modern CPUs fetch memory in 64-byte lines. ArrayList's contiguous data blazes through; LinkedList chases pointers and misses the cache on almost every step.

When LinkedList could win

  • Extremely large lists where you insert/remove mostly in the middle, through an existing ListIterator that already holds the position.
  • Legacy APIs that return LinkedList.

For queue-like usage, ArrayDeque is faster than LinkedList for both FIFO and LIFO. The JDK itself uses ArrayDeque in BlockingQueue implementations.

Common mistakes

  • Picking LinkedList because "linked = fast inserts" — cache locality usually wins. Benchmark before choosing.
  • Calling get(i) in a loop — each call is O(n), so the loop is O(n²). Use for-each or an Iterator.
  • Using as a queue — ArrayDeque is strictly better.

Related

Pillar: Java collections. Prefer ArrayList or ArrayDeque.

Related articles