Getting a value back out

Everything here reads and returns, and nothing here changes the list. That is the first thing to notice, because it means no pointer ever gets rewritten, size never moves, and the only ways to be wrong are stopping in the wrong place and crashing on a list that is shorter than you assumed.

There are 2 kinds of question you can ask a list. One is about positions: what sits at position k, or where a value sits. The other asks for the value that wins some comparison, such as the largest or the smallest. They need different loops for a reason worth understanding rather than memorizing.

By index

An array answers this in one step because every slot is the same size and the machine can compute where slot k sits. A linked list cannot. The nodes are separate objects scattered wherever they were allocated, and the only thing tying them together is the arrow in each one, so the only way to reach position k is to start at the front and take k steps. That is what you are paying for the cheap insert at the front.

indexOf asks the position question backward. It is handed a value and returns the position of the first node that holds it, counted from 0 at the first real node (its index), or minus 1 when no node does.

public int indexOf(Object wanted)
{
    int pos = 0;                // the position cur is standing on
    Node cur = this.head;
    while (cur != null)
    {
        if (wanted.equals(cur.data))
        {
            return pos;
        }
        cur = cur.next;
        pos++;
    }
    return -1;                  // no node holds it
}

Read 3 things off that.

The counter and the cursor move together. pos is 0 while cur is on the first node, and both step in the same pass, so pos always names the position cur is standing on. Every walk to a position depends on that pairing, whichever way the question is asked.

The bounds stop one short of the size. A method handed a position has to check it before it walks. Legal positions for reading a node are 0 through size minus 1, because you are naming a node that has to exist. An add accepts size itself, because it is naming a gap and there is one more gap than there are nodes. Two methods, 2 rules, in the same class. indexOf needs no such check, because it is handed a value and only ever returns a position the walk reached.

Standing on the node, or in front of it. Reaching position k from the first node takes k steps and leaves the cursor on that node, which is where a read wants to be. An insert or a remove wants to be standing on the node before, since it is about to rewrite that node's arrow, so it takes 1 step fewer. Decide what has to happen after the loop and the step count follows from it.

On a list with a sentinel, start the cursor on head.next with pos at 0. Starting on head with pos at 0 counts the sentinel as position 0, so every answer comes back 1 too high, and a value in the first real node is reported at position 1. Nothing crashes, which is why this one survives a quick test.

By a criterion, such as the largest

Now nobody tells you where to stop. You have to look at every value and keep the best one you have seen.

public Object max()
{
    if (this.head == null)
    {
        throw new NoSuchElementException("empty list");
    }
    Node best = this.head;
    Node cur = this.head.next;
    while (cur != null)
    {
        if (((Comparable) cur.data).compareTo(best.data) > 0)
        {
            best = cur;
        }
        cur = cur.next;
    }
    return best.data;
}

Three decisions in there, and each one has a reason.

The best starts as the first real node, not as null and not as some very small number. Starting at null would force a null test inside the loop on every single pass, which is slower to write and one more place to be wrong. Starting at a very small number works for int and has no equivalent for Object, and the moment the data could be anything, a stand-in value that happens to lose every comparison does not exist. The first value in the list is always a legal answer to start from, because it is one of the values in the running.

The walk starts on the second node. The first one is already the incumbent, so comparing it against itself is a wasted pass that changes nothing.

The empty list gets a guard. There is no largest value in a list with no values, and there is no correct value to return. Throwing says so. Returning null is the other defensible answer, and either is fine as long as the method says which one it does and the caller can tell the difference. What is not fine is quietly returning the first node's value from a list that has no nodes.

Smallest is the same method with the comparison reversed. Any other criterion is the same method with the comparison replaced, because the shape is not about size at all: hold the best so far, look at the next one, replace the best only when the new one wins.

By a criterion, such as the first one that matches

Searching for the first value that satisfies a rule is the indexOf walk with a different answer. A findFirst(Object wanted) method has the same loop and the same test, returns cur.data where indexOf returns pos, and needs no counter at all.

Returning from inside the loop ends the walk the moment the answer is known, and continuing the walk would only cost time. The interesting decision is the last line. A search that finds nothing has to report that, and there are 3 usual ways: return null, return minus 1 for a position, or throw. Pick the one the specification in front of you asks for.

The walk that compares neighbors, rather than comparing a node against a fixed value, is where the 2 dots crash happens.

// broken: nothing proved cur.next is a real node
while (cur != null)
{
    if (cur.data.equals(cur.next.data)) { ... }
    cur = cur.next;
}

// fixed: the test proves both reads before either happens
while (cur != null && cur.next != null)
{
    if (cur.data.equals(cur.next.data)) { ... }
    cur = cur.next;
}

Java evaluates && left to right and stops as soon as the answer is settled, so when cur is null the second half never runs. That ordering is what makes the fixed version safe, and writing the 2 halves the other way round undoes it.

In the practice APE

None of the 3 practice exams has a linked list problem that hands back 1 value, by index or by a criterion. The set problem in Practice exam 3 works at a position in a list with no sentinel. The findLargest problems in Practice exams 1 and 2 find the largest value of an array, with recursion. The official topic list names retrieval by index and by a criterion such as maximum or minimum, so the absence is about these 3 practice exams and not about what can be asked.

Practice it yourself, and it costs 10 minutes. Take any list class you already have in front of you and add 3 methods to it from a blank line: contains(Object), which returns true when some node holds the value, min(), and lastIndexOf(Object), which returns the position of the last node that holds the value. Then run each one against an empty list, a 1 value list, a list where the answer is the first value, and a list where it is the last. Those 4 lists find almost every bug described here.

Readiness check

The one thing to keep

A read never changes anything, so the only questions are where to stop and what to do when there is nothing to return. By position, a counter that steps with the cursor always names where the cursor stands, the bounds for a read end at size minus 1, and reaching position k takes k steps because a read stands on the node rather than in front of it. By a criterion, hold the first real value as the best so far, start the walk on the second node, and replace the best only on a strict win. An empty list has no largest value and no value at any index, so say so out loud with a guard rather than letting the walk find out.