HW4 SAMPLE ANSWERS

1. Each insert costs 3 units of work, one to insert, two saved for later. Once
there are n inserts, there is 2n units of work banked for the copy to the
new array, and there are 2n copies needed, so the cost for an insert is
O(1) over n inserts.
OR
Another way to look at it: for n inserts, n-1 of them will be constant,
and then 1 insert will cost 2n+1 to do the insert and then copy. The
average over all the n inserts is 3n/n = 3 = O(1).

2. 
(I) Worst case and best case are the same: O(n)
You either find element near beginning of array O(1) and remove shifts
more elements O(n) or you find element near end of array O(n) and remove
shifts few elements O(1).

(II) Worst case: O(n) - element is at beginning of array so search is
linear and shifting is linear
Best case: O(1) - element is at end of array so search is constant and
shifting is constant

(III) Worst case: O(n) - either: use binary search and element is at
beginning of array (search O(log n) + remove O(n) = O(n)). Or: use binary
search and element is in middle of array (search O(1) + remove O(n) =
O(n)).
Best case: O(log n) - element is at end of array (search O(log n) + remove
O(1) = O(log n)).

3.

public static void reverse(ArrayList<E> list) {
    for (int i = 1; i < list.size(); i++) {
         list.add(0,list.remove(i)); // add at index 0
    }
}
OR
public static void reverse(ArrayList<E> list) { 
    for (int i = list.size()-2; i >= 0; i--) { 
         list.add(list.remove(i));   // add to end
    } 
}

4. 

(a) 3
    Prints out the data in the last node of the list.
    To avoid a runtime error, list must not be empty.

(b) This code destroys the list after computing the sum.
    New version:
    int s = 0;
    Node<E> nodeRef = head;
    while (nodeRef != null) {
       s += nodeRef.data;
       nodeRef = nodeRef.next;
    }
    System.out.println(s);

5. 
   complexity:
   worst case O(n) - don't find element, have to search whole list
   best case O(1) - find element in first position

public boolean addToHead(E element) {
   numElements++;
   if (head == null) {
       head = new Node<E>(element);
       return true;
   } else {
       Node<E> nodePtr = head;
       while (nodePtr != null) {
            if (nodePtr.data.equals(element)) {
                  return false;
            }
       }
       Node<E> newNode = new Node<E>(element);
       newNode.next = head;
       head = newNode;
       //OR head = new Node<E>(element, head);
       return true;
   }
}

6. (a) Returns the middle data value of list 

   (b) Throws an exception since q moves off list. 
       Avoid runtime error by advancing q one
       'next' at a time, checking for null so we don't get an exception:
       q = q.next;
       if (q != null) q = q.next;

   (c) O(n) - iterates n/2 times which is O(n)