Removing a node, every case

Removing a node is one write. The node in front of it points past it. You never erase anything, and you never touch the node you are removing except to read its value on the way out. Once nothing in the list points at it, it is gone from the list, and Java reclaims the memory whenever it gets around to it.

So the entire problem is getting a handle on the node in front. A singly linked list has arrows pointing one direction only. There is no previous field to read, so once a cursor has moved past a node there is no way to ask it where it came from. Every case is a different answer to the same question: how do I end up holding the node before the one I want gone?

The one move

before:   ... -> [10] -> [20] -> [30] -> ...
                  ^ prev   ^ cur

after:    ... -> [10] -> [30] -> ...

prev.next = cur.next;
this.size--;

That is the whole removal. Draw the after picture and only 2 things are different: one arrow was rerouted, and the count went down. The node holding 20 still exists in memory for the moment and its own next still points at 30, which does not matter at all, because nothing in the list points at it any more.

From the front

The first real node has nothing in front of it on a list with no sentinel, so head is the reference that changes.

public Object removeFirst()
{
    if (this.head == null)
    {
        throw new NoSuchElementException("empty list");
    }
    Object out = this.head.data;
    this.head = this.head.next;
    this.size--;
    return out;
}

The guard is not decoration. An empty list has no first value, and there is nothing correct to invent, so the method refuses rather than guessing. It also protects the 2 reads under it, because this.head.data on a null head throws.

Read the value before you move head. Once head has moved you have no handle on the node you removed, and the value went with it.

On a list with a sentinel, the sentinel is the node in front, so the front is not special. The empty check changes shape but does not go away, because you still cannot remove a first node that is not there.

if (this.head.next == null)
{
    throw new NoSuchElementException("empty list");
}
Object out = this.head.next.data;
this.head.next = this.head.next.next;
this.size--;

By index

The legal indexes for a remove are 0 through size minus 1, because you can only remove a node that exists. This is the opposite of an add, where size itself is legal because a chain has one more gap than it has nodes. Two methods in the same class with 2 different bounds is normal, and using one rule for both is a common way to lose a whole case.

Index 0 is the front, index size minus 1 is the back, and every index between them is the middle. Except at the front, the node to rewire is the one in front of the target, and a singly linked list has no arrow pointing back to it. The fix is to walk 2 cursors together, with prev always one node behind cur. Picture stepping stones: your back foot never lifts until your front foot has landed.

public Object removeAtIndex(int index)
{
    if (index < 0 || index >= this.size)
    {
        throw new IndexOutOfBoundsException("index " + index);
    }
    Node prev = null;               // no node in front of index 0
    Node cur = this.head;
    int pos = 0;                    // the index cur is standing on
    while (pos < index)
    {
        prev = cur;
        cur = cur.next;
        pos++;
    }
    if (prev == null)
    {
        this.head = cur.next;       // index 0: head is the arrow that moves
    }
    else
    {
        prev.next = cur.next;
    }
    this.size--;
    return cur.data;
}

The line to watch is prev = cur, written just before the cursor steps. pos goes up by 1 on every step, so it always names the index cur is standing on. When the loop ends, cur is on the node at index and prev is on the node in front of it, which is exactly the node whose next needs rewriting. Both reads through cur are safe because the bounds check already proved there is a node at that index.

Now run it with index 0. The loop test is false on the very first check, so the body never runs and prev = cur never fires. prev is still null, and prev.next = cur.next would throw. There is no node in front of the first one, so there is no arrow to reroute, and head moves instead. On a list holding 1 node, index 0 is also the last index, cur.next is null, and the list becomes empty. A 3 node drawing never shows you this. Only the 1 node drawing does, which is why the checklist is empty, one, many rather than just many.

A single cursor also works. Start it on the first node and take index - 1 steps, the same walk an add at an index uses, and it stops on the node in front. That version needs its own if (index == 0) branch, because index 0 has no node in front to stop on. On a list with a sentinel, start prev on head and cur on head.next. prev is then never null, and the front branch disappears.

By object equality

Now the node you want is not at a position you were told. You have to find it, and finding means comparing.

The data in these classes is declared Object, so the comparison is equals, not ==. == asks whether 2 references point at the same object in memory. Every string literal in a small test file happens to be the same object, because Java interns literals, so == appears to work and then stops working the moment a value is built at run time instead of typed into the source. equals asks the question you actually meant, which is whether the 2 values are the same value.

Put the argument on the left of the call.

if (target.equals(cur.data))

The method below promises its caller never passes null, so the left side is safe. A value inside a node can be null, and cur.data.equals(target) throws a NullPointerException the moment a node holds null. When neither side is safe, Objects.equals(a, b) in the standard library handles both nulls.

Removing every match is the same one write in a loop, plus one rule that is easy to get wrong.

public void removeAll(Object target)
{
    Node prev = null;               // no node in front of the first one
    Node cur = this.head;
    while (cur != null)
    {
        if (target.equals(cur.data))
        {
            if (prev == null)
            {
                this.head = cur.next;   // a match at the front moves head
            }
            else
            {
                prev.next = cur.next;   // prev does NOT move
            }
            this.size--;
        }
        else
        {
            prev = cur;             // only a keep moves prev
        }
        cur = cur.next;
    }
}

The rule is the comment. When you delete, prev stays where it is. It is already sitting on the last node you decided to keep, and the node you just unlinked is not in the list any more, so moving prev onto it would leave your only handle pointing at something nothing else points at. Every write you made after that would land outside the list and do nothing. Move prev only when you keep.

That is also what makes 2 matches in a row work. After the first delete, prev is still on the node in front, cur steps onto the second match, and the same delete runs again from the same prev. A version that moves prev every pass drops the first of each adjacent pair and keeps the second, which looks almost right and is the reason adjacent duplicates are worth testing by hand.

This list has no sentinel, so the front case is back. The first real node has no node in front of it, so prev starts at null. A match while prev is still null moves head instead. That branch also handles a leading run of matches, because prev stays null until the first keep. With a sentinel, the first real node has a node in front, and the branch is not needed. This is the single clearest example of what the extra node buys.

In the practice APE

The deleteAllOccurrences problem in Practice exam 2 removes by object equality on a list with a sentinel. The removeLast problem in Practice exam 3 removes from the back of a list with no sentinel. The Practice exam 2 problem's header comment is its specification, and the Practice exam 3 problem is specified on that exam's instruction sheet.

One pass of the removeAll above, drawn out, on a list holding A B A with A as the argument. This list has no sentinel, so head points at the first real node.

  head -> A -> B -> A -> null
          cur
  prev is null.

delete at the front: this.head = cur.next
  head -> B -> A -> null
  prev is still null. cur moves to B. size 3 to 2.

keep: prev = cur
  head -> B -> A -> null
          prev cur

delete: prev.next = cur.next
  head -> B -> null
          prev
  cur moves to null, the loop ends. size 2 to 1.

On an empty list the same loop runs 0 times and changes nothing, with no special case. Compare values with equals. A String test such as contains also matches a value that only holds the target inside it.

Readiness check

The one thing to keep

A removal is prev.next = cur.next and a decrement, so the work is all in getting prev. At the front of a plain list prev does not exist, so head moves instead. By index you walk 2 cursors as a pair, the legal range stops one short of the size, and a prev still null after the walk means the target was the front. By value you compare with equals, with the argument you proved on the left, and you leave prev alone every time you delete.