Reaching the end of a dummy-head list

The lessons behind it are A run of items, added or removed and Adding a node, every case.

The method moveFirstToEnd takes the node at the front of a list and attaches that same node at the end. 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 void moveFirstToEnd()

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 relinks 1 node that is already in the list.
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.
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.

List before	List after	`size` after
empty	empty	0
red	red	1
red green	green red	2
red green blue	green blue red	3

The node that held red at the front is the same node object that sits at the end afterward. Nothing is copied, and size never changes.

The idea

Put first on head.next. If first is null, the list is empty, so return.
Point head.next at first.next. Now no node in the list points at first (it is unlinked).
Set first.next to null. first is about to be the last node, and the last node points at null.
Put last on head, the dummy. Move last forward while last.next is not null.
Point last.next at first.
Leave size alone. The list holds the same nodes as before.

Step 4 starts on the dummy so that a 1-node list needs no if. After step 2, a list that had 1 node is empty, because head.next is now null. The walk stops at once with last on the dummy, and step 5 sets head.next back to first. A walk that started on head.next would start on null in that case and throw at last.next.

public void moveFirstToEnd() {
    Node first = head.next;
    if (first == null) {
        return;
    }
    head.next = first.next;
    first.next = null;
    Node last = head;
    while (last.next != null) {
        last = last.next;
    }
    last.next = first;
}

A trace of the method on red green blue, with the list read from head.next:

Line	`last` is on	What changed	List	`size`
`Node first = head.next;`	not set	`first` is on red	red green blue	3
`head.next = first.next;`	not set	the dummy points at green; red still points at green	green blue	3
`first.next = null;`	not set	red points at `null`	green blue	3
`Node last = head;`	dummy	the walk starts	green blue	3
loop, turn 1	green	`last` moved	green blue	3
loop, turn 2	blue	`last` moved; `blue.next` is `null`, so the loop ends	green blue	3
`last.next = first;`	blue	blue points at red	green blue red	3

The cases

Case	List before	Printed after	What it checks
Empty	empty	`List size is: 0`	the guard returns before `first.next` is read
1 node	red	`List size is: 1` `red`	the walk from the dummy puts red back
2 nodes	red green	`List size is: 2` `green` `red`	the loop runs 1 turn
3 nodes	red green blue	`List size is: 3` `green` `blue` `red`	the usual case
Equal values at the front	red red green	`List size is: 3` `red` `green` `red`	the method moves a node, so equal values do not matter
2 calls on 3 nodes	red green blue	`List size is: 3` `blue` `red` `green`	the end of the list is still marked by `null` after the first call
3 calls on 3 nodes	red green blue	`List size is: 3` `red` `green` `blue`	the list comes back to where it started

Drill

Work each one on paper before you tap.

Level-up check

1. Predict the output. The list holds ant bee cat dog front to back. moveFirstToEnd() runs once and the list is printed. What comes out?

The front node, ant, leaves the front and is attached after dog. dog ant bee cat is the result of moving the last node to the front, which is the reverse job. Size 3 treats the move as a removal, and size 5 treats it as an add. The same 4 nodes are in the list before and after, so size stays 4.

2. Spot the bug. This version starts the walk on head.next instead of the dummy. It runs on the 1-node list ant. What happens?

Node first = head.next;
if (first == null) {
    return;
}
head.next = first.next;
first.next = null;
Node last = head.next;
while (last.next != null) {
    last = last.next;
}
last.next = first;

first is on ant, so the if does not return. Then head.next = first.next sets head.next to null, so last starts on null, and reading last.next throws. On ant bee cat the same code prints bee cat ant, which is why a test on a long list misses the bug. Starting on the dummy fixes it with no extra if.

3. Pointer order. The 2 unlink lines are written in the other order: first.next = null; first, then head.next = first.next;. Everything else is the same. The list holds ant bee cat. What is printed?

Setting first.next to null first throws away the only pointer to bee. Then head.next = first.next copies that null into the dummy, so the list is empty. The walk stops on the dummy and attaches ant. size was never touched, so it still reads 3. Read a pointer before you overwrite it.

4. An edge case. Someone deletes the if (first == null) block and calls the method on an empty list. What happens?

first is null on an empty list, and reading first.next throws. The walk from the dummy covers the 1-node list. It cannot cover the empty list, because the empty list has no node to move. The guard is the 1 if the method needs. The dummy never moves, since first starts on head.next.

4 questions. 3 right is a pass.

Write itThe walk to the last node

Write the lines that leave last on the last node of a dummy-head list. They must also work when head.next is null.

Start on the dummy

Node last = head;
while (last.next != null) {
    last = last.next;
}

When head.next is null, the loop test is false at once and last stays on the dummy. Attaching after the dummy is the same as attaching at the front of an empty list, so 1 line covers both.

Write itLeaving out first.next = null

Someone leaves out the line first.next = null;. The list holds ant bee cat. Write which node points at which when the method ends, and say what toString does.

The nodes go around in a circle

dummy -> bee -> cat -> ant -> bee -> cat -> ant -> ...

ant still points at bee, and the walk attached ant after cat. The nodes now form a loop (a cycle). The loop in toString stops only at null, and there is no null left, so it never returns a string.

Your checklist

Tick these when they are true.

My only if is for the empty list, and it returns before any pointer changes.
I point head.next at first.next before I change first.next.
I set first.next to null, so the node I move ends the list.
last starts on head, the dummy, and stops when last.next is null.
I traced the 1-node list red by hand, and it came back as red with no if for it.
size reads the same before and after.
I ran the 7 cases, and every 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 addLast problem in Practice exam 2 and the addAll problem in Practice exam 1 use these moves.