# Class 36: Implementing Lists with Arrays

Back to Exam 2, Continued. On to Detour: Applets.

Held Wednesday, November 1, 2000

Summary

Today we consider how to implement our basic lists using arrays. I call this data structure the Array-based list.

Notes

• I've finally remembered to update the news page.
• On Friday, you will do lab G1, Graphics and Applets. Please read it over before Friday's class.

Overview

• What is a list? Revisited
• Implementing lists with arrays
• Alternative designs

## Lists Revisited

• You may recall that we defined lists as something like:
A potentially empty collection of elements. All non-empty lists have a designated first element and last element. In one-element lists, the first and last element are the same. All but the last element of the list has exactly one successor. All but the first element of the list has exactly one predecessor.
• We also came up with some adjectives to describe lists. Lists are collections that are
• Linear (or at least flat)
• Iterable
• Ordered (in some people's worlds, lists are not ordered)
• Unindexed (in some people's worlds, lists are indexed)
• We debated as to whether lists should have a separate iterator or a build-in "current" element. I'm not sure we resolved this issue, so I'm going to use separate iterators.
• Given these parameters, we have the following basic set of operations for a list.
• Construct a new list.
• Add an element to the front of the list.
• Add an element to the back of the list.
• Delete the first element of the list.
• Delete the last element of the list.
• Clear the list
• Get the iterator for the list
• Iterators might provide
• Reset to the beginning of the list.
• Get the current element of the list.
• Advance the iterator to the next element.
• Determine if the iterator is at the end of the list.
• Java's `java.util.Iterator` class provides
• `getNext`, get the next uniterated element
• `hasNext`, which determines whether or not there is an uniterated element
• `delete` (optional), which deletes the value that corresponds to the most recently returned value.
• Other possible list operations:
• Delete the element "pointed to" by an iterator
• Add an element before or after the iterator
• Other possible iterator operations:
• Determine if the iterator is still on the list (if there are operations that permit you to move the iterator off the list, such as advancing beyond the end of the list; also useful for empty lists).
• Get the underlying list.
• Retreat the iterator.
• Check if we're at the front of the list (so that it's unsafe to retreat).
• We'll decide which are appropriate to implement at each step.

## Implementing Lists with Arrays

• The fields:
• An array of elements
• The cursor (a current element for iteration)
• The length (number of values in the list)
• The constructors:
• With an initial capacity
• Some questions
• Can we do without the array size?
• Are there other things we need?
• Can we do without the length?
• The methods (think about preconditions and postconditions)
• delete(Object o)
• length
• More questions
• Should we copy elements when assigning, or just copy references.
• Others?
• Here's an untested implementation of simple lists in Java.
```/**
* The start of an implementation of Lists, using arrays
* as the underlying implementation structure.
*
* @author Samuel A. Rebelsky
* @version 1.1 of November 2000
*/
public class ArrayBasedList
implements List
{
/** The elements of the list. */
// +--------+--------------------------------------------------
// | Fields |
// +--------+

protected Object[] elements;

/**
* The length of the list (different from the length of
* the array).  Also used as the index of the next element
*/
protected int length;

// +--------------+--------------------------------------------
// | Constructors |
// +--------------+

/** Create a new list of specified capacity. */
public ArrayBasedList(int capacity) {
this.elements = new Object[capacity];
this.length = 0;
} // ArrayBasedSimpleList(int)

// +---------+-------------------------------------------------
// | Methods |
// +---------+

/**
* Add an element to the end of the list.  See the interface for
* other preconditions and postconditions.
* Pre: The list has space available for another element. [Unchecked]
*/
this.elements[this.length] = element;
// Note the increase in length.
++this.length;

/**
* Add an element to the end of the list.  See the interface for
* preconditions and postconditions.
* Pre: The list has space available for another element. [Unchecked]
*/
// Shift everything to the right one space.
for(int i = this.length; i > 0; i--) {
this.elements[i] = this.elements[i-1];
}
this.elements[0] = element;
// Note the increase in length.
++this.length;

/**
* Delete the first element of the list.
* See interface for preconditions and postconditions.
*/
public Object deleteFirst() {
// Remember the first element.
Object oldFirst = elements[0];
// Shift everything left.
for (int i = 0; i < this.length-1; i++) {
this.elements[i] = this.elements[i+1];
}
// Clear the last element.
this.elements[this.length] = 0;
// Note the decrease in length.
--this.length;
// Return the deleted thing.
return oldFirst;
} // deleteFirst()

/**
* Delete the last element of the list.
* See interface for preconditions and postconditions.
*/
public Object deleteLast() {
// Remember the last element.
Object oldLast = this.elements[this.length];
// Clear the last element.
this.elements[this.length] = 0;
// Note the decrease in length.
--this.length;
// Return the deleted element.
return oldLast;
} // deleteLast()

/**
* Get a new iterator for this list.
*/
public Iterator getIterator() {
return new ArrayBasedListIterator(this);
} // getIterator()

/**
* Determine the length of the list.  See the interface
* for preconditions and postconditions.
*/
public int length() {
return this.length;
} // length()

/**
* Determine whether there is space available.  See the
* interface for preconditions and postconditions.
*/
public boolean spaceAvailable() {
// There is space available if the length of the list is
// less than the length of the array.
return this.length < this.elements.length;
} // spaceAvailable()

} // class ArrayBasedList
```

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Wednesday, 1 November 2000

Monday, 6 November 2000

• Removed section on interators for array-based lists (uncovered)

Back to Exam 2, Continued. On to Detour: Applets.

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.