CSE143 Sample Program handout #4 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); } }
Stuart Reges
Last modified: Fri Oct 13 13:51:36 PDT 2017