Java recursive sort verification function for a linked list

Question

It should return true, if there is no element that follow or the following elements are greater than their predecessors.

public class Element { 
    private int value; 
    private Element next;

    public boolean isSorted(){
        if (this.next == null)
            return true;
        else return (this.value < this.next.value && this.next.isSorted());
    }
}

What do you guys think of it?

Answer 1

With this implementation it is impossible for a list with duplicate elements to be sorted. However, that possibility is easy enough to support:

return (next == null)
    || ((value <= next.value) && next.isSorted());

Now, empty lists are explicitly sorted by the first clause. Lists with an element strictly greater than a previous element are not sorted by the second. And the third says that if the first two values are sorted and the rest of the list is sorted, the list as a whole is sorted.

This works because this uses short circuit Boolean operators. So when next is null, it doesn't bother to check the rest of the statement (true || is always true). And when the current value is greater than the next, it doesn't need to continue (false && is always false). Finally, if it makes it to the last clause, it can simply return the result of it. Because it knows that the first clause was false and the second was true; otherwise, it would never have reached the third.

Alternately, you could change the name from isSorted to isIncreasing which would better describe what you are actually doing. If that is what you actually wanted to do.

Moving from a recursive solution on Element to an iterative solution on the linked list would also make sense.

Answer 2

I would like to add few improvements for better readability.

1. You don't need an else statement; rather you should directly return it.

2. For every if and else statement, even if it is a single line and Java allows it without braces, it's not preferable because of possible code bugs which may arise in future due to missing braces.

3. Better to put (this.value < this.next.value) in brackets for better readability.

So the updated code should look like:

public boolean isSorted() {
    if (this.next == null) {
        return true;
    }
      
    return (this.value < this.next.value) && this.next.isSorted();
} 

Answer 3

There is no need for else. For better code readability single point of return should be used.

return (this.next == null) || ((this.value < this.next.value) && this.next.isSorted());