Lab 8: Lists and stacks

Task 0: Prepare for lab

Download the following zip file: lab8.zip

Unzip this archive, and you should find a folder named lab8, 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. Why can we declare vals1 to be of type List when the object that we’re assigning to it is of type ArrayList? 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().

Task 3: Understand stacks

Your work for the first part of this task should be done on paper. Please show your work to a staff member before you leave the lab.

1. Given the following stack, depicted here from top to bottom:

   +     +
   | "f" |  top
   | "e" |
   | "a" |
   | "c" |
   | "b" |
   +-----+
   

   Show what the stack look like after each of the following sequence of pushes and pops:

   pop()
   push("x")
   push("w")
   str = pop()
   pop()
   push("z")
   push(str)
   

2. Create a client program called StackClient with a main() method in which you do the following:

   1. Construct a stack object (either an ArrayStack or an LLStack) and assign it to a variable.

      Hint: Don’t forget that our stack implementations are generic classes, so you’ll need to specify the type of item when you declare the variable and when you construct the stack object. For example:

      Stack<...> s1 = new ArrayStack<...>();
      or 
      Stack<...> s1 = new LLStack<...>();
      

      where you replace the ... with the appropriate data type. You can create a reference to either stack implementation and the methods will produce the same results.

   2. Perform a series of pushes to create the stack shown at the beginning of this task. Make sure that you push them in the appropriate order!

   3. Print the stack, which should show you the items from top to bottom as follows:

      {f, e, a, c, b}
      

      If you don’t see this result, modify your calls to push() as needed.

   4. Perform the above sequence of modifications to the stack. When you assign the result of the second call to pop() to a variable, you will not need a type cast. Why not?

   5. Reprint the stack after all of those operations have been performed. Doing so should provide the following output:

      {w, z, e, a, c, b}
      

3. Could you add code to your client program that removes the "z" without first removing another item? Why or why not?

Task 4: Analyze another approach to searching (optional)

Your work on this task should be done on paper. Please show your work to a staff member before you leave the lab.

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?

Task 5: Submit your work

You should show the paper with your work to the teaching assistant.

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.