A run of items, added or removed

One call, many items. Nothing new happens per item, because every one of them is the single add or the single remove you already know. What is new is the bookkeeping around the loop: where the cursor is when the loop starts, whether it moves with the work, and what the count says at the end.

Two ways to get this wrong, and they are the 2 that cost the most. Attaching every item to the same node, so each one overwrites the last and only the final item survives. And walking from the front again for every item, which is correct and slow, and slow is a thing you can lose marks for when the specification calls it out.

Adding a run at the front

Say you are handed a List from the Java library and asked to put everything in it at the front of your list, in the order it comes.

public void addAllAtFront(List aList)
{
    if (aList == null)
    {
        throw new IllegalArgumentException("list was null");
    }
    Node cur = this.head;              // the sentinel
    Node rest = this.head.next;        // the old first node
    for (Object item : aList)
    {
        cur.next = new Node(item, null);
        cur = cur.next;                // the cursor moves with the work
        this.size++;
    }
    cur.next = rest;                   // the old items follow the new ones
}

The guard is the first statement, not the second. An enhanced for loop over a null list throws a NullPointerException, which is not the exception the specification asked for, so a guard written below the loop never gets the chance to run. Put it first and the method fails in the way it promised to fail.

The old first node is saved before the loop. The first item goes right after the sentinel, so the cursor starts there with no walk at all. The first attach overwrites head.next, so rest has to hold the old first node before that line runs.

The cursor moves with the work. That is the line people leave out. Attach, then step onto what you attached, so the next item hangs off the item before it. Leave the step out and every item is attached to the sentinel, so each one replaces the last. The last line then points the sentinel back at rest, and none of the new items survive. Do the 2 lines in the other order and the cursor steps onto the old first node before anything is attached.

The count goes up once per item. Inside the loop is the right place, because then it is right no matter how the loop ends. Adding the source list's size once before the loop is fine too, as long as the loop really does add every one of them.

The order comes from the source. Front of the source goes on first. Calling addFirst once per item puts the run at the front in reverse order, because each new item goes in ahead of the one before it.

The empty source needs no special case. The loop does not run, the last line points the sentinel back at rest, and the list is left as it was. Writing an if for it adds a branch that can only be wrong.

On a list with no sentinel this method needs one more branch, because there is no node in front of the head for the cursor to start on, and the first item has to become the head. That is the same front case as everywhere else, and it is exactly what the sentinel is buying here.

Adding a run in the middle

Same idea, different starting point. Walk once to the node at index - 1, remember what came after it, then attach each item in turn and step the cursor. When the items run out, attach the remembered tail back on.

Node cur = this.head;
for (int i = 0; i < index - 1; i++)
{
    cur = cur.next;
}
Node rest = cur.next;              // save it before you overwrite it
for (Object item : aList)
{
    cur.next = new Node(item, null);
    cur = cur.next;
    this.size++;
}
cur.next = rest;                   // stitch the tail back on

Saving rest first is the same aim before you break rule, stretched over a loop instead of a single statement. Forget it and the moment the first item attaches, nothing remembers where the rest of the list went.

Removing a run

Two kinds of run get removed, and they are different jobs.

A run by position. Remove count items starting at an index. Walk once to the node at index - 1, then step a second cursor forward count nodes and point the first one at where the second one landed. One write, whatever the count is.

Node cur = this.head;
for (int i = 0; i < index - 1; i++)
{
    cur = cur.next;
}
Node stop = cur.next;
int removed = 0;
while (removed < count && stop != null)
{
    stop = stop.next;
    removed++;
}
cur.next = stop;
this.size -= removed;

The stop != null half of that test is the decision that matters. If the list runs out before the count does, you have to choose: remove what is there and report how many, or refuse the whole call because it asked for more than exists. Both are defensible, and the specification in front of you says which. What is not defensible is walking off the end, because the next .next throws. Count what you actually removed and subtract that, not what you were asked for.

A run by value. Remove every item that matches a rule, wherever they sit. That is the walk worked through in Removing a node, with one cursor on the node being examined and one on the last node you kept, and with the rule that the trailing cursor does not move on a delete. Removing 5 matches in a row and removing 5 matches scattered through the list are the same code, and the adjacent ones are the case that exposes a wrong trailing cursor.

In the practice APE

The addLast problem in Practice exam 2 adds a run at the end of a list with a sentinel. Its header comment is the specification.

The front version above, traced on a list that holds 5 values and an argument that holds 3:

before:  [ / ] -> 1 -> 2 -> 3 -> 4 -> 5 -> null       size 5
         aList holds first, second, third

start:   the cursor is on the sentinel, rest holds 1

item 1:  attach first after the sentinel, step onto it   size 6
item 2:  attach second after first, step onto it         size 7
item 3:  attach third after second, step onto it         size 8

stitch:  third.next = rest, the node holding 1

after:   [ / ] -> first -> second -> third
         -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Now the empty list case, which is where the sentinel earns its keep. The list is empty, so head.next is null and rest holds null. The cursor stands on the sentinel, and the sentinel is the node the first item attaches to. The stitch puts null after the last item, which ends the list. Same code, no branch. If the cursor had started at head.next instead, it would be null and the first attach would throw.

And the empty argument, on a list that already holds a value: the loop does not run, the stitch puts the old first node back after the sentinel, nothing changes, and size must not move.

Readiness check

The one thing to keep

A run is the single operation in a loop, plus a cursor that moves with the work so you never search twice. Guard the argument before anything else, walk once to the place the run starts, attach and step for every item, and count what you actually did rather than what you were asked for. The empty source list needs no branch, because a loop that runs zero times already does the right thing.