Theory
Four verbs, one working queue
The concepts are in place; now BookBridge's request list must actually WORK. Four operations cover its whole life:
- create/append: a new request joins the end
- insert in front: an urgent staff request jumps the queue
- traverse: print the current line for the librarian
- delete: a member cancels; their node leaves the chain
Each operation is 2 to 6 lines, and every line is a reference update you must be able to TRACE. Exams ask exactly that: show the links before and after.
Practical
The complete IssueList
class Node {
String title;
Node next;
Node(String t) { title = t; }
}
class IssueList {
Node head; // null means empty list
void addLast(String t) { // append at the end
Node n = new Node(t);
if (head == null) { head = n; return; } // empty: n IS the list
Node cur = head;
while (cur.next != null) cur = cur.next; // walk to the tail
cur.next = n; // link the new tail
}
void addFirst(String t) { // insert at the beginning
Node n = new Node(t);
n.next = head; // step 1: n grabs the old chain
head = n; // step 2: head moves to n
}
void delete(String t) { // delete by value
if (head == null) return;
if (head.title.equals(t)) { head = head.next; return; }
Node cur = head; // find the node BEFORE the target
while (cur.next != null && !cur.next.title.equals(t))
cur = cur.next;
if (cur.next != null) cur.next = cur.next.next; // bypass
}
void traverse() {
for (Node cur = head; cur != null; cur = cur.next)
System.out.println(cur.title);
}
}
Theory
Trace: the list takes shape
Run this sequence in your head, drawing boxes and arrows:
addLast("A"): empty, so head → [A|null]
addLast("B"): walk from A (its next is null), link: head → [A] → [B|null]
addFirst("C"): step 1, C.next = head (C grabs A); step 2, head = C:
head → [C] → [A] → [B|null]
The order of addFirst's 2 steps is the heart of this lesson, and the quiz below is about getting it wrong.
Quiz
A student swaps addFirst's 2 lines: head = n; n.next = head; What does the list look like after calling addFirst("C") on the chain A → B?
- C → A → B, same as the correct version
- C pointing to itself; A and B are lost
- A → B → C, appended instead of inserted
- Compile error: head cannot be assigned before n.next
Show the answer
C pointing to itself; A and B are lost
Walk it: head = n makes head point at C while C.next is still null; then n.next = head reads the NEW head, which is C itself, so C.next = C, a self-loop. Nothing points at A anymore: the old chain is unreachable and the garbage collector claims it. This is the classic order-of-updates disaster: always connect the new node INTO the structure (n.next = head) before moving the entry reference. Draw the 2 steps as arrows and the correct order becomes obvious.
Theory
Delete: find the node BEFORE
Deleting [A] from head → [C] → [A] → [B] cannot start at A itself: in a singly list, nobody can see backwards, and the node whose next must change is C.
So delete walks with the test one step ahead: cur.next.title.equals(t). Standing at C with A next, it fires the bypass:
cur.next = cur.next.next; (C now points at B)
head → [C] → [B]. Node A has no references left and is garbage-collected. Deleting the HEAD is the special case with no node before it: head = head.next;
Think first
Full trace, start to finish
Fresh list. addLast("A"); addLast("B"); addFirst("C"); delete("A"); traverse(); Draw the chain after each call, then tap to check.
Show the answer
addLast("A"): head → A. addLast("B"): head → A → B. addFirst("C"): C grabs A, head moves: head → C → A → B. delete("A"): head is C, not the target; standing at C, cur.next is A, match: C.next = A.next = B. Final chain head → C → B, so traverse prints C then B. If your drawing matched at every step, you can answer any exam variant of this; the operations never change, only the sequence.
Watch out
The 3 classic list bugs
Losing the chain: moving head (or any link) before connecting the new node: the quiz disaster.
Forgetting the special cases: empty list in addLast, head-deletion in delete. Every operation asks: what if the list is empty? what if it is the first node?
== on titles: head.title == t compares references (the string-pool lesson!); real input needs .equals(). A delete that never matches is usually this.
Formula
The exam recipe
Linked-list questions are diagram questions wearing code. The method that always scores:
1. Draw the nodes as boxes with arrows, including head and null.
2. Number each reference update in the code (1, 2, 3...).
3. Redraw the arrows after EACH numbered step, not just at the end.
4. State the special cases (empty list, head node) in one line each.
Examiners award the steps, not just the final picture.
Summary
Key takeaways
- addLast: walk to the node with next == null and link there; empty list means head = n.
- addFirst: n.next = head THEN head = n; the order protects the old chain.
- delete: walk to the node BEFORE the target and bypass with cur.next = cur.next.next; head deletion is its own case.
- traverse: from head while cur != null; the bypassed node is garbage-collected.
- Compare titles with .equals(), never ==.
- Every operation handles 2 questions first: empty list? first node?
- Memory hook: connect the new node before you move the head.