<![CDATA[
CSE143 Sample Program handout #8
Assuming that we are using the ListNode class from handout #8 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);
}
}
]]>