Adding before a value

The lesson behind it is Adding a node, every case.

The method addBefore puts a new node in front of the first node that holds a given value. The list has no empty node in front of its first value (a sentinel), so head is the first real node, or null when the list is empty.

Your readiness not started

Your own marking on this problem.

The contract

public boolean addBefore(Object target, Object data)

What the class already has:

private class Node with the fields data and next, and the constructor Node(Object data, Node next).
private Node head is the first real node, or null.
private int size counts the nodes. The method keeps it right.
addFirst(Object data) puts a value at the front and adds 1 to size.
toString() prints List size is: N, then 1 value per line from front to back.

The node the method looks for is the first node where target.equals(node.data) is true (the match). The checks at the top of a method that throw before anything changes are its guard. Here the guard throws IllegalArgumentException with the message addBefore was passed null.

Input	Result	Size after
`target` or `data` is `null`, on any list, empty included	Throws `IllegalArgumentException`. The list is unchanged.	unchanged
No node equals `target`, the empty list included	Returns `false`. The list is unchanged.	unchanged
The first node is the match	Returns `true`. The new node becomes `head`.	up by 1
A later node is the match	Returns `true`. The new node goes between the match and the node in front of it.	up by 1

Inserting in front of a found node

Guard first. If target or data is null, throw. Nothing has changed yet, so the list is left as it was.
Put match on this.head and set before to null. before is always the node in front of match, and it is null while match is on the first node.
Loop while match is not null and target does not equal match.data. Each turn, before moves to match, then match moves to match.next.
If match is null, no node matched. Return false and leave size alone.
Build the new node with match as its next. It points at the match, and nothing points at it yet.
Link it in. When before is null, the match is the first node, so head changes to the new node. Otherwise before.next changes to the new node.
Add 1 to size and return true.

Step 6 has 2 branches because nothing sits in front of the first node. With a sentinel there would always be a node in front, and 1 branch would do.

public boolean addBefore(Object target, Object data) {
    if (target == null || data == null) {
        throw new IllegalArgumentException("addBefore was passed null");
    }
    Node before = null;
    Node match = this.head;
    while (match != null && !target.equals(match.data)) {
        before = match;
        match = match.next;
    }
    if (match == null) {
        return false;
    }
    Node added = new Node(data, match);
    if (before == null) {
        this.head = added;
    } else {
        before.next = added;
    }
    this.size++;
    return true;
}

The trace below runs addBefore("green", "pink") once on a list that holds red blue green, front to back.

Step	`before`	`match`	What changed	`size`
start	null	red	nothing	3
turn 1	red	blue	`red` is not `green`, so both step	3
turn 2	blue	green	`blue` is not `green`, so both step	3
loop ends	blue	green	`green` equals the target	3
build	blue	green	a node holding `pink` now points at `green`. The list is unchanged.	3
link	blue	green	`blue.next` is the new node. The list reads `red blue pink green`.	3
end	blue	green	`size` goes up, and the method returns `true`	4

The cases

Each list is written front to back. Each case makes 1 call and prints the list after it.

Case	List before	Call	Returns	Printed after
Empty	empty	`addBefore("blue", "pink")`	false	size 0
Empty, null data	empty	`addBefore("blue", null)`	throws	size 0
1 node, match	blue	`addBefore("blue", "pink")`	true	size 2: pink blue
1 node, no match	blue	`addBefore("gray", "pink")`	false	size 1: blue
Match at the front	red blue green	`addBefore("red", "pink")`	true	size 4: pink red blue green
Match in the middle	red blue green	`addBefore("blue", "pink")`	true	size 4: red pink blue green
Match at the last node	red blue green	`addBefore("green", "pink")`	true	size 4: red blue pink green
No match	red blue green	`addBefore("gray", "pink")`	false	size 3: red blue green
Target appears twice	red blue green blue	`addBefore("blue", "pink")`	true	size 5: red pink blue green blue
Null target	red blue green	`addBefore(null, "pink")`	throws	size 3: red blue green

Empty, null data. The guard runs before the walk, so the method throws even though no node could match.
1 node, match and Match at the front. These take the before == null branch. A method that skips that branch throws NullPointerException here.
Match at the last node. The new node goes in front of the last node, so green stays last.
Target appears twice. The walk stops at the first match, so only 1 node is added.
No match and Empty. match reaches null, the method returns false, and size stays where it was.

The printed output of 3 of the cases, line for line. The label above each list comes from the test driver, not from toString.

Match at the front, returns true:
List size is: 4
pink
red
blue
green

Match at the last node, returns true:
List size is: 4
red
blue
pink
green

Null target, throws IllegalArgumentException: addBefore was passed null
List size is: 3
red
blue
green

Drill

Level-up check

1. Predict the output. A list holds red blue red green, front to back. The code calls addBefore("red", "pink") and prints the list. What comes out?

The first node is the match, so pink becomes the new head and the walk never reaches the second red. The first choice adds in front of every match, which is what a walk that keeps going after the first match does. The second choice puts the new node after the match. The fourth choice links the node correctly and forgets this.size++.

2. Spot the bug. This ending has no front case. The walk above it is correct. The list holds red blue and the call is addBefore("red", "pink"). What happens?

if (match == null) {
    return false;
}
before.next = new Node(data, match);
this.size++;
return true;

The match is the first node, so the loop never runs and before is still null. Writing before.next reads through null, and the exception fires before size changes. The same code passes addBefore("blue", "pink") on this list and prints red pink blue, which is why a test that only matches later nodes misses the bug.

3. Pointer order. The list holds red blue, and the match is the first node. Each line below is followed by this.size++. Which line gives a list that prints size 3, then pink red blue?

The right side runs first. It reads the old head into the new node's next, and then head moves to the new node. The first choice adds after the first node, so the list reads red pink blue. The third choice drops the rest of the list, so only pink prints under a size of 3. The fourth choice builds a node that nothing points at, so red blue prints under a size of 3.

4. Guard order. The list is empty and the call is addBefore("red", null). What happens?

The guard is the first thing in the method, so a null argument throws on every list. A version that checks for an empty list before the guard returns false here, which is the first choice. Nothing reads through null before the guard, so NullPointerException never happens, and the guard stops the method before any node is built.

4 questions. 3 right is a pass.

Write it

Write itThe guard

Write the guard for addBefore. It throws IllegalArgumentException with the message addBefore was passed null when target or data is null.

An if and a throw

if (target == null || data == null) {
    throw new IllegalArgumentException("addBefore was passed null");
}

Use ||, because 1 null is enough to throw. The guard goes above the walk. The walk calls target.equals, so a null target would throw NullPointerException there instead.

Write itThe walk to the match

Write the lines that leave match on the first node whose data equals target, with before on the node in front of it, and that return false when no node matches.

2 starting values, a loop, and an early return

Node before = null;
Node match = this.head;
while (match != null && !target.equals(match.data)) {
    before = match;
    match = match.next;
}
if (match == null) {
    return false;
}

The null test comes first in the loop, because && stops at the first false half, so match.data is never read through null. target sits on the left of equals, because the guard already proved it is not null. The early return comes before any line that changes the list.

Your checklist

Tick these when they are true.

My guard is the first thing in the method, so an empty list with a null argument throws and does not return false.
before starts at null and match starts on head, and before is always the node in front of match.
I compare with target.equals(match.data), and the walk stops at the first match.
When match reaches null, I return false and size is untouched.
When before is null, I set this.head to the new node, and I tested a match on the first node.
The new node gets match as its next first, and only then does anything point at the new node.
size goes up by 1 when the method returns true, and stays the same when it returns false or throws.

Could you write this cold?

Blank file, no notes, 4 hours on a clock, and only the Java API documentation open. Say yes only when that is true. You can take it back at any time.

Rules on the practice APE

You change only the lines between //startMethod and //endMethod, and you keep each method header as given.

A private helper method or field of your own between the markers is fine.

No new imports.

The official site's Basic Strategies page says: You may receive points for compiling code but you WON’T receive points for code that does not compile.

The addAtIndex problem in Practice exam 2 uses these moves.