Grundlagen verketteter Listen
Knoten und Referenzen, warum Einfügen O(1), aber Zugriff O(n) ist, und der Dummy-Head-Trick, der Sonderfälle beseitigt.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.