LinkedList in Java
- LinkedList is a doubly-linked list that also implements Deque — it shines as a queue.
- Random access (get(i)) is O(n) — LinkedList has to traverse from the head.
- Head/tail insert and remove are O(1) — the genuine advantage over ArrayList.
Java's LinkedList is a doubly-linked list that also implements Deque. It excels at O(1) insertions and deletions at the head or tail, but is slow (O(n)) for random access. For most use cases ArrayList is faster due to CPU cache locality. Use LinkedList specifically when you need a queue/deque with frequent head/tail operations.
LinkedList as a List
package io.thecodeforge.java.collections; import java.util.LinkedList; import java.util.List; public class LinkedListBasics { public static void main(String[] args) { List<String> list = new LinkedList<>(); list.add("banana"); list.add("cherry"); list.add(0, "apple"); // insert at head — O(1) for LinkedList, O(n) for ArrayList System.out.println(list); // [apple, banana, cherry] System.out.println(list.get(1)); // banana — O(n) traversal list.remove(1); // O(n) to find, O(1) to remove System.out.println(list); // [apple, cherry] } }
banana
[apple, cherry]
LinkedList as a Deque
This is where LinkedList has a genuine advantage — O(1) add/remove at both ends. Use it when you need a queue or deque with frequent operations at both ends.
package io.thecodeforge.java.collections; import java.util.Deque; import java.util.LinkedList; public class LinkedListDeque { public static void main(String[] args) { Deque<Integer> deque = new LinkedList<>(); // O(1) operations at both ends deque.addFirst(2); // [2] deque.addFirst(1); // [1, 2] deque.addLast(3); // [1, 2, 3] deque.addLast(4); // [1, 2, 3, 4] System.out.println(deque.peekFirst()); // 1 System.out.println(deque.peekLast()); // 4 System.out.println(deque.pollFirst()); // 1 — remove from front System.out.println(deque.pollLast()); // 4 — remove from back System.out.println(deque); // [2, 3] } }
4
1
4
[2, 3]
LinkedList vs ArrayList — When to Choose Which
package io.thecodeforge.java.collections; import java.util.*; public class Benchmark { static final int N = 100_000; public static void main(String[] args) { // Scenario 1: Random access — ArrayList wins decisively List<Integer> arrayList = new ArrayList<>(Collections.nCopies(N, 1)); List<Integer> linkedList = new LinkedList<>(Collections.nCopies(N, 1)); long start = System.nanoTime(); for (int i = 0; i < 10_000; i++) arrayList.get(N / 2); System.out.printf("ArrayList random access: %,dns%n", System.nanoTime() - start); start = System.nanoTime(); for (int i = 0; i < 10_000; i++) linkedList.get(N / 2); System.out.printf("LinkedList random access: %,dns (much slower)%n", System.nanoTime() - start); // Scenario 2: Insert at head — LinkedList wins start = System.nanoTime(); for (int i = 0; i < 10_000; i++) arrayList.add(0, 0); System.out.printf("ArrayList head insert: %,dns%n", System.nanoTime() - start); Deque<Integer> deque = new LinkedList<>(); start = System.nanoTime(); for (int i = 0; i < 10_000; i++) deque.addFirst(0); System.out.printf("LinkedList head insert: %,dns%n", System.nanoTime() - start); } }
LinkedList random access: 8,000,000ns (much slower)
ArrayList head insert: 15,000,000ns
LinkedList head insert: 120,000ns
🎯 Key Takeaways
- LinkedList is a doubly-linked list that also implements Deque — it shines as a queue.
- Random access (get(i)) is O(n) — LinkedList has to traverse from the head.
- Head/tail insert and remove are O(1) — the genuine advantage over ArrayList.
- For most workloads ArrayList is faster because of CPU cache locality.
- Prefer ArrayDeque over LinkedList even for queue use — it is faster and uses less memory.
Interview Questions on This Topic
- QWhat is the time complexity of get(i) for LinkedList vs ArrayList?
- QWhen would you choose LinkedList over ArrayDeque for a queue?
- QWhy is iterating over ArrayList typically faster than LinkedList despite the same O(n) complexity?
Frequently Asked Questions
When does LinkedList beat ArrayList in practice?
When you have a very large list and need frequent insertions and deletions at the front or back, and you never need random access by index. The most common real case is implementing a FIFO queue or deque. Even then, ArrayDeque is usually faster — use LinkedList when you specifically need the List interface alongside Deque.
Why is LinkedList slower for iteration despite O(n) complexity on both?
CPU cache. ArrayList stores elements in a contiguous block of memory — iterating it pre-fetches elements into cache automatically. LinkedList nodes are scattered across the heap — each next pointer dereference is likely a cache miss. At modern CPU speeds, cache misses are 100-200x slower than a cache hit.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.