Lab 10: Methods that operate on linked lists; List ADT

Task 1: Trace a recursive linked-list method

The StringNode class allows to build a 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) {  // explicit base case
        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, therefore, we don’t need to use the name of the class to call the method.

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: 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");

Task 3: A list of objects, using the List Interface

Download the following zip file: lab10.zip

Unzip this archive, and you should find a folder named lab10, and within it the files you will need for the remaining two tasks.

The following List interface:

public interface List {
    Object getItem(int i);
    boolean addItem(Object item, int i);
    Object removeItem(int i);
    int length();
    boolean isFull();
}

has been implemented in the two classes:

• ArrayList, which uses an array to store the items
• LLList, which uses a linked list.

Consider the following lines of client code:

List vals1 = new ArrayList(10);

vals1.addItem("hello", 0);
vals1.addItem("world!", 0);
vals1.addItem("how", 1);
vals1.addItem("are", 1);
vals1.addItem("you?", 2);

System.out.println(vals1);

1. Note that we declare vals1 to be of type List even though the object that we’re assigning to it is of type ArrayList. This is the power of polymorphism. Objects of classes that implement an interface are also objects of the interface type. This will be discussed more in lecture next week.

2. The ArrayList class includes a toString() method, and therefore printing vals1 will show us the items in the list from position 0 to the end of the list.

   Given the calls to addItem() shown above, what order will the strings be in when vals1 is printed?

3. Write a sequence of method calls that rearrange the items in vals1 (removing and reinserting them as needed) so that printing the list will gives us the following:

   {hello, world!, how, are, you?}
   

   Important:

   • You should not change the original calls to addItem(). You should add new method calls that rearrange the items.

   • Your new method calls should not use any string literals. Rather, for each item that needs to move, you should:

     • make a call to remove the item, and store the removed item in a variable

     • make a call to readd the item at the appropriate location, and use the variable as part of that call.

   • When removing the items, if you use a variable of type String, you will need to perform a type cast, which looks like this:

     String item = (String) ...;
     

   • Try to accomplish the reordering using as few method calls as possible!

4. Change the line that creates the list object so that it creates an LLList instead of an ArrayList.

   • Open the LLList class to remind yourself of what parameters the LLList constructor takes, and call it accordingly.

   • No other lines of code need to be changed! Because both ArrayList and LLList implement the List interface, they both support the methods in that interface.

   • Rerun the code to confirm that it still produces the same output. The items are now being stored in a linked list instead of an array, but our list operations end up producing the same abstract list!

Task 4: Search a list

Suppose that we have a list of items, and we want to determine whether the list contains a given item.

Here’s a template for one possible way that we could do this from within a client program:

public static boolean contains(List items, Object item) {
    if (items == null || item == null) {
        return false;
    }

    for (int i = 0; i < ______________; i++) {
         ________ itemAt = ______________;    // get item at position i
         if (______________________) {
             return true;
         }
    }

    return false;
}

1. Complete this method by filling in the blanks. Consult the List interface as needed to remind yourself of the available methods.

2. Add code to the main() method that uses this method to:

   • search for the string "hello" in vals1 and print a message indicating whether it was found
   • search for the string "goodbye" in vals1 and print a message indicating whether it was found.

3. What are the time efficiencies (best-, worst-, and average-case) of this contains() method as a function of the length n of the list:

   • if we pass in an instance of our ArrayList class?
   • if we pass in an instance of our LLList class?

4. How could we rewrite the contains() method so that it is efficient for both implementations of our List interface?

   Go ahead and do so, giving the new method the name contains2().