Foundation 07
Linked List
A chain of nodes. Each node stores a value and a reference to the next node.
Mental model
What the structure guarantees
Nodes need not be adjacent in memory. There is no arithmetic shortcut to node i, so traversal starts at the head and follows links. Once you already have the right node, changing links does not shift the rest of the list.
Implementation
How that model appears in code
The final node points to null. Correct linked-list code is largely about preserving the next reference before changing it and checking null before following another link.
Linked List basics
class Node {
int value;
Node next;
Node(int value) { this.value = value; }
}class Node:
def __init__(self, value, next=None):
self.value = value
self.next = nextstruct Node {
int value;
Node* next;
Node(int v) : value(v), next(nullptr) {}
};Operation costs
What gets more expensive as the input grows
O(1)The node stores both directly.O(i)Every preceding link must be followed.O(1)Only a small fixed number of links change.O(n)The list may need a full traversal.Tradeoffs
Choose it for the operations it makes cheap
Good fit
- Constant-time insertion after a known node
- Chains with unknown or changing length
- Pointer-spacing techniques
Poor fit
- Indexed access
- Cache-friendly scans
- Walking backwards in a singly linked list
Used by
Common mistakes
Errors that survive a first glance
Check before following next
A condition such as fast != null && fast.next != null is ordered so the second access is safe.
Save the next node before rewiring
Otherwise the remaining chain can become unreachable.
A cycle never reaches null
Ordinary traversal loops forever on cyclic input unless it records visited nodes or uses two speeds.