CSE143 Sample Program handout #8
Assuming we have the ListNode class from handout #7 and that we are defining a
new class with the following general structure:
public class LinkedIntList {
private ListNode front;
}
We could define the following method:
// 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 || front.data >= value)
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);
}
}