Keeping it sorted, and sorting it

There are 2 ways a list ends up in order, and they are different jobs. You can keep it sorted as values arrive, so it is never out of order in the first place. Or you can take a list that is already a mess and put it in order. The first is addOrdered, the second is a sort you write by hand, and both rest on the same small contract about what it means for one value to come before another.

The contract underneath both

A value knows how to compare itself to another value of its own kind when its class implements Comparable, which means it has a compareTo method. That method promises a sign and nothing else: negative if the receiver sorts before the argument, 0 if they tie, positive if it sorts after.

Read that as a promise about order, not about size. Numbers sort by value, strings sort in the order the characters happen to fall, and a class you write sorts however you wrote it, which may be last name and then first name and then a number. All a sort ever asks is this one question, over and over: does this value belong before that one?

So compare with the method and test the sign.

if (a.compareTo(b) < 0)      // a belongs before b
if (a.compareTo(b) == 0)     // they tie
if (a.compareTo(b) > 0)      // a belongs after b

Never < between 2 objects, because that operator compares references or primitives and does not know your order. And never compareTo(b) == -1, because the promise is the sign and a correct implementation is free to return any negative number. String returns a difference between characters, which is usually not minus 1.

addOrdered: finding the spot

Adding at the front is easy and adding at the back is easy, because in both cases you already know which node the new one attaches to. Keeping a list sorted is a different problem: the right spot depends on the value itself, and you do not know where it is until you go looking. addOrdered goes looking, one comparison at a time, and stops the instant it finds the spot.

public void addOrdered(Object item)
{
    Node fresh = new Node(item, null);
    Node prev = null;
    Node cur = this.head;
    while (cur != null
            && ((Comparable) cur.data).compareTo(item) < 0)
    {
        prev = cur;
        cur = cur.next;
    }
    fresh.next = cur;            // aim before you break
    if (prev == null)
    {
        this.head = fresh;       // front of the list, or the list was empty
    }
    else
    {
        prev.next = fresh;
    }
    this.size++;
}

Two cursors move together. cur does the looking and walks forward while the node it is on still holds a value that belongs before the new one. prev trails one node behind the whole time, because once cur stops, prev is the node whose arrow has to change.

Read the loop condition in the order Java reads it. cur != null runs first, and only if that passes does Java run the comparison. That order is the safety. If cur ever reached null and the second half ran anyway, you would call a method on nothing. The loop stops when either half fails, which means either the walk ran off the end of the list, or the node cur is on no longer belongs before the new value. Either way, cur is the first node the new value does not belong after, and prev is exactly where the new node attaches.

Picture inserting 20 into a list holding 10 and 30.

head -> [10] -> [30] -> null
         prev    cur

10 belongs before 20, so both cursors stepped.
30 does not, so the walk stopped there.
The new node goes between them.

The wiring is 2 lines and the order is not a style choice. fresh.next = cur runs first, pointing the new node at the rest of the list while cur still names it. Only then does anything else point at the new node. Reverse it and prev.next is already fresh by the time you read it, so the new node points at itself and everything after is unreachable.

The front case covers the empty list for free. prev starts as null and the only line that changes it lives in the loop body, so prev is still null in exactly 2 situations, both of them meaning the loop never ran. Either the list was empty, so cur was null on the first check, or the new value belongs in front of everything, so the first comparison already failed. Both want the same answer, which is that the new node becomes the head. One branch, 2 situations, and no special case written for either.

A tie goes in front. The test is strictly less than, so a node holding a value equal to the new one does not count as belonging before it, and the walk stops on it. The new value lands immediately in front of the equal one. The list is still sorted either way, so nothing breaks, but know which one your loop does before somebody asks.

On a list with a sentinel, prev never starts at null. It starts on the sentinel, which is always there, so the if (prev == null) branch disappears and inserting at the front is the same move as inserting anywhere else. That is the trade the sentinel buys, seen in one method.

Sorting the list you already have

Now the values are already in the nodes, in no particular order, and you have to put them in order. Insertion sort is the shortest one to write here, because addOrdered already does all of its work.

The plan has 2 parts. First, take the old chain off the list, so the list is empty and the old nodes are still reachable through a local cursor. Then walk the old chain and hand each value to addOrdered, which puts it in sorted position in the new list.

public void sort()
{
    Node cur = this.head;        // the old chain
    this.head = null;
    this.size = 0;
    while (cur != null)
    {
        this.addOrdered(cur.data);
        cur = cur.next;
    }
}

The first line keeps the old chain reachable through cur. The next 2 lines empty the list, so head is null and size is 0. The loop then hands each old value to addOrdered, which walks the new list, finds the spot, attaches a fresh node and counts it. The old nodes are never changed, so cur = cur.next still walks the old chain.

Follow 4 values through it. The list holds 4 9 1 6.

Two details separate a correct version from one that merely looks right.

Reset size to 0. addOrdered adds 1 for every value it places. Leave size at its old value and it ends up doubled, so 4 9 1 6 sorts correctly and reports a size of 8.

A tie goes in front. addOrdered stops on a value equal to the new one, so a value lands in front of an equal value already placed. 2 equal values come out in the reverse of their old order. The list still reads as sorted.

Empty, one, many. Empty sets cur to null on the first line, so the loop test fails immediately and the list is left empty with a size of 0, which is correct because an empty list is already sorted. One node runs the loop once, and addOrdered puts the value back as the only node with a size of 1. Many is the walk above.

On a list with a sentinel, the sentinel stays. Save head.next instead of head, set head.next to null, and let the sentinel version of addOrdered place each value.

In the practice APE

The practice exam asks you to sort a linked list with a sentinel by hand. Its class gives you no addOrdered, so the sort above does not drop in as written. Any sort you can write from a blank line works, with compareTo doing the comparing. Nothing in the practice exam asks for addOrdered itself, so that half of this page is yours to practice on your own, and it is worth the time, because the official topic list names both.

The practice you want for the sort is the cold write. Take any list class you have, delete your sort, and type it again from a blank line. Then run it on 4 lists: empty, one value, values already in order, and values in exactly reverse order. Reverse order sends every value through the front branch of addOrdered, and values already in order make every call walk to the end.

Readiness check

The one thing to keep

addOrdered walks while the node in front still belongs before the new value, checking the cursor before the comparison so the walk never reads through nothing. It stops one node early with prev trailing, because prev owns the arrow that has to change, and the prev == null branch covers both the empty list and the new front with no second branch written for either. A sort you write by hand on a list can reuse addOrdered. Save the old chain, empty the list and its size, then hand each value back in turn.