Laboratory: Implementing Lists with Arrays

Skim through the documentation for Iterator and ListIterator. You should identify the primary methods, their meanings, and any subtleties.

Make sure that you can answer the following questions. You may find it useful to run some experiments to check your answers. The file ArrayListExperiment.java is a good starting place for your experiments.

a. Where, conceptually, is an iterator relative to the elements of a list?

b. What element does remove remove? For example, if an iterator, it, is between the a and the b in the list [a,b,c] and we call it.remove(), which value does it remove?

c. Suppose we have a list iterator, lit, and call lit.add(x) and then immediately after call lit.add(y). In what order will x and y appear in the list?

d. Suppose we have a list iterator, lit, between the a and b in the list [a,b,c]. Suppose we then call lit.remove() and then immediately after call lit.remove() again. What can or should happen?

e. Can we add an element using a list iterator immediately after creating that list iterator? Why or why not?

f. Can we remove an element using a list iterator immediately after creating that list iterator? Why or why not?

g. Can we set an element using a list iterator immediately after creating that list iterator? Why or why not?

h. Suppose we've created two list iterators, lit1 and lit2 for the list [a,b,c], and both are between the a and the b in the list. If we call lit1.add(d), what should lit2.next() return?

i. Suppose we've created two list iterators, lit1 and lit2 for the list [a,b,c], and both are between the a and the b in the list. If we call lit1.remove(), what should lit2.next() return?

j. What other subtleties, if any, have you noticed about these two kinds of iterators?

Look at the SimpleList interface. You will note that it contains only two methods, iterator and listIterator.

a. You may recall that we decided that lists are dynamic, user-ordered, homogeneous collections of values. Does the SimpleList interface achieve that goal? Why or why not?

a. You may also recall that we decided that lists need methods to add elements (at the front, at the back, at particular positions). How do we add elements to SimpleLists? Can we control where in the list those elements go?

b. You me recall that we decided that lists need methods to remove elements. How can we remove elements from SimpleLists?

Read through the code of SimpleListExpt.java and SALExpt.java.

a. Sketch the output you expect to see from SALExpt.

b. Check your sketch experimentally.

The class SimpleArrayList.java contains an array-based implementation of the SimpleList interface. How are these array-based-lists implemented? It's time to look. We'll start with fields. Once we've examined the fields, we can start considering the implementation of various methods.

Here are the two basic fields. (There are a few others.)

public class SimpleArrayList<T>
  implements SimpleList<T>
{
  /**
   * The array used to store the list elements.
   */
  T[] values;

  /**
   * The number of values actually in the list.
   */
  int size;

Of course, most of the work happens in the iterators. Because these iterators will need to access the fields of the SimpleArrayList that they are iterating, we use anonymous inner classes. The anonymous inner class has one main field, pos.

  public ListIterator<T> listIterator()
  {
    return new ListIterator<T>()
      {
        /**
         * The position in the list of the next value to be returned.
         */
        int pos = 0;

        ...
      }; // new ListIterator<T>
  } // listIterator()

a. Sketch how you would implement the next method.

b. Compare your answer to that in the code. You can ignore the call to failFast. We'll come back to that in another exercise.

c. Sketch how you would implement the hasNext() method.

d. Compare your answer to the answer in the code.

e. Sketch how you would implement the add(T val) method.

f. Compare your answer to the answer in the code.

You may note that the set method is not yet implemented.

a. Write a small experiment that will let you check if set works. For example, you might create a list of five values and set elements 0, 2, and 4 to other values. Don't bother checking the extreme edge cases, such as what happens when there has not been a prior call to next or prev.

b. Here's a simple strategy for implementing set. Since pos represents the location of the value to be returned by next, pos-1 represents the location of the value that was last returned. Hence, all set needs to do is set the value in the array at that location.

What flaws, if any, do you see in this strategy?

c. Implement set using this strategy and, through your experiment, determine whether or not it seems to work.

d. If we use this strategy, one time that set will fail is when pos is 0. Update your program so that it throws an exception in such cases.

e. As you may have noted, a possible flaw in this implementation is that, while it works when we move forward with next, it will likely fail when we use prev. Sketch a strategy for dealing with this problem. (You do not need to implement the strategy.)

You may recall that in exercise 1, we asked what happens when we mutate a list using one iterator and then try to access it using another iterator for the same list. You probably found that the documentation for iterators is vague on this issue. You should have also noted that the vagueness is problematic. So, what should we do?

Let's see what the designers of Java did by looking at the standard java.util.ArrayList class.

a. If you look at SimpleListExpt.java, you'll see a method called failFastExpt. Explain to your partner how this allows us to understand fast failure.

b. Add the following line to the main method of SALExpt.java so that we can see if our simple array-based lists fail fast, at least in a simple situation. (After adding the line, you should recompile and run SALExpt.)

    SimpleListExpt.failFastExpt(pen, new SimpleArrayList<String>());

c. Suppose you were called upon to implement the “fail-fast” policy. How would you achieve that goal?

d. Read through the code for SimpleArrayList.java to see how it achieves the “fail-fast” policy.

You'll note that the previous method is not implemented. Implement it.

Once we implement previous, we are likely to break the set method we defined earlier. Fix that method.