<![CDATA[
CSE143 Sample Program handout #8
Assuming that we are using the ListNode class from handout #6 and are defining
a LinkedIntList class that has a single field storing a reference to the front
of the list:
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
<constructors>
}
public class LinkedIntList {
private ListNode front;
<methods>
}
We could define the following method for the LinkedIntList class:
// pre : list is in sorted (non-decreasing) order
// post: given value inserted into list so as to preserve sorted order
public void addSorted(int value) {
if (front == null || value <= front.data)
front = new ListNode(value, front);
else {
ListNode current = front;
while (current.next != null && current.next.data < value)
current = current.next;
current.next = new ListNode(value, current.next);
}
}
Below is variant of addSorted that uses both a prev and current pointer.
public void addSorted(int value) {
if (front == null || front.data >= value)
front = new ListNode(value, front);
else {
ListNode prev = front;
ListNode current = front.next;
while (current != null && current.data < value) {
prev = current;
current = current.next;
}
prev.next = new ListNode(value, prev.next);
}
}
Here is a variant you don't need to understand yet, that uses a recursive style:
public static ListNode addSortedR(int value, ListNode head) {
if(head == null || value > head.data) {
return new ListNode(value, head);
} else {
return new ListNode(head.data, addSortedR(value,head.next));
}
}
]]>