Lab 9: The List ADT

Task 0: Prepare for lab

Download the following zip file: lab9.zip

Unzip this archive, and you should find a folder named lab9, and within it the files you will need for this lab.

Task 1: Work with list objects

In lecture, we’ve been working with 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();
}

We’ve examined two classes that implement it:

• 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 can declare vals1 to be of type List, even though the object that we’re assigning to it is of type ArrayList.

   This is another example of polymorphism, which we discussed earlier in the semester, except instead of using a superclass as the declared type of the variable, we are using the interface that the class implements.

   What is the benefit of doing this?

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 2: Search a list

Your answers to the non-coding parts of this task should be done on paper. Please show your work to a staff member before you leave the lab.

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 and adding it to the file that you used for Task 1. 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().

   Note: Students in the B1 lecture will discuss the construct needed for contains2 during Friday’s lecture. They may want to wait until after that lecture to complete this method.

Challenge

Task 3: Analyze another approach to searching

The approach to searching taken by our contains() method from Task 2 is referred to as linear search or sequential search.

If we knew that the list were sorted, we could use binary search instead. Here is pseudocode for an iterative implementation of that algorithm:

bin_search(list, item) {
    min = 0
    max = list.length()

    while (min < max) {
        mid = (min + max) / 2
        midItem = list.getItem(mid)
        if (midItem is equal to item) {
            return true
        } else if (midItem is less than item) {
            max = mid - 1    // item must come before position mid
        } else {
            min = mid + 1    // item must come after position mid
        }
    }

    return false
}

What is the worst-case time efficiency of this bin_search method:

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