CSC 207 Grinnell College Fall, 2014
 
Algorithms and Object-Oriented Design
 

Implementing the ArrayList Class

Summary

Java's ArrayList class describes an ArrayList as a "Resizable-array implementation of the List interface." The full class has numerous operations, and many of these operations must be implemented within efficiency constraints.

This laboratory explores the ArrayList class, considers implications of possible implementations, and provides practice writing an Iterator class for the ArrayList class.

Introduction

The ArrayList class is designed to have many properties of an array, but at the same time have flexible size. In order to behave similarly to an array in important ways, the efficiency of many operations is specified as follows, assuming the ArrayList currently holds n items:

Operation Order
size O(1)
isEmpty O(1)
get O(1)
set O(1)
iterator O(1)
add amortized O(1)
adding n elements at the end of the list requires O(n) overall
elements can be inserted at the end or at any designated position i
remove O(n)
indexOf O(n)
lastIndexOf O(n)
contains O(n)

The full ArrayList class includes a variety of other methods as well, many of which involve working with collections of data. For the purposes of this lab, however, the above methods (plus the empty constructor) will suffice.

For clarity, the rest of this lab constructs to a new class MyArrayList, which satisfies the ArrayList specifications, but which we build on our own. An initial stub for this class may be found at MyArrayList.java

Implementation Basics

The class MyArrayList will be a generic type that holds objects of class E. MyArrayList has two internal fields, and its definition begins as follows:

   public class MyArrayList<E> 
   {
      private E myArray [];
      private int numStored;  // the number of items actually stored in myArray

      /***
       * the default constructor
       */
      public MyArrayList ()
      {
         // initially, the internal array has room for 10 items,
         // but no items have actually been inserted
         myArray = (E[]) new Object [10];
         numStored = 0;
      }

      // other public methods follow, BUT
      // no other fields are declared outside of individual methods
      //    — except perhaps for the extra credit part at the very end of this lab
   }

The add Methods

The ArrayList interface provides two ways to insert a single item:

The idea of an addition is reasonably simple: if myArray is sufficiently large to accommodate another item, then addition is easy:

   myArray[numStored] = e;
   numStored++;

However, if myArray already is full (i.e., if numStored == myArray.length), then

Although this outline is reasonably straightforward, the question arises as to how large the new array should be. There are at least 3 choices:

  1. the new array could be 1 larger than the old array
  2. the new array could be some constant number of items larger than the previous (e.g., when a new array is needed, increase the size of the old array by 10).
  3. the new array could be constructed as being twice the size of the original array.

Overall, the above notes give rise to the following code for add (e):

   public void add (E e)
   {
      // check if myArray must be expanded
      if (numStored == myArray.length)
         {
            E newArray [] = (E[]) new Object [/* size to be determined */];
            for (int i = 0; i < numStored; i++)
                newArray[i] = myArray[i];
            myArray = newArray; 
         }

   // insert the given element into myArray
   myArray[numStored] = e;
   numStored++;
   }
  1. Suppose n items are to be inserted into a MyArrayList object— each at the end of the array.

    Determine the amount of work required for each of the approaches for expanding the size of myArray. That is, analyze how many times each step is performed and derive an expression for the total amount of work performed.

    Notes: Feel free to assume n = 10r or n = 2t, if such an assumption would simplify your analysis.

  2. The specification of ArrayList indicates that the addition of n items should run in O(n). Which, if any, of the approaches for expanding the size of myArray meet this specification? Justify your answer.

  3. Expand/modify/rewrite add (E e) to give a complete implementation of add (int index, E e).

The remove Methods

The method remove (int i) deletes the ith element in the array. Thus, after the operation, elements in positions 0..i-1 are not affected, and an item originally in position j (j > i) will thereafter be in position j-1.

To implement remove (i), the number of elements in the array is reduced by 1. Also, there are at least 2 approaches for handling myArray:

Note that there rarely is an reason to make myArray smaller — extra space in the array simply will not be used unless more items are added later.

  1. Analyze each of the two approaches for remove, based on there being n elements in myArray. Wat is the order of the algorithm for each approach?

  2. Suppose a MyArrayList object were used over a period of time, with numerous adds and removes. For each approach for remove, answer the following

  3. Which, if any, of the algorithms for the removal of an item meet the ArrayList specification?

  4. Implement the remove method.

Implementing an Iterator

An Iterator is an object that allows a program to move sequentially through elements in a collection. When the collection has an order (e.g., item at index 0, item at index 1, etc.), the Iterator normally is expected to maintain the order.

In implementing an Iterator, one normally does not copy the full structure. Rather, the Iterator maintains a reference to the structure through some internal field. Also, the Iterator likely maintains a few private fields (usually just one or two fields) to keep track of where processing within the structure is taking place.

Since an Iterator moves sequentially through a structure, troubles could arise if the structure changed during processing. Thus, an Iterator normally provides a method remove to change the current item in the structure. However, any other changes to the structure typically yield an exception. Also, note that remove for the Iterator can only be called once for each call to next.

  1. Implement an iterator method for MyArrayList. See examples of iterators in MyArray1.java and MyArray2.java. (The second example may be more relevant here.)

Extra Credit

The documentation for ArrayList states "The iterators returned by this classes's iterator ... are fail-safe: if the [Array]List is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException."

  1. Modify MyArrayList and/or your iterator to through a ConcurrentModificationException, if required, when using the iterator.


This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-arraylist.shtml

created 30 March 2012
last revised 3 April 2012
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.