Start here: what this lesson is for
Everything you have stored so far has been an array: values sitting side by side in memory. This lesson introduces the first structure that gives that up entirely, and every difference between the two follows from that single decision.
A linked list keeps its items in scattered boxes, each holding a reference to the next. Losing adjacency costs you instant access by index - there is no arithmetic that finds the fifth item - but it buys something an array genuinely cannot do: inserting without moving anything.
There is also an honesty lesson here that most courses skip. The theory says linked lists win at insertion, and on a modern machine an array often beats a list even where the Big-O says otherwise. You will see that measured rather than asserted, and understand why.
- What you need first: chapter 2 (arrays and contiguous memory) and chapter 1 (counting steps).
- What you will be able to do: choose between an array and a list for a real reason, not a remembered table.
- How long: about 22 minutes, plus two problems at the end.
- reference
- - a value that says where an object lives, rather than holding it directly
A chain instead of a row
Every structure so far has been an array: values sitting side by side in memory, which is what makes a[5] instant - the machine multiplies and jumps.
A linked list gives that up entirely. Each value lives in its own little box, a node, and each node holds a reference to the next one. The boxes can be scattered anywhere in memory. What holds the list together isn't position, it's the chain of references.
Losing adjacency costs you random access - there is no arithmetic that finds the fifth node, you must walk. But it buys something arrays cannot offer: inserting in the middle without shifting anything.
Imagine it like this: A treasure hunt. Each clue tells you where the next clue is. You cannot skip to clue five - you must follow the chain - but slipping a new clue into the middle only means rewriting the one before it.
- node
- - one box holding a value and a reference to the next node
- head
- - the reference to the first node - lose it and the list is gone
- null
- - the end of the chain: a next that points to nothing
The insert arrays can't match
Insert at the front of an array of a million elements and every one of them shifts one slot right. A million writes, to add one value.
In a linked list, the same insert is two writes: point the new node at the old head, then point head at the new node. It costs the same whether the list holds ten items or ten million - the rest of the chain never learns anything happened.
The order of those two writes is not negotiable. Reassign head first and you've lost the only reference to the rest of the list, and the garbage collector takes the whole thing. Link forward, then move the head.
class Node {
int value;
Node next; // null means "end of the chain"
Node(int value) { this.value = value; }
}
Node head = null;
void addFirst(int value) {
Node node = new Node(value);
node.next = head; // 1. link the new node to the old front
head = node; // 2. THEN move the head. Never reverse it.
}
int get(int index) { // no arithmetic - you have to walk
Node cur = head;
for (int i = 0; i < index; i++) cur = cur.next;
return cur.value;
}addFirst(3) head -> [3|] -> null addFirst(2) head -> [2|] -> [3|] -> null addFirst(1) head -> [1|] -> [2|] -> [3|] -> null get(2) walks 1 -> 2 -> 3 (3 hops, not one jump)
addFirst did the same two writes each time regardless of length: that is O(1). get had to walk: that is O(n). The trade is right there in five lines.- reference
- - a value that says where an object lives, rather than holding it
The honest comparison
Written as a table it looks like a fair fight. In practice arrays win far more often than the table suggests, and the reason isn't in the Big-O.
It's cache. Array elements sit together, so fetching one pulls its neighbours into fast memory for free - the next few reads are already there. Linked list nodes are scattered, so every hop can be a fresh trip to main memory, and that trip costs roughly 100x a cache hit. A linked list walk can lose to an array scan while doing the same number of 'steps'.
So reach for a linked list when you genuinely insert and remove at the ends constantly and rarely index - queues and deques, which is exactly chapter 7. Otherwise ArrayList is usually the faster answer even where theory says otherwise.
Summing 1,000,000 values: array vs linked list. Both are O(n). Same speed?
// 1,000,000 elements, summing every value
// identical O(n) walks - wildly different real cost
int sumArray(int[] a) { ... } // adjacent in memory
int sumList(Node head) { ... } // scattered across the heapsumArray 1,000,000 elements ~1.1 ms sumList 1,000,000 elements ~19.4 ms <- same O(n), 18x slower insert at front, 100,000 times array ~4,900 ms (shifting every time) list ~3 ms <- the case the list actually wins
- Insert/remove at a known position: O(1) for a list, O(n) for an array
- Access by index: O(1) for an array, O(n) for a list
- Lists pay per-node memory overhead and lose cache locality
- Prefer ArrayList by default; use a list when you work at the ends
- cache locality
- - nearby data being fetched together, making adjacent reads nearly free
The dummy head, and why experienced code uses it
Once you write real list code, one annoyance appears immediately: the first node is always a special case. Deleting the head means updating the head reference; deleting anything else means updating the previous node's next. Two branches, in every single method.
The standard fix is a dummy head - a throwaway node that sits before the real first one and holds no value. Now every real node has a previous node, the special case disappears, and you return dummy.next at the end.
It costs one object and removes an entire class of bug. When you read production list code and wonder why it starts by allocating a node nobody wants, this is why.
// WITHOUT a dummy: the head is a special case
Node removeAll(Node head, int value) {
while (head != null && head.value == value) head = head.next; // branch 1
Node cur = head;
while (cur != null && cur.next != null) { // branch 2
if (cur.next.value == value) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
// WITH a dummy: one loop, no special case
Node removeAllClean(Node head, int value) {
Node dummy = new Node(0);
dummy.next = head;
Node cur = dummy;
while (cur.next != null) {
if (cur.next.value == value) cur.next = cur.next.next; // skip it
else cur = cur.next;
}
return dummy.next; // the real head, whatever it turned out to be
}remove 1 from [1] -> [1] -> [2] -> [1] -> [3] without dummy two loops, head reassigned twice with dummy one loop, head handled like any other node both return [2] -> [3]
- dummy head
- - a placeholder node before the real first one, so every node has a previous
- sentinel
- - the general name for a placeholder that removes an edge case
Recap: choosing between them for a real reason
The honest summary is shorter than the table people memorise.
Use an array (or ArrayList) by default. You get O(1) access by index, excellent cache behaviour, and less memory per item - no reference to store alongside every value. Most code reads far more than it inserts in the middle.
Use a linked list when you genuinely work at the ends and rarely index: queues, deques, and anything that constantly adds or removes at the front. That is a real but narrow case, and chapter 7 is built on it.
Do not choose based on the Big-O table alone. An array beat a list by 18x on the same O(n) traversal earlier in this lesson, purely because of memory layout - and that constant is invisible in the notation.
Then there is the technique that outlives the structure: two pointers at different speeds. Cycle detection, finding the middle, and nth-from-the-end are all the same idea, and it works on anything you can only walk forward through.
- Array: O(1) index, better cache, less memory - the default
- List: O(1) insert or remove at a known position; O(n) to find it
- Save the next reference before overwriting it - always
- A dummy head removes the first-node special case
- Fast and slow pointers: cycle, middle, nth-from-end
Your turn
Reading is not learning. Open each one in NeonFlow and watch your own code run, step by step.
Reverse it without losing it
Reverse a linked list in place. The trap is that overwriting a node's next destroys your only route to the rest of the chain - so the order of the four lines is the entire problem. Watch the pointers move in NeonFlow.
public class ReverseList {
static class Node {
int value; Node next;
Node(int v) { value = v; }
}
static Node reverse(Node head) {
Node prev = null, cur = head;
while (cur != null) {
// TODO, in this order:
// 1. SAVE cur.next before you destroy it
// 2. point cur.next backwards at prev
// 3. prev moves up to cur
// 4. cur moves on to the saved next
}
return prev; // cur is null; prev is the new head
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
for (Node n = reverse(head); n != null; n = n.next) {
System.out.print(n.value + " "); // expect 3 2 1
}
}
}Find the middle in one pass
Return the middle node without counting the length first. Two walkers, one moving twice as fast - when the fast one reaches the end, where is the slow one? This is the same trick that detects cycles.
public class FindMiddle {
static class Node {
int value; Node next;
Node(int v) { value = v; }
}
static Node middle(Node head) {
Node slow = head, fast = head;
// TODO: advance fast by TWO and slow by ONE each round,
// while fast != null && fast.next != null
return slow;
}
public static void main(String[] args) {
Node head = new Node(1);
Node n = head;
for (int i = 2; i <= 5; i++) { n.next = new Node(i); n = n.next; }
System.out.println(middle(head).value); // 1 2 3 4 5 -> expect 3
}
}