BrewlearnLinked lists in Java
Nodes and pointers, reversal, cycle detection.
Nodes and pointers
A linked list is a chain of nodes. Each node holds a value and a reference to the next node; the last one points to null. There's no index arithmetic: to reach the 7th clue, you follow the first six.
class Node {
int val;
Node next;
Node(int v, Node n) { val = v; next = n; }
}
// 1 -> 2 -> 3 -> nullCheap splices, expensive lookups
Inserting or removing at a node you already hold is O(1): just rewire a pointer. But getting the element at index i is O(n): java.util.LinkedList.get(i) walks node by node from the nearer end. A loop calling get(i) for every i becomes O(n²).
// insert after node n: O(1)
n.next = new Node(42, n.next);
// get(i): walk i steps: O(n)Reverse in one pass
Walk the list with three pointers. At each node: **save next first**, point the node back at prev, then step forward. When cur runs off the end, prev is the new head.
Node prev = null, cur = head;
while (cur != null) {
Node next = cur.next; // save it
cur.next = prev; // flip
prev = cur;
cur = next;
}
// prev is the new headWhere did the old head go?
After reversing, what does this print?
// list: 1 -> 2 -> 3 -> 4
Node prev = null, cur = head;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
System.out.println(prev.val + " " + head.val
+ " " + (head.next == null));4 1 true1 4 false4 1 false
Show the answer
prev is the new head, node 4. The head variable still points at node 1, which is now the tail, so its next is null. Reversal doesn't move nodes, it only flips arrows.
Losing the rest of the list
Flip the pointer before saving cur.next, and the only link to the rest of the list is gone. The loop then stops after one node. Always save next first.
while (cur != null) {
cur.next = prev; // rest of list lost!
prev = cur;
cur = cur.next; // null: loop ends
}Floyd: tortoise and hare
To detect a cycle, move slow 1 step and fast 2 steps. No cycle: fast reaches null. Cycle: once both are inside the loop, fast gains exactly one node per step, so the gap shrinks to zero and they must meet; it can't skip past.
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;Where do they meet?
The list is 1 -> 2 -> 3 -> 4 -> 5, and 5 points back to 3. What does this print?
// 1 -> 2 -> 3 -> 4 -> 5 -> (back to 3)
Node slow = head, fast = head;
boolean cycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { cycle = true; break; }
}
System.out.println(cycle + " " + slow.val);true 4true 3false 5
Show the answer
Start: both at 1. Round 1: slow 2, fast 3. Round 2: slow 3, fast 5. Round 3: slow 4; fast goes 5 to 3 to 4. They meet at node 4.
ArrayList usually wins
Mostly appending and reading by index? Use ArrayList: O(1) index access, amortized O(1) appends, and a contiguous array that CPU caches love. LinkedList spends an extra node object per element. Linked lists still matter in interviews and inside structures like LRU caches.
Key takeaways
- Access by index is O(n); insert/remove at a known node is O(1)
- Reverse: walk once, flipping each next pointer
- Floyd: slow moves 1, fast moves 2; they meet only if there's a cycle
- In practice ArrayList beats LinkedList for most workloads
💡 A treasure hunt: each clue tells you where the next one is, so you can't skip to clue 7.
Joshua Bloch, who wrote java.util.LinkedList, once tweeted about it: "I wrote it, and I never use it."
Practice questions
What does this print?
// head: 1 -> 2 -> 3
Node prev = null, cur = head;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
for (Node n = prev; n != null; n = n.next)
System.out.print(n.val + " ");- 1 2 3
- 3
- 3 2 1
- 1
Check your answer
3 2 1. Each step points the current node back at the previous one, then moves forward. When cur runs off the end, prev is the new head: 3 -> 2 -> 1.
In Floyd's cycle detection, why must the slow and fast pointers meet if there is a cycle?
- The fast pointer eventually becomes null
- Inside the cycle, fast gains one node per step, so the gap shrinks to zero
- Both pointers start at the same node
- The list must be sorted
Check your answer
Inside the cycle, fast gains one node per step, so the gap shrinks to zero. Once both are in the loop, the distance between them changes by exactly one each step, so it can't skip past zero. Without a cycle, fast simply reaches null.