Removing repeats in 1 walk

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

The method removeRepeats walks a list once. Wherever 2 or more neighboring nodes hold equal values, it keeps the first of them, takes the rest out, and returns how many it took out. The list has a node in front of the first value that holds no value of its own (a dummy head).

Your readiness not started

Your own marking on this problem.

The contract

public int removeRepeats()

What the class already has:

private class Node with 2 fields, data and next, and a constructor Node(Object data, Node next). This method builds no node. It only relinks the ones already there.
private Node head is the dummy head. The constructor makes it once and it never changes. Its data is null. The first value sits in head.next. An empty list is a dummy whose next is null.
private int size counts the values. The dummy is not counted. The method keeps it correct.
addFirst(Object data) puts a value at the front and adds 1 to size. Every list below is written front to back, in the order the values sit in the list.
toString() prints List size is: N and then 1 value per line, starting at head.next, with \r\n line endings.

No node holds null. 2 values are equal when equals returns true.

List before	Returns	List after	`size` after
empty	0	empty	0
a	0	a	1
a b c	0	a b c	3
a a b	1	a b	2
a b a	0	a b a	3
a a b b b a	3	a b a	3

The idea

To take a node out of a singly linked list, you change the next field of the node in front of it so that it skips the node (you unlink it). A node cannot see the node behind it, so the walk has to sit on the node in front. Here that node is always keep, the last node the method decided to keep.

Put keep on head.next. Start removed at 0.
Loop while keep is not null.
While the node after keep holds a value equal to the value in keep, unlink it with keep.next = keep.next.next, subtract 1 from size, and add 1 to removed.
keep stays put during step 3. The node that moves up behind it may be a repeat too.
When the node after keep differs, or there is none, move keep 1 node forward.
Return removed.

The first value never goes, because no value sits in front of it to repeat. So there is no front case. On an empty list, keep starts on null and the loop never runs.

The test in step 3 lives in a small private helper. Its null check comes first. && stops at the first part that is false (short-circuit evaluation), so node.next.data is read only when node.next exists.

public int removeRepeats() {
    int removed = 0;
    Node keep = head.next;
    while (keep != null) {
        while (repeatsNext(keep)) {
            keep.next = keep.next.next;
            size--;
            removed++;
        }
        keep = keep.next;
    }
    return removed;
}

private boolean repeatsNext(Node node) {
    return node.next != null && node.data.equals(node.next.data);
}

A trace on a a b b b a. Each row is 1 check of repeatsNext(keep).

Check	`keep` is on	Node after `keep`	What changed	List	`size`	`removed`
1	1st a	a	unlink the 2nd a	a b b b a	5	1
2	1st a	b	`keep` moves to the 1st b	a b b b a	5	1
3	1st b	b	unlink the 2nd b	a b b a	4	2
4	1st b	b	unlink the 3rd b	a b a	3	3
5	1st b	a	`keep` moves to the last a	a b a	3	3
6	last a	none	`keep` moves to `null`; the loop ends; return 3	a b a	3	3

The cases

Case	List before	Returns	Printed after	What it checks
Empty	empty	0	`List size is: 0`	the loop never runs
1 node	a	0	`List size is: 1` `a`	the helper sees `next` is `null` and does not throw
No repeats	a b c	0	`List size is: 3` `a` `b` `c`	nothing changes
Run at the front	a a b	1	`List size is: 2` `a` `b`	the first a stays
Run at the back	a b b	1	`List size is: 2` `a` `b`	the unlink writes `null` into `keep.next`
All the same	a a a a	3	`List size is: 1` `a`	`keep` stays on the 1st a for the whole run
Equal but not neighbors	a b a	0	`List size is: 3` `a` `b` `a`	only neighbors count
Runs of 2 and 3	a a b b b a	3	`List size is: 3` `a` `b` `a`	2 runs in 1 walk

Drill

Work each one on paper before you tap.

Level-up check

1. Predict the output. The list holds x y y x x x front to back. removeRepeats() runs, then the return value and the list are printed. What comes out?

The run y y loses 1 node and the run x x x loses 2, so 3 go. Returning 4 removes every later copy of a value anywhere in the list, but the first x and the 3rd x are not neighbors. Returning 2 is what happens when keep steps forward after an unlink and misses the end of the run. Size 6 means size was never decremented.

2. Spot the bug. In this version the inner while is an if. It runs on a a a b. What happens?

while (keep != null) {
    if (repeatsNext(keep)) {
        keep.next = keep.next.next;
        size--;
        removed++;
    }
    keep = keep.next;
}

The first check unlinks the 2nd a, so the 3rd a moves up behind keep. Then keep steps forward onto that 3rd a without comparing it with the 1st one. The next check compares the 3rd a with b, and nothing else is removed. The outer loop test catches null, so nothing throws. After an unlink, keep stays and checks again.

3. Order of the checks. repeatsNext is called on the last node of the list, where node.next is null. Which return line gives false there without throwing?

Java reads the parts of && from left to right and stops at the first false. With the null check on the left, node.next.data is never read on the last node. The 1st and 3rd lines read node.next.data first and throw NullPointerException. With ||, a false left part makes Java read the right part, so it throws too.

4. An edge case. The list holds a b a b. What does removeRepeats() return, and what is printed?

Every node sits next to a different value, so no check is true and nothing changes. a b and b a come from removing copies that are not neighbors. The last choice counts repeats without unlinking them, and the contract asks for both.

4 questions. 3 right is a pass.

Write itThe inner loop

Write the inner loop of removeRepeats: the part that unlinks every repeat after keep and keeps size and removed correct.

keep stays put inside it

while (repeatsNext(keep)) {
    keep.next = keep.next.next;
    size--;
    removed++;
}

No line inside the loop moves keep. Each turn writes to keep.next, the field of the node in front of the repeat. The loop ends when the node after keep differs or does not exist.

Trace itp p p p, by hand

The list holds p p p p. For each check of repeatsNext(keep), write where keep is, what changed, size, and removed.

4 checks, keep on the 1st p throughout

check keep    change                 size removed
1     1st p   unlink the 2nd p       3    1
2     1st p   unlink the next p      2    2
3     1st p   unlink the last p      1    3
4     1st p   next is null, move on  1    3
keep is null, return 3

keep leaves the 1st p only after keep.next is null. The list prints List size is: 1 and then p.

Your checklist

Tick these when they are true.

keep starts on head.next, and an empty list skips the loop.
My test checks node.next != null before it reads node.next.data.
I compare the 2 values with equals.
My unlink is keep.next = keep.next.next, a write to the node in front of the repeat.
keep moves only when the node after it differs. I traced a a a a and got 1 node and a return of 3.
size goes down by 1 for each unlink, and the number I return matches.
I ran the 8 cases, and every return value and printed line matched.

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 deleteAllOccurrences problem in Practice exam 2 uses these moves.