<![CDATA[
CSE143X Sample Program handout #12
Assuming that we are using the ListNode class from lecture 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:
// post : constructs a list of integers in descending order starting
// with n and ending with 0 (empty list if n is less than zero)
public LinkedIntList(int n) {
front = null;
for (int i = 0; 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);
}
}
]]>