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);
}

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)
    {
	if (head == null)
	    return false;
	else 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;
	}
    }
}