Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 89

System.out.printf("\n");
} //end printList
} //end class LinkedList
We could add a method to check whether a linked list is empty.
public boolean empty() {
return head == null;
}
If LL is a LinkedList , we can use empty as follows:
while (!LL.empty()) { ...
Now suppose we want to add a method that will build a linked list in “sorted order.” Again, since LinkedList does
not know what NodeData might contain, how do we define “sorted order” in LinkedList ? Once more, the solution is to
let NodeData tell us when one NodeData item is less than, equal to, or greater than another NodeData item.
We can do this by writing an instance method (we'll call it compareTo ) in NodeData . Here it is:
public int compareTo(NodeData nd) {
if (this.num == nd.num) return 0;
if (this.num < nd.num) return -1;
return 1;
}
Here, we use the Java keyword this for the first time. If a and b are two NodeData objects, remember that we can
call the method with a.compareTo(b) . In the method, this refers to the object used to call it. Thus, this.num refers to
a.num . We note that the method will work just the same without this because num , by itself, does refer to a.num .
Since the NodeData class we are using has one integer field, num , compareTo reduces to comparing two integers.
The expression a.compareTo(b) returns 0 if a.num is equal to b.num , -1 if a.num is less than b.num , and 1 if a.num is
greater than b.num .
Using compareTo , we can write addInPlace as follows:
public void addInPlace(NodeData nd) {
Node np, curr, prev;
np = new Node(nd);
prev = null;
curr = head;
while (curr != null && nd.compareTo(curr.data) > 0) { //new value is bigger
prev = curr;
curr = curr.next;
}
np.next = curr;
if (prev == null) head = np;
else prev.next = np;
} //end addInPlace