import java.util.*;

/** Abstract data type for a <em>generic</em>, dynamically growing list. The <tt>Iterator</tt>
  * returned by <tt>iterator()</tt> must support the <tt>remove()</tt> method.
  * @author Jacob Whitehill
 */
public interface List12<T> extends Iterable<T> {
	/** Adds the specified object <tt>o</tt>, which may be null, to the
	  * front of the list (i.e., at the head).
	  * @param o the object to add to the list. */
	void addToFront (T o);
	
	/** Adds the specified object <tt>o</tt>, which may be null, to the
	  * back of the list (i.e., at the tail).
	  * @param o the object to add to the list. */
	void addToBack (T o);
	
	/** Equivalent to addToBack.
	  * @param o the object to add to the list. */
	void add (T o);

	/** Removes and returns the element at the front of the list.
	  * @return the element that was removed from the front of the list.
	  * @throws NoSuchElementException if the list was empty.
	  */
	T removeFront () throws NoSuchElementException;

	/** Removes and returns the element at the back of the list.
	  * @return the element that was removed from the back of the list.
	  * @throws NoSuchElementException if the list was empty.
	  */
	T removeBack () throws NoSuchElementException;

	/** Removes the first occurrence (ordered from front to
	  * back, i.e., head to tail of the list) of the specified
	  * object <tt>o</tt> from the list, if it exists. <tt>o</tt> may be null; if
	  * it is, then this method removes the first element in
	  * the list that is null. Otherwise, this method removes
	  * the first element in the list that <tt>equals()</tt>
	  * <tt>o</tt> (if any such element exists).
	  * @return <tt>true</tt> if an element was removed, or
	  * <tt>false</tt> otherwise.
	  */
	boolean remove (T o);

	/** Removes all elements from the list. */
	void clear ();

	/** Returns the element stored at location <tt>index</tt>, where index 0
	  * is the element stored at the head of the list and <tt>size()-1</tt> is
	  * the index of the element at the tail of the list.
	  * @param index the index of the element to retrieve.
	  * @throws IndexOutOfBoundsException if the index is invalid.
	  * @return the object at the specified index.
	  */
	T get (int index) throws IndexOutOfBoundsException;

	/** Returns the number of elements (null or otherwise) currently stored in the
	  * list.
	  * @return the number of elements stored in the list.
	  */
	int size ();

	/** Returns whether the specified object <tt>o</tt> is contained in the list. <tt>o</tt>
	  * may be null.
	  * @param o the object whose presence in the list should be determined.
	  * @return whether <tt>o</tt> is contained in the list.
	  */
	boolean contains (T o);
}