Lab 7: Methods that operate on linked lists

Task 1: Trace a recursive linked-list method

Your work for this task should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

In lecture, we have continued to work with linked lists of characters, where each node in the linked list is an instance of the following class:

public class StringNode {
    private char ch;
    private StringNode next;
    ...
}

One of the methods in the StringNode class is the following recursive method called numOccur:

public static int numOccur(StringNode str, char ch) {
    if (str == null) {
        return 0;
    }

    int numInRest = numOccur(str.next, ch);
    if (str.ch == ch) {
        return 1 + numInRest;
    } else {
        return numInRest;
    }
}

It finds the number of occurrences of the character ch in the linked list to which str refers.

Considered the following linked list, which represents the string "java":

Trace the following call of the numOccur() method on this linked list:

int count = numOccur(s, 'a');

which we assume is being made from the main() method in the StringNode class.

You should begin with something like the following at the bottom of the page:

Note that we have included the stack frame for main(), and above it the stack frame for the initial call to numOccur(). (We’ve omitted the parameter ch from that stack frame, because its value ('a') doesn’t change over time.

To complete the trace, you should:

• Add stack frames as needed for each recursive call – filling in the the value of str in each of them – until you reach the base case.

• On the way back from the base case, fill in the value of numInRest in each stack frame, continuing until you get back to the main() method.

• Fill in the value of count that is assigned after the initial call to numOccur() has returned.

Task 2: Convert a recursive method to an iterative one

To begin this task:

• Create a folder named lab7.

• Download StringNode.java, and save it in the lab7 folder.

• Open the file in DrJava.

Rewrite the numOccur() method that we traced in Task 1. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

You should make use of the template for iteratively traversing a linked list that we considered in lecture:

StringNode trav = str;    // make trav point to the first node
while (trav != null) {
    // do something here
    trav = trav.next;
}

To test your iterative version of the method, compile the class, and try tests like this one from the Interactions Pane:

> StringNode s = StringNode.convert("java");
> StringNode.numOccur(s, 'a')
2

Task 3: Trace an iterative linked-list method

The StringNode class includes another method called convert that uses iteration to gradually convert a Java String object to a linked-list string:

public static StringNode convert(String s) {
    if (s.length() == 0) {
        return null;
    }

    StringNode firstNode = new StringNode(s.charAt(0), null);
    StringNode prevNode = firstNode;
    StringNode nextNode;

    for (int i = 1; i < s.length(); i++) {
        nextNode = new StringNode(s.charAt(i), null);
        prevNode.next = nextNode;
        prevNode = nextNode;
    }

    return firstNode;
}

We used this method in our testing for Task 2.

Note that the method uses several variables of type StringNode:

• one called firstNode, which holds a reference to the node containing the first character; we need this variable so that the method can return a reference to the first node after the entire linked list has been created

• one called nextNode, which is used to hold a reference to each new node that is created (except the first node)

• one called prevNode, which starts out pointing to the first node, and which stays one node behind nextNode in the linked list

Let’s trace through the execution of the following call of this method:

StringNode s1 = StringNode.convert("node");

As we trace through it on the board, add the diagram to the paper that you used in Task 1.

Task 4: Convert an iterative method to a recursive one

Now rewrite the convert() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead.

Your new method should be much simpler! It should take advantage of our usual recursive approach to processing strings – both Java String objects, and strings that are represented as linked lists:

• base case: if the string is empty, handle it directly

• recursive case: take care of the first character, and make a recursive call to handle the rest of the string.

To test your recursive version of the method, compile the file, and try tests like this one from the Interactions Pane:

> StringNode s = StringNode.convert("node");
> System.out.println(s);
node

(Note: We are able to see the string when we print it because our StringNode class includes a toString() method.)

Task 5: Submit your work

You should show the paper with your work on Tasks 1 and 3 to the teaching assistant.

You should use Apollo to submit the following file:

• your modified StringNode.java file containing the changes you made in Tasks 2 and 4

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate lab section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.