Linked List Fundamentals
Nodes and references, why insertion is O(1) but access is O(n), and the dummy-head trick that removes edge cases.
On this page
Linked lists rarely appear in production Java - ArrayList wins almost every real use case - yet they
dominate interviews. Why? Because they test the one skill an array can't: manipulating references
by hand. Get comfortable with nodes and pointers here, and the reversal and cycle problems that
follow become routine.
Nodes and references
A linked list is a chain of nodes, each holding a value and a reference to the next node. There's
no contiguous block of memory and no index - to reach the fifth element you must walk from the head
through four next pointers.
class ListNode {
int val;
ListNode next; // reference to the next node, or null at the end
ListNode(int val) { this.val = val; }
}
// traverse: walk until you fall off the end
ListNode node = head;
while (node != null) {
process(node.val);
node = node.next; // step forward
}This gives linked lists the opposite performance profile from arrays:
| Operation | Array (ArrayList) | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) - must walk |
| Insert/delete at a known node | O(n) - shift elements | O(1) - re-point references |
| Memory | contiguous, compact | scattered, extra pointer per node |
The trade is the whole point: linked lists make insertion and deletion cheap (just re-point a couple of references) at the cost of losing O(1) random access.
The dummy-head trick
Linked-list code is a minefield of edge cases: inserting before the head, deleting the head, an empty list. A dummy (sentinel) head node - a throwaway node placed before the real head - erases most of them, because now every real node has a predecessor to point at:
// remove all nodes with a target value — dummy head handles deleting the head
ListNode removeElements(ListNode head, int target) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null) {
if (prev.next.val == target) prev.next = prev.next.next; // skip the node
else prev = prev.next;
}
return dummy.next; // the (possibly new) real head
}Without the dummy, deleting the head would need a special branch. With it, the head is just another node with a predecessor. Reach for a dummy head whenever the head itself might change.
Losing the rest of the list
The number-one linked-list bug: reassigning a next pointer before you've saved what it pointed to,
which orphans the entire remainder of the list. Always capture ListNode saved = node.next; before
you overwrite node.next. Draw the pointers on paper - interviewers expect it, and it prevents
exactly this mistake.
An array is a numbered locker room: you walk straight to locker 5. A linked list is a treasure hunt - each clue tells you only where the next clue is, so to reach the fifth you must follow four clues in order. Adding a new stop is trivial (rewrite one clue to point at your insert, and your insert to point at the old next), but there's no jumping ahead - you can only follow the chain from the start.
You're given a reference to a node to delete (not the head, and guaranteed not the tail), but no reference to the list's head. You can't reach the previous node to re-point it. How do you delete it in O(1)?
What is the key performance difference between an array and a linked list?
Key takeaways
- A linked list is a chain of nodes, each holding a value and a reference to the next - no indices, no contiguous memory.
- Access is O(n) (you must walk), but insert/delete at a known node is O(1) (re-point references) - the opposite of an array.
- A dummy/sentinel head node removes edge cases when the head itself may change.
- The classic bug is overwriting a next pointer before saving it, orphaning the rest of the list - save references first.
- Linked lists are an interview staple because they test manual pointer manipulation, not because they're common in production Java.