The node

Here is the whole object a list is built from. Two fields, and nothing else.

private static class Node
{
    // the value this node carries
    Object data;
    // the next node, or null at the end of the chain
    Node next;

    Node(Object data, Node next)
    {
        this.data = data;
        this.next = next;
    }
}

Look at the type of next. It is Node, the same class the field lives in. A node can point at another node of its own kind, and that one fact does all the work. Chain enough nodes together and you have a list. Stop the chain with null and you know exactly where it ends.

Head, and what empty means

The list object itself keeps one reference, usually called head. On the plain shape it points at the first node, and it holds null when there is nothing in the list yet.

head -> [10] -> [20] -> [30] -> null

Draw that on paper. Three things are in the picture: an arrow labeled head, 3 boxes with values in them, and the word null hanging off the right end. Now notice what is missing. There is no arrow pointing backward anywhere, and there is no arrow into the middle. head is the only way in, so to reach the node holding 20 you have to be standing on the node holding 10 and read its next. That is the price the structure charges, and it is why every method starts by walking.

Size, and why it has to stay true

Most of these classes also keep an int size. Nothing forces it to be right. It is a promise you make, and every path through every method you write either keeps it or breaks it. A list whose nodes are perfect and whose size is one behind is a broken list, because the first line toString prints is the size, and because anything that checks an index against the size is now checking against a lie.

To keep it true, walk each path through the method separately once you have written it and ask one question. On this path, did the list get longer, shorter, or stay the same? Then make the size line on that path say so. A path that throws changed nothing, so it touches nothing.

Two shapes, and why the second one exists

You will be handed one of 2 shapes, and the first thing to do with any linked list problem is say out loud which one is in front of you.

No sentinel. head points straight at the first real value. An empty list is head == null.

head -> [10] -> [20] -> null
empty:   head -> null

With a sentinel. One node sits permanently at the front and never holds a real value. head points at that node forever. The first real value is in head.next, and an empty list is head.next == null. The same node goes by 2 names, header node and sentinel node, and some people call it a dummy head. They all mean the one node in front that you never read a value out of.

head -> [ / ] -> [10] -> [20] -> null
empty:   head -> [ / ] -> null

Why would anyone pay for an extra node? Because of what it removes. On the plain shape, inserting at the front and deleting the front are different from inserting and deleting anywhere else, since there is no node in front of the first one to rewire, so head itself has to change. That difference shows up as an if (this.head == null) branch, or an if (index == 0) branch, in method after method. Put one node in front and every real node has a node before it, including the first, so there is no front case left. You are always doing the same move: edit some node's next. You never assign to head at all.

The trade is honest rather than free. You spend one node of memory and you accept one new way to be wrong, which is reading the sentinel's fake value. The rule that prevents it: a walk that inserts or deletes starts at head, because it needs to see the node in front of the first real one. A walk that only reads starts at head.next, because the sentinel holds nothing worth reading. Forget the .next on a read-only walk and every list prints a stray blank at the top.

The 2 loop tests

Nearly every method here starts the same way. Put a cursor on the front and step it forward one node at a time. The only thing that changes from method to method is what the while tests, and that one word decides exactly where the cursor is standing when the walk is done.

Node cur = this.head;
while (cur.next != null)
{
    cur = cur.next;
}
// cur is standing on the last node

That one asks, is there a node after me? It stops on the last real node, and cur never becomes null. Reach for it when you have to change the last node's next, which is what appending does.

Node cur = this.head;
while (cur != null)
{
    // read cur.data here
    cur = cur.next;
}
// cur is null, and every node was visited

That one asks a plainer question, am I standing on a real node at all? It visits every node, the last one included, and stops only when there is nothing left. Reach for it when you are counting, searching, printing, or copying.

Decide where the cursor has to be standing when the loop ends, and the test writes itself. Then check the empty list, because the first test has a trap in it. On an empty plain list head is null, so cur is null, and asking cur.next != null reads a field off nothing and throws a NullPointerException before the body ever runs. Guard the empty list in front of that walk, or give the list a sentinel, which is the same fix bought with a node instead of a branch. The other test needs no guard at all, because it asks about cur itself rather than reaching one field past it.

Pointer order: aim before you break

Two assignments that look interchangeable are not. Say you want a new node at the front of a plain list.

Node fresh = new Node(data, null);
fresh.next = this.head;   // 1. aim the new node at the old front
this.head = fresh;        // 2. then move head

Swap those 2 lines and watch the list eat itself. this.head = fresh overwrites the only reference to the old front, so the moment it is gone the old chain is unreachable. The next line then reads this.head, which is already fresh, so the new node points at itself. The list is one node long, that node points at itself, printing it runs forever, and no exception fires to tell you.

The rule, said once so it covers every case: whenever you are about to overwrite a reference that is the only name for something, aim the new arrow first, using a handle you saved before you touched anything. The 2 argument constructor does this for free, because Java works out the whole right hand side before it changes the left.

this.head = new Node(data, this.head);

Draw it before you code it

Every list problem, even one you have never seen, comes apart the same way.

1. Draw the before picture and the after picture, boxes and arrows.
2. Work backward from the after picture. What actually changed?
3. Name each change. It is always some mix of a node, an arrow, and size.
4. Write one line of code for each named change.
5. Check it against empty, one, and many.

Step 5 is the one that catches the bugs the other 4 miss. A 3 node picture never shows you that a trailing pointer could still be null, and only the one node picture makes it obvious. If your code survives all 3 sizes it is done. If it only survives many, it is not.

What the department names

The official APE site lists the operations this area covers. Its own words:

This will be a non-circular singly-linked list, either with or without a header/sentinel node

Operations will be chosen from the following list

Adding node(s) — all cases (to an empty list, to a non-empty list, at front, at back, in the middle)

Remove node(s) — all cases (based on index, based on Object equality, from front, from back, from middle)

Retrieve an item based on index or some other criterion (such as maximum or minimum)

Order-related manipulations, such as addOrdered and sort, may be exemplified within the linked list

Generate a sublist based on some criterion or criteria.

Add/remove a sequence of items to/from the list.

Process two input lists and generate another list, for example, combining two lists into one.

Every item on that list has a lesson of its own, and every lesson is written for both shapes.

The lessons

Trace these before you go on

Work each one on paper and write the answer down before you open it. If one of them surprises you, go back to the section it came from.

The practice problems

Four worked problems from the department's practice exam, each with the reasoning and the trace. Each one is also the worked example inside its lesson, so start with the lesson if the problem does not click.

The one thing to keep

A node holds a value and a reference to the next node. head is the only way in, and it either points at the first value or at a sentinel that stands in front of it. Decide which shape you are in before you write a line, choose the loop test by where the cursor has to stop, aim every new arrow before you break the old one, and keep size honest on every path. Draw the before and after, name what changed, and check empty, one, and many.