Linked Lists - Building Java Programs: A Back to Basics Approach - page 953

77 } else {
78 ListNode current = nodeAt(index - 1);
79 current.next = new ListNode(value, current.next);
80 }
81 }
82
83 // pre : 0 <= index < size()
84 // post: removes value at the given index
85 public void remove( int index) {
86 if (index == 0) {
87 front = front.next;
88 } else {
89 ListNode current = nodeAt(index - 1);
90 current.next = current.next.next;
91 }
92 }
93
94 // pre : 0 <= i < size()
95 // post: returns a reference to the node at the given index
96 private ListNode nodeAt( int index) {
97 ListNode current = front;
98 for ( int i = 0; i < index; i++) {
99 current = current.next;
100 }
101 return current;
102 }
103 }
16.3 A Complex List Operation
Suppose that you want to write a new method for your LinkedIntList class called
addSorted that would add values to the list in a way which preserves sorted order. In
other words, the method would be specified as follows:
// pre : list is in sorted (nondecreasing) order
// post: given value is added to the list so as to preserve sorted
// (nondecreasing) order, duplicates allowed
public void addSorted(int value) {
...
}
Our exploration of this task will point out important cases to consider and signifi-
cant pitfalls that you must be careful to avoid when you program with linked lists.