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: // 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); } }
Stuart Reges
Last modified: Fri Jan 22 13:05:48 PST 2016