Class 42: Implementing Lists with Arrays

Held: Tuesday, April 18, 2006

Summary: Today we consider issues in the implementation of lists with arrays.

Related Pages:

• EBoard.
• Sample Code.

Notes:

• Are there questions on Homework 14?

Overview:

• Adding Preconditions and Postconditions.
• Testing.
• The Vector-Based Implementation.
• Validating Positions.

Adding Preconditions and Postconditons

• I've made the executive decision that we will use positions rather than iterators.
• Consider the resulting SimpleList interface.
• What are the preconditions and postconditions for each method?
• Do they differ in the remaining interfaces?

Testing

• Now that we have a list of functions, let's consider how we might be confident that an implementation works, even if we don't know how the implmentation works.
• I've started us with two tests. What other ones would you like to try?

The Vector-Based Implementation

• Now we are ready to consider our implementation.
• A VectorBasedSimpleList has one primary field, the underlying vector.
• Positions are integers (well, wrapped integers).
• How do we implement each method?

Validating Positions

• Given that removal and addition potentially "invalidate" positions, how can we decide whether or not a position is valid?