# Class 38: Iterating Array-Based Lists

Back to Detour: Applets. On to Linked 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.
• Lists can keep expanding
• You don't need to specify the maximum size of the list when you create it.
• ...
• 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?
• Faster insertion and deletion at ends.
• ...
• 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.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Monday, 6 November 2000

• Filled in the details. Most are new.

Back to Detour: Applets. On to Linked Lists.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.