Definition
- Node structure:
private static class Node{ E item; Node next; Node prev; } - Head and tail: the list maintains
first(head) andlast(tail) pointers; an empty list has both set to null - Deque operations: addFirst/addLast/removeFirst/removeLast are O(1) – just pointer rewiring
- Random access:
get(index)is O(n) – traverses from the closer end (head if index < size/2, tail otherwise) - Implements: both
ListandDequeinterfaces
LinkedList is like a chain of safety deposit boxes in a bank vault. Each box has a label (the data), a tag pointing to the previous box, and a tag pointing to the next box. The vault manager keeps a note of which box is first and which is last. Adding a box at either end is instant – just update the tags and the manager's note. But finding box number 500 means walking through the chain from box 1 (or from the end), one box at a time.
Understanding the Concepts
What is the internal structure of LinkedList?
LinkedList is built from Node objects. Each Node holds three things: the element itself, a reference to the previous Node, and a reference to the next Node. The list also maintains two pointers: first (the head) and last (the tail).
Here is the simplified internal structure from OpenJDK:
package com.bank.demo;
public class SimpleLinkedList<E> {
private int size;
private Node<E> first; // head
private Node<E> last; // tail
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.prev = prev;
this.next = next;
}
}
public void addFirst(E e) {
Node<E> f = first;
Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) {
last = newNode; // list was empty
} else {
f.prev = newNode;
}
size++;
}
public void addLast(E e) {
Node<E> l = last;
Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode; // list was empty
} else {
l.next = newNode;
}
size++;
}
@SuppressWarnings("unchecked")
public E get(int index) {
// Optimization: start from closer end
Node<E> x;
if (index < (size >> 1)) {
x = first;
for (int i = 0; i < index; i++) x = x.next;
} else {
x = last;
for (int i = size - 1; i > index; i--) x = x.prev;
}
return x.item;
}
public int size() { return size; }
public static void main(String[] args) {
SimpleLinkedList<String> accounts = new SimpleLinkedList<>();
accounts.addLast("SAV2001");
accounts.addLast("CUR3001");
accounts.addFirst("FD4001");
System.out.println("Element at 0: " + accounts.get(0));
System.out.println("Element at 2: " + accounts.get(2));
System.out.println("Size: " + accounts.size());
}
}
Element at 0: FD4001
Element at 2: CUR3001
Size: 3
How do add and remove operations work?
All operations at the head or tail are O(1) because they only rewire 2-3 pointers. No elements need to move.
Adding at the head: create a new node, point its next to the current first, update the old first's prev to the new node, and set first to the new node.
Removing from the head: save the first node's item, set first to the first node's next, clear the old first node's references (to help GC), and update the new first node's prev to null.
Adding or removing in the middle requires finding the position first, which is O(n). But once the position is found, the actual link/unlink is O(1).
package com.bank.demo;
import java.util.*;
public class LinkedListOperationsDemo {
public static void main(String[] args) {
LinkedList<String> txnQueue = new LinkedList<>();
// addFirst / addLast: O(1)
txnQueue.addLast("TXN-001: Deposit 50000");
txnQueue.addLast("TXN-002: Withdraw 10000");
txnQueue.addFirst("TXN-000: High priority transfer");
System.out.println("Queue: " + txnQueue);
// removeFirst: O(1) – process from front
String processed = txnQueue.removeFirst();
System.out.println("Processed: " + processed);
// removeLast: O(1) – remove from back
String removed = txnQueue.removeLast();
System.out.println("Removed last: " + removed);
// peekFirst / peekLast: O(1) – read without removing
txnQueue.addLast("TXN-003: EMI payment");
System.out.println("Peek first: " + txnQueue.peekFirst());
System.out.println("Peek last: " + txnQueue.peekLast());
// get(index): O(n) – must traverse
txnQueue.addLast("TXN-004: Interest credit");
txnQueue.addLast("TXN-005: Statement fee");
System.out.println("get(1): " + txnQueue.get(1)); // traversal from head
}
}
Queue: [TXN-000: High priority transfer, TXN-001: Deposit 50000, TXN-002: Withdraw 10000]
Processed: TXN-000: High priority transfer
Removed last: TXN-002: Withdraw 10000
Peek first: TXN-001: Deposit 50000
Peek last: TXN-003: EMI payment
get(1): TXN-003: EMI payment
How does LinkedList implement the Deque interface?
LinkedList implements both List and Deque. This means you can use it as a queue (FIFO), a stack (LIFO), or a double-ended queue.
| Deque method | What it does | Time |
|---|---|---|
| offerFirst(e) / addFirst(e) | Insert at head | O(1) |
| offerLast(e) / addLast(e) | Insert at tail | O(1) |
| pollFirst() / removeFirst() | Remove from head | O(1) |
| pollLast() / removeLast() | Remove from tail | O(1) |
| peekFirst() / getFirst() | Read head without removing | O(1) |
| peekLast() / getLast() | Read tail without removing | O(1) |
| push(e) | Insert at head (stack push) | O(1) |
| pop() | Remove from head (stack pop) | O(1) |
The offer/poll/peek variants return null on failure. The add/remove/get variants throw exceptions.
package com.bank.service;
import java.util.*;
public class DequeUsageDemo {
public static void main(String[] args) {
// As a FIFO queue (first in, first out)
Deque<String> fifoQueue = new LinkedList<>();
fifoQueue.offerLast("Customer Rajesh");
fifoQueue.offerLast("Customer Priya");
fifoQueue.offerLast("Customer Amit");
System.out.println("Queue processing (FIFO):");
while (!fifoQueue.isEmpty()) {
System.out.println(" Serving: " + fifoQueue.pollFirst());
}
// As a LIFO stack (last in, first out)
Deque<String> undoStack = new LinkedList<>();
undoStack.push("Created account SAV2001");
undoStack.push("Deposited 50000");
undoStack.push("Set up auto-pay");
System.out.println("\nUndo stack (LIFO):");
while (!undoStack.isEmpty()) {
System.out.println(" Undo: " + undoStack.pop());
}
}
}
Queue processing (FIFO):
Serving: Customer Rajesh
Serving: Customer Priya
Serving: Customer Amit
Undo stack (LIFO):
Undo: Set up auto-pay
Undo: Deposited 50000
Undo: Created account SAV2001
How does the get(index) optimization work?
LinkedList optimizes get(index) by checking whether the index is in the first half or second half of the list. If index < size/2, it traverses forward from first. If index >= size/2, it traverses backward from last. This halves the average traversal time, but it is still O(n).
package com.bank.demo;
import java.util.*;
public class GetOptimizationDemo {
public static void main(String[] args) {
LinkedList<String> accounts = new LinkedList<>();
for (int i = 0; i < 10; i++) accounts.add("ACC" + i);
// get(2): index < 5 (size/2) → traverse from head
// head → ACC0 → ACC1 → ACC2 (3 hops)
System.out.println("get(2): " + accounts.get(2));
// get(8): index >= 5 → traverse from tail
// tail → ACC9 → ACC8 (2 hops – faster than 9 hops from head)
System.out.println("get(8): " + accounts.get(8));
}
}
get(2): ACC2
get(8): ACC8
What is the ListIterator advantage?
The only scenario where LinkedList genuinely outperforms ArrayList is when you use a ListIterator to insert or remove elements during traversal. At the iterator's current position, add() and remove() are O(1) on LinkedList because they just rewire pointers. On ArrayList, these operations are O(n) because elements must shift.
package com.bank.service;
import java.util.*;
public class ListIteratorDemo {
public static void main(String[] args) {
// Scenario: process transactions and insert audit entries inline
LinkedList<String> transactions = new LinkedList<>(List.of(
"TXN-001: Deposit",
"TXN-002: Withdraw",
"TXN-003: Transfer"
));
ListIterator<String> it = transactions.listIterator();
while (it.hasNext()) {
String txn = it.next();
// Insert audit entry after each transaction – O(1)!
it.add("[AUDIT] Verified: " + txn);
}
transactions.forEach(System.out::println);
}
}
TXN-001: Deposit
[AUDIT] Verified: TXN-001: Deposit
TXN-002: Withdraw
[AUDIT] Verified: TXN-002: Withdraw
TXN-003: Transfer
[AUDIT] Verified: TXN-003: Transfer
What about memory overhead?
Each LinkedList node is a separate Java object on the heap with the following layout (64-bit JVM with compressed oops):
- Object header: 12 bytes
itemreference: 4 bytesnextreference: 4 bytesprevreference: 4 bytes- Padding: 8 bytes (to align to 8-byte boundary)
Total per node: 32 bytes. Some JVMs may use 40 bytes depending on alignment.
For 1 million elements: LinkedList uses approximately 32-40 MB just for nodes, plus the elements themselves. ArrayList uses approximately 4 MB for the reference array.
The scattered allocation also means more work for the garbage collector, because it must track 1 million individual Node objects instead of one large array.
What are common mistakes with LinkedList?
Mistake 1: Using get(index) in a loop
// WRONG – O(n^2) because each get(i) is O(i)
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add("ACC" + i);
for (int i = 0; i < list.size(); i++) {
String acc = list.get(i); // O(i) traversal each time!
}
// Total: O(1 + 2 + 3 + ... + n) = O(n^2)
// CORRECT – use iterator (O(n) total)
for (String acc : list) {
// O(1) per iteration step
}
Mistake 2: Choosing LinkedList for a queue without considering ArrayDeque
// SUBOPTIMAL – LinkedList has memory overhead and cache misses
Queue<String> queue = new LinkedList<>();
// BETTER – ArrayDeque is faster for both queue and stack
Queue<String> queue = new ArrayDeque<>();
What about thread safety?
LinkedList is not thread-safe. For concurrent access:
- Use
Collections.synchronizedList(new LinkedList<>())for simple thread safety. - Use
ConcurrentLinkedDequefor a lock-free concurrent deque. - Use
LinkedBlockingDequefor a bounded blocking deque (producer-consumer pattern).
What should a senior engineer know?
- No random access marker. LinkedList does not implement RandomAccess. Algorithms in Collections check for this marker: Collections.binarySearch() uses an iterator-based approach for LinkedList instead of the index-based approach used for ArrayList. This makes binarySearch O(n) on LinkedList regardless.
- Null elements. LinkedList allows null elements, including multiple nulls. Be careful with remove(null) – it removes the first null found.
- Serialization. LinkedList has custom serialization that writes each element sequentially, not the node objects. The deserialized list creates fresh nodes. This makes serialization format efficient.
- descendingIterator(). LinkedList provides descendingIterator() for backward traversal without the overhead of a ListIterator.
- GC pressure. Each add() creates a new Node object. In a high-throughput banking system adding millions of elements, this creates GC pressure. ArrayList creates no objects during add (unless resizing). This is another reason ArrayList is preferred.
What are common interview follow-up questions?
- "What is the time complexity of get(500) on a LinkedList with 1000 elements?" – O(500), traverses from head. With 600: O(400), traverses from tail.
- "Can you implement a stack using LinkedList?" – Yes, push = addFirst, pop = removeFirst.
- "Why is ArrayDeque faster than LinkedList for queue operations?" – Contiguous circular array, cache-friendly, no node object creation.
- "What happens when you call get(index) on a LinkedList with a negative index?" – Throws IndexOutOfBoundsException.
Visual Overview
LinkedList internal structure
first last
↓ ↓
┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐
│ prev:null│ │ prev: ←──│─────│ prev: ←──│─────│ prev: ←──│
│ item: A │ │ item: B │ │ item: C │ │ item: D │
│ next: ──→│─────│ next: ──→│─────│ next: ──→│─────│ next:null│
└──────────┘ └──────────┘ └──────────┘ └──────────┘
Node 0 Node 1 Node 2 Node 3
addFirst(X):
┌──────────┐
│ prev:null│──→ old first
│ item: X │
│ next: ──→│──→ A
└──────────┘
first = X, A.prev = X (2 pointer updates = O(1))
get(2): index < size/2?
YES → traverse from first: A → B → C (2 hops)
NO → traverse from last: D → C (1 hop)
Key Takeaway
LinkedList is a doubly-linked list where each element lives in a Node object with item, prev, and next references. The list keeps first and last pointers, making operations at both ends O(1) – just pointer rewiring, no element shifting. But random access is O(n) because there is no way to jump to a position; you must traverse the chain.
LinkedList implements both List and Deque, so you can use it as a queue (offerLast/pollFirst), a stack (push/pop), or a regular list. But in modern Java, ArrayDeque is faster for all deque operations because its contiguous array is cache-friendly. LinkedList's scattered heap nodes cause cache misses that dominate the runtime.
The one scenario where LinkedList truly shines is ListIterator-based modification during traversal. At the iterator's current position, add and remove are O(1) – just rewire the prev and next pointers. On ArrayList, the same operations shift all subsequent elements.
Remember one sentence: LinkedList is O(1) at both ends and O(1) at the iterator position, but O(n) for random access, 10x heavier in memory, and slower than ArrayDeque for queue and stack operations.
---