A treasure hunt
In a treasure hunt each clue says where the next clue is hidden. You can't jump to clue 5 – you follow the chain from clue 1. A linked list works the same way: each node holds a value and a reference (an arrow) to the next node. The last node points to null – the end.
class Node {
int value;
Node next; // the arrow to the next node (null = the end)
Node(int value) {
this.value = value;
}
}
public class Main {
public static void main(String[] args) {
Node head = new Node(7); // the first node is called the head
head.next = new Node(3);
head.next.next = new Node(9);
// walk the chain from the head until we fall off the end
Node cur = head;
while (cur != null) {
System.out.print(cur.value + " -> ");
cur = cur.next;
}
System.out.println("null");
}
}Output
7 -> 3 -> 9 -> null
Array or linked list?
| Array / ArrayList | Linked list | |
|---|---|---|
| Get item number i | O(1) – jump there | O(n) – follow the arrows |
| Add / remove at the front | O(n) – everyone shifts | O(1) – change one arrow |
| Add after a node you already hold | O(n) | O(1) |
| Memory | one block, side by side | nodes anywhere, plus an arrow each |
Think of it like this: An array is a row of houses with numbers – go straight to number 40. A linked list is a chain of people holding hands – to reach the 40th you pass along the chain.
Remember: Always keep a reference to the head. If you lose it, the whole list is lost.