Java Notes
Complete guide to Java LinkedList — internal working with doubly-linked nodes, performance analysis, Deque operations, comparison with ArrayList, and when to use LinkedList.
What is LinkedList?
java.util.LinkedList is a doubly-linked list implementation of both the List and Deque interfaces. Unlike ArrayList (which uses a resizable array), LinkedList stores elements in nodes, where each node holds a reference to the previous and next node.
// LinkedList implements both List and Deque
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, SerializableHow Operations Work Internally
Adding at the End — add(E e) / addLast(E e)
Time: O(1) — Just update the last pointer and create a node.
Adding at the Beginning — addFirst(E e)
Time: O(1) — Just update the first pointer.
Adding at an Index — add(int index, E element)
// Simplified logic:
// 1. Find the node at the given index (traversal)
// 2. Insert the new node before itTime: O(n) — Must traverse to find the position. However, LinkedList optimizes by starting from the closer end:
Getting an Element — get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item; // Must traverse to the node!
}Time: O(n) — This is the major disadvantage of LinkedList. Even with the halfway optimization, accessing element at index n/2 still requires traversing half the list.
Removing an Element — remove(Object o)
Unlinking is O(1) once you have the node reference. But finding the node is O(n).
Time Complexity Summary
| Operation | Time Complexity | Notes |
|---|---|---|
| ----------- | :-: | --- |
add(E e) (end) | O(1) | Has direct last pointer |
addFirst(E e) | O(1) | Has direct first pointer |
add(int index, E e) | O(n) | Must traverse to index |
get(int index) | O(n) | Must traverse to index |
set(int index, E e) | O(n) | Must traverse to index |
remove(int index) | O(n) | Must traverse to index |
removeFirst() | O(1) | Direct access to head |
removeLast() | O(1) | Direct access to tail |
contains(Object o) | O(n) | Linear search |
size() | O(1) | Maintained as field |
iterator.remove() | O(1) | Already at the node |
LinkedList as a Deque
LinkedList implements Deque, making it a double-ended queue:
LinkedList<String> deque = new LinkedList<>();
// Queue operations (FIFO)
deque.offer("First"); // Add to tail
deque.offer("Second");
deque.offer("Third");
String head = deque.poll(); // Remove from head → "First"
// Stack operations (LIFO)
deque.push("Top"); // Add to head
String top = deque.pop(); // Remove from head → "Top"
// Deque operations
deque.offerFirst("Front");
deque.offerLast("Back");
deque.peekFirst(); // See front without removing
deque.peekLast(); // See back without removing
deque.pollFirst(); // Remove from front
deque.pollLast(); // Remove from backComplete Example
Output:
| List | [Apple, Avocado, Banana, Cherry] |
| First | Apple |
| Last | Cherry |
| At index 2 | Banana |
| After removals | [Banana] |
| Popped | Pushed |
| Polled | Banana |
LinkedList vs ArrayList — Deep Comparison
Memory Layout
Memory Overhead
For each element:
- ArrayList: ~4-8 bytes (one reference in the array)
- LinkedList: ~48 bytes per node on 64-bit JVM (prev pointer + next pointer + item pointer + object header)
That's 6-12x more memory per element!
Cache Performance
- ArrayList: Elements are stored in a contiguous block → CPU cache-friendly → hardware prefetching works great
- LinkedList: Nodes are scattered in heap → cache misses on every traversal → much slower in practice
When ArrayList Beats LinkedList (Almost Always)
// Random access — ArrayList O(1) vs LinkedList O(n)
list.get(500); // ArrayList: instant | LinkedList: traverse 500 nodes
// Even sequential iteration is faster in ArrayList due to cache locality!
for (String s : list) { ... } // ArrayList wins due to memory layoutWhen LinkedList Can Be Better
// Constant-time operations at both ends (when used as Deque)
deque.addFirst(element);
deque.removeLast();
// Iteration + removal pattern (via Iterator)
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if (condition) it.remove(); // O(1) unlink — no array shifting
}Thread Safety
LinkedList is NOT thread-safe. For concurrent access:
// Option 1: Synchronized wrapper
List<String> syncList = Collections.synchronizedList(new LinkedList<>());
// Option 2: ConcurrentLinkedDeque (for deque operations)
Deque<String> concurrentDeque = new ConcurrentLinkedDeque<>();
// Option 3: LinkedBlockingDeque (blocking operations)
BlockingDeque<String> blockingDeque = new LinkedBlockingDeque<>();Common Mistakes
1. Using LinkedList for Random Access
2. Choosing LinkedList by Default
// DON'T do this — ArrayList is almost always better
List<String> items = new LinkedList<>(); // Wrong default choice!
// DO this — ArrayList is the default choice
List<String> items = new ArrayList<>();3. Thinking remove(Object) is O(1)
// The UNLINKING is O(1), but FINDING the node is O(n)!
list.remove("target"); // Still O(n) — must traverse to find itInterview Questions
Q1: How is LinkedList implemented internally?
A: As a doubly-linked list with Node objects containing prev, item, and next references. The list maintains first and last pointers for O(1) access to both ends.
Q2: When should you use LinkedList over ArrayList?
A: When you primarily do insertions/removals at the beginning or end (Deque operations), or when iterating and removing elements frequently via Iterator. In practice, ArrayList is almost always better due to CPU cache performance.
Q3: Is LinkedList.get(index) O(1)?
A: No! It's O(n). LinkedList optimizes by starting traversal from whichever end is closer, but it's still linear.
Q4: Can LinkedList contain null elements?
A: Yes. Unlike some other collections, LinkedList allows null elements and multiple nulls.
Q5: What interfaces does LinkedList implement?
A: List, Deque, Queue, Cloneable, Serializable. This makes it usable as a list, queue, stack, or double-ended queue.
Q6: How much memory overhead does LinkedList have compared to ArrayList?
A: Significantly more. Each node requires ~48 bytes (on 64-bit JVM) for pointers and object headers, vs ~4-8 bytes per element in ArrayList. For 1 million elements, LinkedList uses ~48MB extra.
Q7: Why is iterating LinkedList slower than ArrayList even though both are O(n)?
A: Because of cache locality. ArrayList stores references in contiguous memory, enabling CPU prefetching. LinkedList nodes are scattered across the heap, causing frequent cache misses.
Complete Runnable Example
import java.util.LinkedList;
import java.util.Iterator;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
// Adding elements
list.add("B");
list.addFirst("A"); // Add at beginning
list.addLast("D"); // Add at end
list.add(2, "C"); // Add at index
System.out.println("List: " + list);
// Accessing elements
System.out.println("First: " + list.getFirst());
System.out.println("Last: " + list.getLast());
System.out.println("At index 2: " + list.get(2));
// Queue operations (FIFO)
System.out.println("Peek: " + list.peek());
System.out.println("Poll: " + list.poll());
System.out.println("After poll: " + list);
// Stack operations (LIFO)
list.push("Z");
System.out.println("After push Z: " + list);
System.out.println("Pop: " + list.pop());
// Removing elements
list.removeFirst();
list.removeLast();
System.out.println("After remove first & last: " + list);
// Size and contains
System.out.println("Size: " + list.size());
System.out.println("Contains C: " + list.contains("C"));
}
}List: [A, B, C, D] First: A Last: D At index 2: C Peek: A Poll: A After poll: [B, C, D] After push Z: [Z, B, C, D] Pop: Z After remove first & last: [B, C] Size: 2 Contains C: true
Q8: What is the difference between poll() and remove() in LinkedList?
A: Both remove the first element. remove() throws NoSuchElementException if the list is empty. poll() returns null if the list is empty. Use poll() when empty list is a valid scenario; use remove() when empty list indicates a bug.
Q9: Why is LinkedList preferred for implementing Queue/Deque?
A: LinkedList offers O(1) insertion and removal at both ends (first and last), making it ideal for FIFO (Queue) and LIFO (Stack/Deque) operations. ArrayDeque is actually even faster due to cache locality, but LinkedList also implements the List interface for indexed access.
Q10: Does LinkedList use more memory than ArrayList?
A: Yes, significantly more. Each LinkedList node stores the data plus two object references (prev and next), plus object header overhead — approximately 48 bytes per node on 64-bit JVM. ArrayList stores only the reference (~4-8 bytes per element in the backing array).
Q11: How does LinkedList perform with large datasets compared to ArrayList?
A: For sequential access (iteration), both are O(n) but ArrayList is faster due to CPU cache locality (contiguous memory). For random access, ArrayList is O(1) vs LinkedList O(n). LinkedList only wins for frequent insertions/removals at known positions with an existing iterator reference.
Q12: Can LinkedList be used as both Stack and Queue?
A: Yes! LinkedList implements both Deque and List. As Queue: use offer()/poll()/peek(). As Stack: use push()/pop()/peek(). As List: use get(index)/add(index, element). This versatility is one reason LinkedList exists despite ArrayDeque being faster for pure stack/queue use.
Summary
| Aspect | LinkedList |
|---|---|
| Structure | Doubly-linked nodes |
| Best for | Deque operations, Iterator-based removal |
| Worst for | Random access, large datasets |
| Memory | High overhead per element (~48 bytes/node) |
| Cache performance | Poor (scattered memory) |
| Thread-safe | No (use ConcurrentLinkedDeque) |
| Null elements | Allowed |
| Default choice? | No — prefer ArrayList or ArrayDeque |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for LinkedList in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, list
Related Java Master Course Topics