Problem Set 8 FAQ

Part I

1. For problem 3, I’m having trouble determining the time efficiencies. Do you have any suggestions?

   One way to do this is to make a table that records the approximate number of items/nodes processed by each of the two methods calls (getItem and addItem) for each value of the loop variable i:

   i    # processed by getItem   # processed by addItem
   --   ----------------------   ----------------------
   0
   1
   2
   ...
   

   You won’t need to fill the table in entirely in order to see a pattern emerge that you can use to determine an approximate expression for the total number of elements/nodes processed by the algorithm, and to derive a big-O expression from it.

2. For problem 3, part 2, I’m having trouble thinking of ways to improve the efficiency. Do you have any suggestions?

   In lecture, we analyzed the efficiencies of the methods in ArrayList and LLList. See if you can revise the method so that it takes advantage of the best cases of the relevant methods.

Problems 5 and 6

1. In problems 5.1, 5.3, and 5.5, we have to write iterative versions of existing recursive methods of the StringNode class. Can you give us any general tips on converting recursive methods into iterative methods?

   In general, when writing iterative versions of these methods, a good starting point is the template for iterative traversal of a linked list given in lecture:

   StringNode trav = __________;   // add expression for first node in list
   while (trav != null) {
       // do something here
       trav = trav.next;           // advance to next node
   }
   

   Then decide what needs to be done inside the loop, and what (if any) special cases need to be handled outside the loop. Special cases that often need to be handled outside the main loop include an empty list, and a list with only one node; however, there are certainly instances where either or both of these cases can be handled within the loop itself.

   Make sure your methods handle these boundary cases of an empty list and a list with only one node correctly! It’s very easy to write a method that works fine with a list with at least two nodes, but fails with a null pointer exception or otherwise behaves incorrectly with smaller lists.

   You also need to think carefully about what local variables your iterative method will need, and how these locals should be initialized. For example, is a single “trav” reference sufficient, or do you need to use a trailing reference as well?

   See the numOccurrences() and read() examples from the section notes for two examples of a recursive to iterative conversion.

2. In problems 5 and 6, are we allowed to change the method headers in any way?

   No. You must use the method headers we have given you.

3. When writing recursive methods in problems 5 and 6, can we call a helper method to perform the recursion?

   No, the methods themselves must be recursive – i.e., they must call themselves. You should not need to write additional helper methods for these methods.

4. I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for problems 5 and 6. Do you have any hints on how to do this?

   One thing that can help is to consider what should happen for one or more concrete cases.

   For example, let’s say that you needed to write a recursive numOccur method for the StringNode class. As with many recursive methods that operate on linked lists, this method should make recursive calls on ever shorter linked lists – i.e., on the rest of the list. For example, let’s say that we wanted to do numOccur([linked list for "recur"], 'r')

   This would lead to the following sequence of method calls:

   numOccur([linked list for "recur"], 'r')
       numOccur([linked list for "ecur"], 'r')
           numOccur([linked list for "cur"], 'r')
               numOccur([linked list for "ur"], 'r')
                   numOccur([linked list for "r"], 'r')
                       numOccur(null, 'r')
   

   where [linked list for ...] represents a reference to the first node in the linked list for the specified string.

   Then, once you have the sequence of method calls, think about what each of these separate method calls should return, treating them as if they were independent of each other. For example, what should numOccur([linked list for "cur"], 'r') return – i.e., how many times does 'r' occur in "cur"? Based on these return values, you should be able to figure out how a given invocation of the method should use the return value from the recursive call to form its own return value.

5. One of my recursive methods for problems 5 and 6 is not working correctly. Do you have any suggestions?

   Try tracing through some concrete examples of cases in which your method is not returning the correct value. You might also want to try adding some temporary printlns to see if that helps you to diagnose the problem. In particular, you could print what the method will return before it actually returns it. That will allow you to see when the wrong value is being returned.

   In addition, if your method returns a value, make sure that you aren’t throwing away the return value of the recursive call. For example, consider this incorrect version of a recursive method that copies a linked-list string:

   public static StringNode copy(StringNode str) {
       if (str == null) {
           return 0;
       }
   
       StringNode copyFirst = new StringNode(str.ch, null);
   
       // XXX: recursive call -- return value is thrown away
       copy(str.next);
   
       return copyFirst;
   }
   

   This version of the method makes the correct recursive call – passing in a reference to the first node in the rest of the linked list – but it throws away the value that is returned.

   To avoid losing the return value of the recursive call, we can do one of two things:

   1. assign it to a variable, and then do something with that variable

   2. make the recursive call part of a return statement, if doing so makes sense. It may not always make sense – especially if the value that the current method call should return depends on the value that was returned by the recursive call.

6. I tried using Java Tutor to step through one of my StringNode methods, but it says that the code has too many steps to execute. Do you have any suggestions?

   Yes. You should use a stripped-down version of the StringNode class in which you take out almost all of the methods and just leave only the following:

   • the fields
   • the constructor
   • the method you are trying to trace
   • a main method in which you manually build a simple linked list and then call your method to process it.

   Manually building the linked list is better than using the convert method because convert requires a lot of steps. Here’s a simple example in which we build a linked list for the string "cat":

   StringNode s1 = new StringNode('t', null);
   s1 = new StringNode('a', s1);
   s1 = new StringNode('c', s1);
   

   Note that we start with the node for the last character and work backwards towards the node for the first character, so that each node’s next field can be made to point to the node that comes after it.

   You can find an example of using this approach to test the original version of the toUpperCase method here.

   Here’s how to use Java Tutor:

   1. Go to Java Tutor.

   2. Remove the provided code and replace it with your stripped-down version of StringNode – something like our example.

   3. Click the Visualize Execution button below the code, which will eventually bring you to a separate page.

   4. Use the Next button below the code to trace through the program. As you do so, you should see the stack frames and the StringNode objects displayed on the right-hand side of the window. (Note: Stack frames labeled <init> are for calls to the StringNode constructor.)

7. I’m stuck on the iterative version of the copy method. Any suggestions?

   A good model for this method is the convert method found in the original StringNode class.

   convert takes a Java String object and uses iteration to build a linked list containing the characters from that string. Your iterative copy method will also build a new linked list, but the characters will come from an existing linked list instead of from a Java String.

   The overall approach needed to build the new linked list will be very similar to the approach taken by convert. In particular, it will be helpful to maintain a number of different references to nodes in the new linked list (firstNode, prevNode and nextNode), just as convert does.

   Note that convert is able to use a for loop because it can easily and efficiently get the length of the Java string s by using s.length(), and thus it can know exactly how many repetitions are needed. Your copy method should use a while loop instead, because you don’t know how many nodes are in the original linked list, and it doesn’t make sense to call the StringNode.length() method since it would need to make an extra traversal of the linked list.

Problem 7

1. For problem 7, can we make use of the LLList class, or do we need to create our own linked list class from scratch?

   You need to implement your own linked list. However, you do not need to write a separate class for the linked list itself. The only additional class that you will need besides LLBag is a class for the nodes in the linked list, which should be a private inner class called Node within your LLBag class. See the LLList, LLStack, and LLQueue classes for examples of this.

   You should use a field within your LLBag class to hold a reference to either the first node of the linked list or the dummy head node, if you choose to use one. Then, you should write LLBag versions of the methods found in ArrayBag, rewriting them so that instead of manipulating an array of items they manipulate a linked list of Node objects.

Last updated on July 27, 2026.