<![CDATA[
CSE143 Sample Program handout #7
Assuming that we are using the ListNode class from handout #5 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 constructor for the LinkedIntList class:
// pre : n >= 0
// post : constructs a list of n values starting with n and ending in 1
// (unles n is 0, in which case the list is empty)
public LinkedIntList(int n) {
front = null;
for (int i = 1; i < n; i++) {
front = new ListNode(i, front);
}
}
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 || value <= front.data)
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);
}
}
]]>