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
}

Here is part of the LList class:

class LList<E> implements List<E> {
  private Link<E> head;      // Pointer to list header
  private Link<E> tail;      // Pointer to last element
  private Link<E> curr;      // Access to current element
  private int listSize;      // Size of list

  // Constructors
  LList(int size) {      // Constructor -- Ignore size
    this(); 
  }
  LList() { 
    clear(); 
  }

  public void clear() {
    curr = tail = new Link<E>(null); // Create trailer
    head = new Link<E>(tail);        // Create header
    listSize = 0;
  }

  //...
  
  public E remove () throws NoSuchElementException {
    if (curr == tail) {// Nothing to remove
      throw new NoSuchElementException();
    }
    E it = curr.element();                  // Remember value
    curr.setElement(curr.next().element()); // Pull forward the next element
    if (curr.next() == tail) {
      tail = curr;   // Removed last, move tail
    }
    curr.setNext(curr.next().next());       // Point around unneeded link
    listSize--;                             // Decrement element count
    return it;                              // Return value
  }

Using this code, complete the following diagramming and code-tracing exercises. Do not erase any values or links. Just cross them out.

1. Draw a linked diagram of a freshly constructed list. Mark head, tail, and curr.
2. Draw a linked diagram of a list containing the strings "A", "B", and "C" and which is currently positioned at "B". What happens when remove is called? Update the diagram as you trace through the method’s code. Do not erase any values or links. Just cross them out.

3. Draw a linked diagram of a list containing the strings "A", "B", "C", and "D". and which is currently positioned at "C". What happens when list.precedes("D") is called? Update the diagram as you trace through the method’s code.

   public boolean precedes(E target) {
     Link<E> cursor = head.next();
     while (cursor != curr) {
       if (cursor.element().equals(target)) {
         return true;
       }
       cursor = cursor.next();
      }
      return false;
   }

   
   

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