Compsci 100, Fall 2009, Linked Questions

name: __________________________   login: _____________

name: __________________________   login: _____________

name: __________________________   login: _____________
The code below is also accessible as file ListStuff.java, questions follow the code.

public class ListStuff { public static class Node { String info; Node next; public Node(String s, Node link){ info = s; next = link; } } public static Node array2linked(String[] arr){ Node first = null; Node last = null; for(String s : arr){ if (first == null){ first = new Node(s,null); last = first; } else { last.next = new Node(s,null); last = last.next; } } return first; } public static void print(Node list){ while (list != null){ System.out.print(list.info+" "); list = list.next; } System.out.println(); } public static Node copy(Node list){ if (list == null) return null; return new Node(list.info, copy(list.next)); } public static Node reverse(Node list){ if (list == null || list.next == null) return list; // list has at least 2 nodes in it Node revAfterFirst = reverse(list.next); // at this point, revAfterFirst points at the reverse // of what comes after the first node of the parameter list. // But the first node/list *STILL* points at what used to be the second node, // but which is now the last node of the reversed list. list.next.next = list; list.next = null; return revAfterFirst; } public static Node addXNodes(Node list){ if (list == null || list.next == null) return list; list.next.next = new Node(list.next.info, addNodes(list.next.next)); return list; } public static Node addNodes(Node list){ if (list == null) return list; list.next = new Node(list.info, addNodes(list.next)); return list; } public static void main(String[] args){ String[] arr = {"apple", "banana", "guava", "mango",}; Node list = array2linked(arr); Node list2 = copy(list); print(list); print(list2); print(reverse(list)); // print(addNodes(list2)); } } The output when run is: 
 apple banana guava mango
 apple banana guava mango
 mango guava banana apple
  1. Write a sentence or two explaining how the method copy creates and returns a copy of the entire list passed to it.
  2. In on call of array2linked how many times does the expression first == null evaluate to true? Why?
  3. Occurs Check

    1. Write a method hasDuplicates whose header follows. The method returns true if parameter list has any duplicates (words occurring more than once) and false otherwise. For example, for the list 
       ( "apple", "guava", "cherry")
      hasDuplicates should return false, but it would return true for the list below since "guava" appears twice. 
       ( "apple", "guava", "cherry", "guava")
      In writing hasDuplicates you must call the method countOccurrences shown below and your method must be either a recursive function with no loop or a function with one loop. Either version can include calls to countOccurrences. You cannot use any ArrayList, Set, etc. objects in your code. /** * @return the number of occurrences of s in list */ public static int countOccurrences(Node list, String s) { if (list == null) return 0; int count = 0; if (list.info.equals(s)) count = 1; return count + countOcurrences(list.next,s); } /** * @return true if and only if list has duplicates */ public static boolean hasDuplicates(Node list) { }

    2. What is the complexity (using big-Oh) of the solution you wrote to hasDuplicates and why?
    3. Describe how to write a more efficient solution to the hasDuplicates method using, for example, a TreeSet or a HashSet instead of calling countOccurrences. Be sure to indicate what the complexity of your solution is and why.

  4. The method reverse reverses a linked-list -- no new nodes are created, the original order of the list is reversed as shown in the diagrams below.

    Here is the list before it is reversed, the parameter list references the first node of the list.

    apple banana guava mango

    The first recursive call passes a pointer to the "banana" node to a method reverse. This invocation of reverse generates the second recursive call in which parameter list points at the third node, "guava", as shown below. apple banana guava mango

    This second invocation of reverse results in local variable revAfterFirst pointing at the node containing "mango". Briefly explain why.
    Redraw the list just as the return statement return nodeAfterFirst executes where that variable points to "mango" as shown.

  5. To analyze the runtime of reverse assume each time the next field of any node is referenced (to see what it points to) a cost of one cent is incurred, and that each time a value is assigned to a next field a cost of one cent is incurred.

    1. This means that reversing a one node list has a cost of one cent. Why?
    2. The cost of reversing a 2-node list is five cents as follows:

      code cost
      making the call reverse(list.next) one cent
      the cost of executing/reversing the list with one node one cent
      after the call, list.next.next = null and list.next = null three cents

      What is the cost of reversing a three node list and a five node list? Justify your answer.
    3. What is the cost of reversing a list with N nodes? Why?

  6. What does method addNodes do -- specifically what is printed by the last print statement and why (if it executes)?
  7. Write a non-recursive method that returns a pointer to the middle node of a linked list. This is the fifth node of a nine-node list and the fourth node of an eight-node list. public static Node findMiddle(Node list) { }