Class 38: Iterating Array-Based Lists

Held Monday, November 6, 2000

Summary

Today we continue our consideration of array-based lists by building an iterator for those lists.

Notes

• How did Friday's class go?
• I got back to 120 email messages. I have not yet gone through them all. If you send me email, expect a response later today or this evening.
• On Thursday, the Math/CS Journal club presents a talk by Ole Nelson on the Game of Life on a Toriod. Should be cool.
• Nope, no homework assignments yet. The next homework assignment will involve careful implementation of variants on array-based lists
  • Expandable
  • Shifted within the array
• We're making some good progress on the CS search. I'll do my best to keep you posted.

Overview

Iterating Array-Based Lists

• Two fields:
  • The underlying array-based list
  • The position in that list.
• Methods typically involve moving the position.
• Here's some sample code

  /**
   * Iterators for array-based lists.
   *
   * @author Samuel A. Rebelsky
   * @version 1.0 of November 2000
   */
  public class ArrayBasedListIterator {
    // +--------+--------------------------------------------------
    // | Fields |
    // +--------+
  
    /** The underlying list that we're iterating.  */
    protected ArrayBasedList list;
  
    /** The curernt position in the list. */
    int position;
  
    // +--------------+--------------------------------------------
    // | Constructors |
    // +--------------+
  
    /** Build a new iterator for a particular list. */
    public ArrayBasedListIterator(ArrayBasedList base) {
      this.list = base;
      this.position = 0;
    } // ArrayBasedListIterator(ArrayBasedList)
  
    // +-----------+-----------------------------------------------
    // | Observers |
    // +-----------+
  
    /** Get the current element. */
    public Object getCurrent() {
      return this.list.elements[this.position];
    } // getCurrent()
  
    // +-----------+-----------------------------------------------
    // | Modifiers |
    // +-----------+
  
  } // class ArrayBasedListIterator
  

Modularity and Iterators

• Note that these iterators need to access the elements field of ArrayBasedList.
  • Doesn't this seem to be a violation of protection and modularity?
  • What happens if we make the elements field private (or "package")?
• There are a number of ways we can get around these problems.
• One possibility is to put the two classes in the same package. A package is a collection of classes that are allowed greater access to each other than normal.
• A second is to make ArrayBasedListIterator a protected class within the file ArrayBasedList.java. Then it is legal to build them from within ArrayBasedList but not elsewhere.

Variations on Array-Based Lists

• We can make arrays grow.
• We can permit gaps in the array.
• We can start elsewhere besides 0 and treat the array as circular.
• Combinations?

Expandable Array-Based Lists

• What happens when you run out of space in the array?
  • Traditionally, you disallow the addition of new elements if the array has no space remaining.
• You might also create a new, bigger, array when you run out of space.
• Advantages:
  • Lists can keep expanding
  • You don't need to specify the maximum size of the list when you create it.
  • ...
• Disadvantages:
  • Inserting an element may no longer take constant time
  • May still run out of memory
  • Potentially complicated implementation
  • ...
• Questions:
  • How much do you expand? Ratio? Fixed amount?
  • Should you specify expansion in the constructor?
  • Should there be variations on insert (e.g, insertIfCheap)?

Shifting the List

• We might decide not to require that the 0th element be the first element.
  • That is, we might shift the list within the array.
• We might also allow wraparound.
• Fields:
  • We need a first field.
  • Do we need a last field?
• When you delete the first element, you simply advance first.
• When you insert before the first element, you decrement first.
  • Other details?
• Advantages:
  • Faster insertion and deletion at ends.
  • ...
• Disadvantages:
  • Complicated implementation
  • May make growing the array harder.

Gaps

• If we permit deletion in the middle of the list, we can allow gaps in the array (rather than shifting).
• null might represent a gap.
• When you need an element and there's a gap where you are, keep advancing until you find an element.