Collection202.java

import java.util.*;

/**
 * A subset of the Java Collections Framework Collection interface.
 *
 * @author Jim Glenn
 * @version 0.1 11/10/2004
 */

public interface Collection202
{
    /**
     * Adds the given item o this list.  Returns true if successful,
     * or false if there was some reasont he object could not be added.
     *
     * @param o the object to add
     * @return true iff the object was added
     */

    public boolean add(Object o);

    /**
     * Removes all elements from this list.
     */

    public void clear();

    /**
     * Determines if this list contains the given object.
     *
     * @param o an object
     * @return true iff this list contains that object
     */

    public boolean contains(Object o);

    /**
     * Removes the first ocurrence of the given object from this list.
     * Returns false if the object was not on this list, true
     * otherwise.
     *
     * @param o an object
     * @return true iff that object was on this list
     */

    public boolean remove(Object o);

    /**
     * Returns an iterator positioned at the beginning of this list.
     *
     * @return an iterator positioned at the beginning of this list
     */

    public Iterator iterator();

    /**
     * Returns the number of items on this list.
     *
     * @return the size of this list
     */

    public int size();
}

List202.java

/**
 * A subset of the JCF List interface.
 *
 * @author Jim Glenn
 * @version 0.1 11/10/2004
 */

public interface List202 extends Collection202
{
    /**
     * Returns the object at the given position in this list.  The first
     * item on the list is at position 0.
     *
     * @param index a position in this list
     * @return the object at that position
     */

    public Object get(int index);
}

ArrayList202.java

import java.util.*;

/**
 * A list implemented using an array to hold the elements.
 *
 * @author Jim Glenn
 * @version 0.1 11/10/2004
 */

public class ArrayList202 implements List202
{
    /**
     * The array that holds the elements in this list.  The
     * first item in the list is at index 0 in this array.
     */

    private Object[] elements;
    
    /**
     * The number of items in this list.  Note that this is not necessarily
     * the same as the size of the <CODE>elements</CODE> array since
     * the locations in the array are not necessarily all used.
     */

    private int numElements;

    /**
     * Creates an empty list.
     */

    public ArrayList202()
    {
	clear();
    }

    /**
     * Returns the object at the given position in this list.  The first
     * item on the list is at position 0.
     *
     * @param index a position in this list
     * @return the object at that position
     */

    public Object get(int index)
    {
	return elements[index];
    }

    /**
     * Returns the number of items on this list.
     *
     * @return the size of this list
     */

    public int size()
    {
	return numElements;
    }

    /**
     * Removes all elements from this list.
     */

    public void clear()
    {
	numElements = 0;
	elements = new Object[1];
    }

    /**
     * Adds the given item o this list.  
     *
     * @param o the object to add
     * @return true
     */

    public boolean add(Object o)
    {
	if (numElements == elements.length)
	    {
		// array is full; resize

		Object[] bigger = new Object[numElements * 2];
		System.arraycopy(elements, 0, bigger, 0, numElements);
		elements = bigger;
	    }

	elements[numElements] = o;
	numElements++;

	return true;
    }

    /**
     * Determines if this list contains the given object.
     *
     * @param o an object
     * @return true iff this list contains that object
     */

    public boolean contains(Object o)
    {
	return (find(o) != -1);
    }

    /**
     * Returns the index of the first occurrence of the given object
     * on this list, or -1 if the item is not on this list.
     *
     * @param o an object
     * @return the index in this list of the first occurrence of that object
     */
    
    private int find(Object o)
    {
	int i = 0;
	while (i < numElements && !elements[i].equals(o))
	    i++;

	if (i < numElements)
	    return i;
	else
	    return -1;
    }

    /**
     * Removes the first ocurrence of the given object from this list.
     * Returns false if the object was not on this list, true
     * otherwise.
     *
     * @param o an object
     * @return true iff that object was on this list
     */

    public boolean remove(Object o)
    {
	// find where o is

	int removeIndex = find(o);

	if (removeIndex != -1)
	    {
		for (int copyTo = removeIndex; copyTo < numElements - 1; copyTo++)
		    elements[copyTo] = elements[copyTo + 1];
		numElements--;

		return true;
	    }

	return false;
    }

    /**
     * Returns an iterator positioned at the beginning of this list.
     *
     * @return an iterator positioned at the beginning of this list
     */

    public Iterator iterator()
    {
	return new ArrayList202Iterator();
    }

    /**
     * An iterator through this list.
     */

    private class ArrayList202Iterator implements Iterator
    {
	/**
	 * The current position in the list.
	 */

	private int index;

	/**
	 * Creates an iterator positioned at the beginning of the list.
	 */

	public ArrayList202Iterator()
	{
	    index = 0;
	}

	/**
	 * Determines if this iterator has reached the end of the list.
	 *
	 * @return true iff this iterator has not reached the end
	 */

	public boolean hasNext()
	{
	    return index < numElements;
	}

	/**
	 * Returns the next item in the list and advances this iterator to
	 * the next item.
	 *
	 * @return the next item in this iteration
	 */

	public Object next()
	{
	    index++;
	    return elements[index - 1];
	}

	/**
	 * Not supported.
	 *
	 * @throws UnsupportedOperationException
	 */

	public void remove()
	{
	    throw new UnsupportedOperationException();
	}
    }
}

LinkedList202.java

import java.util.*;

/**
 * A list implemented as a singly linked list.
 *
 * @author Jim Glenn
 * @version 0.1 11/10/2004
 */

public class LinkedList202 implements List202
{
    /**
     * The node containing the first item on this list, or
     * <CODE>null</CODE> if this list is empty.
     */

    private Node head;

    /**
     * The node containing the last item on this list, or
     * <CODE>null</CODE> if this list is empty.
     */

    private Node tail;

    /**
     * The number of items on this list.
     */

    private int numElements;

    /**
     * Creates an empty list.
     */

    public LinkedList202()
    {
	clear();
    }

    /**
     * Returns the object at the given position in this list.  The first
     * item on the list is at position 0.
     *
     * @param index a position in this list
     * @return the object at that position
     */

    public Object get(int index)
    {
	Node curr = head;

	for (int i = 0; i < index; i++)
	    curr = curr.next;

	return curr.data;
    }

    /**
     * Returns the number of items on this list.
     *
     * @return the size of this list
     */

    public int size()
    {
	return numElements;
    }

    /**
     * Removes all elements from this list.
     */

    public void clear()
    {
	numElements = 0;
	head = null;
	tail = null;
    }

    /**
     * Adds the given item o this list.  
     *
     * @param o the object to add
     * @return true
     */

    public boolean add(Object o)
    {
	if (tail == null)
	    {
		head = new Node(o, null);
		tail = head;
	    }
	else
	    {
		tail.next = new Node(o, null);
		tail = tail.next;
	    }

	numElements++;

	return true;
    }

    /**
     * Determines if this list contains the given object.
     *
     * @param o an object
     * @return true iff this list contains that object
     */

    public boolean contains(Object o)
    {
	return (find(o) != null);
    }

    /**
     * Returns the first node that contains the given item, or
     * <CODE>null</CODE> if there is no such node.
     *
     * @param o an object
     * @return the first node in this list that contains that item
     */

    private Node find(Object o)
    {
	Node curr = head;
	while (curr != null && !curr.data.equals(o))
	    curr = curr.next;

	return curr;
    }
    /**
     * Removes the first ocurrence of the given object from this list.
     * Returns false if the object was not on this list, true
     * otherwise.
     *
     * @param o an object
     * @return true iff that object was on this list
     */

    public boolean remove(Object o)
    {
        // there is a case this method does not handle correctly --
        // can you find and fix the problem?

	if (head.data.equals(o))
	    {
		if (tail == head)
		    clear();
		else
		    {
			head = head.next;
			numElements--;
		    }

		return true;
	    }
	else
	    {
		// find node before one containing o

		Node beforeO = head;
		while (beforeO.next != null && !beforeO.next.data.equals(o))
		    beforeO = beforeO.next;
	
		
		if (beforeO.next != null)
		    {
			if (beforeO.next == tail)
			    tail = beforeO;

			beforeO.next = beforeO.next.next;
			numElements--;

			return true;
		    }
		else
		    return false;
	    }
    }

    /**
     * Returns an iterator positioned at the beginning of this list.
     *
     * @return an iterator positioned at the beginning of this list
     */

    public Iterator iterator()
    {
	return new LinkedList202Iterator();
    }

    /**
     * An iterator through this list.
     */

    private class LinkedList202Iterator implements Iterator
    {
	/**
	 * The current node in this iterator.
	 */

	private Node current;

	/**
	 * Creates an iterator positioned at the beginning of the list.
	 */

	public LinkedList202Iterator()
	{
	    current = head;
	}

	/**
	 * Determines if this iterator has reached the end of the list.
	 *
	 * @return true iff this iterator has not reached the end
	 */

	public boolean hasNext()
	{
	    return (current != null);
	}

	/**
	 * Returns the next item in the list and advances this iterator to
	 * the next item.
	 *
	 * @return the next item in this iteration
	 */

	public Object next()
	{
	    Object result = current.data;
	    
	    current = current.next;

	    return result;
	}

	/**
	 * Not supported.
	 *
	 * @throws UnsupportedOperationException
	 */

	public void remove()
	{
	    throw new UnsupportedOperationException();
	}
    }

    /**
     * A node on this list.
     */

    private static class Node
    {
	private Object data;
	private Node next;

	private Node(Object d, Node n)
	{
	    data = d;
	    next = n;
	}
    }
}