Adding a node, every case

Adding to a linked list is always the same 3 moves. Make a node. Point it at whatever comes after it. Make something point at it. The cases people list separately, front and back and middle and empty, differ in exactly one thing: what that something is. Learn the one move and the cases stop being separate.

The one move

Take a chain and a value you want to insert between 2 of its nodes.

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

after:    ... -> [10] -> [15] -> [20] -> ...

Work backward from the after picture. What actually changed? A node holding 15 exists that did not exist before, its arrow points at the node holding 20, and the node holding 10 now points at it instead. Three changes, and one of them is the new object itself, so the code is 2 statements and a count.

Node fresh = new Node(data, cur.next);   // aim it at the rest of the list
cur.next = fresh;                        // then hand the rest of the list over
this.size++;

The order is not a style choice. If you write cur.next = fresh first, then fresh.next = cur.next reads a field you already overwrote, so the new node points at itself and everything past it is unreachable. Aim before you break, using a handle you read before you touched anything. Java works out the whole right hand side of an assignment before it changes the left, so the 2 argument constructor gets that order right for you and the pair collapses to one line.

cur.next = new Node(data, cur.next);

Every case is that one line, with a different answer to a single question: which node is cur?

At the front

There is no node in front of the first one, so on a list with no sentinel there is nothing to hang the new node off. head itself is the reference that has to change.

public void addFirst(Object data)
{
    this.head = new Node(data, this.head);
    this.size++;
}

Read it as the same move with head playing the part of cur.next. The new node is aimed at the old front, then head swings over to it. Write it as 2 statements if that is clearer, as long as the aim comes first.

Node fresh = new Node(data, null);
fresh.next = this.head;     // 1
this.head = fresh;          // 2

Reverse those 2 and the list eats itself. Line 2 would overwrite the only reference to the old chain, so by the time line 1 read this.head it would read fresh, and the node would point at itself. The list would be one node long, printing it would run forever, and nothing would throw to tell you.

On a list with a sentinel, the front is not special, because the sentinel is the node in front of the first real one. You never touch head.

public void addFirst(Object data)
{
    this.head.next = new Node(data, this.head.next);
    this.size++;
}

Into an empty list

On both shapes the front case already handles the empty list, with no extra code, and that is worth slowing down for.

With no sentinel, an empty list is head == null. The front version assigns to this.head and reads this.head only as a value to aim at, which is null, exactly what the single node's next should be. Nothing is dereferenced, so nothing crashes.

With a sentinel, an empty list is head.next == null. The sentinel is a real node, so head.next is a safe read, and the new node ends up with null after it. Same code, same answer.

The mistake that breaks this is writing the front case as a read through head rather than an assignment to it, something like this.head.next = fresh on the shape with no sentinel. On a list that already has nodes that line looks like it works, because it inserts at position 1 instead of position 0 and nothing throws. On an empty list it throws.

At the back

Appending means changing the next of the last node, so you need a cursor standing on the last node. That is the walk whose test asks whether there is a node after me.

Node cur = this.head;
while (cur.next != null)
{
    cur = cur.next;
}
cur.next = new Node(data, null);
this.size++;

On a list with a sentinel that is the whole method. Start the cursor on the sentinel, which always exists, and an empty list stops the loop on the first check with the cursor still on the sentinel, which is exactly the node you want to attach to.

On a list with no sentinel that walk has a hole in it. When the list is empty, cur starts as null, and the while line reads cur.next off nothing and throws before the body runs even once. There is no node to stand on, so the empty list gets its own branch, and that branch is the front case you already wrote.

public void addLast(Object data)
{
    if (this.head == null)
    {
        this.head = new Node(data, null);
    }
    else
    {
        Node cur = this.head;
        while (cur.next != null)
        {
            cur = cur.next;
        }
        cur.next = new Node(data, null);
    }
    this.size++;
}

Once you are past that if, the cursor is never a guess again. It starts on a head the guard just proved is not null, and every later value of cur is a cur.next the loop itself tested on the pass before. That is the shape of a safe walk: each read is one dot past something already proven.

In the middle, at an index

Two questions to answer before you write anything. Which indexes are legal, and which node do you walk to?

Which indexes are legal. For an add it is 0 through size inclusive, both ends. A chain of size nodes has size plus 1 gaps in it: before the first, between each neighboring pair, and after the last. You are putting a value into a gap, so there is one more legal index than there are nodes. That is why index == size is legal and means append, and why the test is index > this.size and not >=. Remove is the opposite and its legal range is 0 through size minus 1, because you can only remove a node that is there.

Which node. The one before the gap, which is at index - 1. A cursor that starts on the first node is already at position 0, so it takes index - 1 steps to get there.

A value can name the gap instead of an index. The method addAfter(Object target, Object data) walks to the first node holding target and puts the new node after it.

public void addAfter(Object target, Object data)
{
    Node cur = this.head;
    while (cur != null && !cur.data.equals(target))
    {
        cur = cur.next;
    }
    if (cur == null)
    {
        throw new IllegalArgumentException("target not found");
    }
    cur.next = new Node(data, cur.next);
    this.size++;
}

Check the walk against both ends before you trust it. When target sits in the last node, the loop stops on that node. Its next is null, so the new node goes on the end with null after it. When target is missing, the loop runs off the end and leaves cur as null. The if throws before the splice can read cur.next, so the list is unchanged.

This method has no front branch on either shape. The new node always goes after a node that holds target, so head never changes. An empty list needs no branch either, because the loop tests cur != null before it reads cur.data. On a list with a sentinel, start the cursor on this.head.next, the first real node, and the rest is the same.

In the practice APE

The addAtIndex problem in Practice exam 2 uses the front and middle cases on a list with no sentinel. The addAll problem in Practice exam 1 uses the back case on a list with no sentinel. Each file's header comment is the specification.

Trace the middle case once, with addAfter. The list holds a b c d e and the call is addAfter("c", "new item").

What the list prints afterward:

List size is: 6
a
b
c
new item
d
e

The size on that first line is part of the output. Correct pointers with a stale size still print a wrong first line.

Readiness check

Work each one on paper and write the answer down before you open it.

The one thing to keep

An add is one statement, somewhere.next = new Node(data, somewhere.next), and the only question is which node somewhere is. At the front on a plain list it is head itself, which is why that case looks different and why it also covers the empty list. At the back it is the node the stand-on-it walk stops on. In the middle it is the node at index - 1. The legal indexes run 0 through size because a chain has one more gap than it has nodes, and size goes up by one on every path that inserted and on no path that threw.