Analyzing List Algorithms

Analyze each of the methods below according to the instructions in the Javadoc comments. In each case you will be comparing the performance of java.util.ArrayList with java.util.LinkedList. Recall that java.util.LinkedList is implemented using a doubly-linked list that maintains both a head and tail reference.

1. /*
    * What is the big-Theta running time of this method, assuming that list is
    * 
    * 
    * an ArrayList:
    * 
    * 
    * a LinkedList:
    * 
    * 
    */
   public static int sumByIndex(List<Integer> list) {
   
       int sum = 0;
       for (int i = 0; i < list.size(); i++) {
           sum += list.get(i);
       }
       return sum;
   }

2. 
   /*
    * What is the big-Theta running time of this method, assuming that list is
    * 
    * 
    * an ArrayList:
    * 
    * 
    * a LinkedList:
    * 
    * 
    */
   public static int sumWithIterator(List<Integer> list) {
   
       int sum = 0;
       for (int curValue : list) {
           sum += curValue;
       }
       return sum;
   
   }

3. 
   /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copy(List<Integer> fromList,
                           List<Integer> toList) {
   
       for (int item : fromList) {
           toList.add(item);
       }
   
   }

   
   

4. /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copyReverseA(List<Integer> fromList, 
                                   List<Integer> toList) {
   
       for (int item : fromList) {
           toList.add(0, item);
       }
   
   }

5. /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copyReverseB(List<Integer> fromList, 
                                   List<Integer> toList) {
       int value;
       for (int i = fromList.size() - 1; i >= 0; i--) {
           value = fromList.get(i);
           toList.add(value);
       }
   
   }

6. /*
    * What is worst-case the big-Theta running time of this method, assuming
    * that toList is initially empty, and that both lists are of the indicated
    * type. Describe the worst case.
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    * What is average-case the big-Theta running time of this method, assuming
    * that toList is initially empty, and that both lists are of the indicated
    * type.
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copyScramble(List<Integer> fromList, 
                                   List<Integer> toList) {
   
       Random gen = new Random();
       int randomIndex;
       int value;
       for (int i = 0; i < fromList.size(); i++) {
           randomIndex = gen.nextInt(fromList.size());
           value = fromList.remove(randomIndex);
           toList.add(value);
       }
   }