Tracing Linked List Code

As a reminder, here is the Link Class from the reading:

    class Link<E> {         // Singly linked list node class
        private E e;          // Value for this node
        private Link<E> n;    // Point to next node in list

        // Constructors
        Link(E it, Link<E> inn) { e = it; n = inn; }
        Link(Link<E> inn) { e = null; n = inn; }

        E element() { return e; }                        // Return the value
        E setElement(E it) { return e = it; }            // Set element value
        Link<E> next() { return n; }                     // Return next link
        Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
    }

1. The insertAtPos method below is broken. Assuming that the figure below represents the state of memory, draw the state of memory after list.insertAtPos(1, "C") is called. How should the method be fixed?

      head                                    tail
       |                                        |
       |                                        |
       v                                        v
   +--------+    +--------+   +--------+    +--------+
   | null |-|--> | "A"  |-|-->| "B"  |-|--> | null |x|
   +--------+    +--------+   +--------+    +--------+

   public boolean insertAtPos(int pos, E it) {
   
       // Return false if the position is invalid
       if ((pos < 0) || (pos > listSize)) {
           return false;
       }
   
       // Find the insertion node
       Link<E> current = head.next();
       for (int i = 0; i < pos; i++) {
           current = current.next();
       }
   
       // Insert
       Link<E> newLink = new Link<E>(it, current);
       current.setNext(newLink);
       if (tail == current) {
           tail = current.next(); // New tail
       }
   
       listSize++;
       return true;
   
   }

   
   

Analyzing List Algorithms

Analyze each of the methods below according to the instructions in the Javadoc comments.

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);
       }
   }