Fundamentals of Computer Science II (CSC-152 2000F)


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

Overview


Lists Revisited

Implementing Lists with Arrays

/**
 * 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
   * to add.
   */
  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]
   */
  public void addToEnd(Object element) {
    // Add the element.
    this.elements[this.length] = element;
    // Note the increase in length.
    ++this.length;
  } // addToEnd(Object)

  /**
   * 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]
   */
  public void addToFront(Object element) {
    // Shift everything to the right one space.
    for(int i = this.length; i > 0; i--) {
      this.elements[i] = this.elements[i-1];
    }
    // Add the new element.
    this.elements[0] = element;
    // Note the increase in length.
    ++this.length;
  } // addToFront(Object)

  /**
   * 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

Thursday, 24 August 2000

Wednesday, 1 November 2000

Monday, 6 November 2000

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.

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Outlines/outline.36.html

Source text last modified Mon Nov 6 08:48:49 2000.

This page generated on Mon Nov 6 08:54:02 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu