public class AList < T > implements ListInterface < T >,
                                             java.io.Serializable
{
    private T [] list; // array of list entries
    private int length; // current number of entries in list
    private static final int MAX_SIZE = 50; // max length of list

    public AList ()
    {
        this (MAX_SIZE); // call next constructor
    } // end default constructor


    public AList (int maxSize)
    {
        length = 0;
        list = (T []) new Object [maxSize]; // necessary cast to generic type
    } // end constructor

    public boolean add (T newEntry)
    {
        if(isFull())
        {
          return false;
        }
        int i = 0;
        while(list[i] != null && i < list.length)
        {
          i++;
        }
        list[i] = newEntry;
        length++;
        return true;
    } // end add


    public boolean add (int newPosition, T newEntry)
    {
        if(isFull() || newPosition < 1 || newPosition > getLength())//list.length)
        {
            return false;
        }
        makeRoom(newPosition);
        list[newPosition-1] = newEntry;
        length++;
        return true;
    } // end add

    public T remove (int givenPosition)
    {
        T result = null; // return value
        if(isEmpty() || givenPosition < 1 || givenPosition > getLength())
        {
          return null;
        }
        result = list[givenPosition-1];
        removeGap(givenPosition);   
        length--;
        return result; // return reference to removed entry, or
        // null if either list is empty or givenPosition
        // is invalid
    } // end remove


    public void clear ()
    {
        length = 0;
    } // end clear


    public boolean replace (int givenPosition, T newEntry)
    {
        if(isEmpty() || givenPosition < 1 || givenPosition > getLength())
        {
          return false; 
        }
        list[givenPosition-1] = newEntry;
        return true;
    } // end replace


    public T getEntry (int givenPosition)
    {
        if(isEmpty() || givenPosition < 1 || givenPosition > getLength())
        {
          return null; 
        }
        return list[givenPosition-1];
    } // end getEntry


    public boolean contains (T anEntry)
    {
        for(int i = 0; i < getLength()-1; i++)
        {
          if(list[i].equals(anEntry))
             return true;
        }
        return false;
    } // end contains


    public int getLength ()
    {
        return length;
    } // end getLength


    public boolean isEmpty ()
    {
        if(length == 0)
        {
          return true;
        }
        return false;
    } // end isEmpty


    public boolean isFull ()
    {
        if(list.length == getLength())//list[list.length-1] != null)
        {
          return true;
        }
        return false;
    } // end isFull


    public void display ()
    {
        for (int index = 0 ; index < length ; index++)
            System.out.println (list [index]);
    } // end display

    public void reverse ()
    {
        T[] temp = (T []) new Object [list.length];
        for(int i = 1; i < list.length; i++)
        {
          temp[i] = list[list.length-i];
        }
        list = temp;
    }
    
    
    /** Task: Makes room for a new entry at newPosition.
    *Precondition:1<=newPosition <= length+1;
    *lengthislistslength before addition. */
    private void makeRoom (int newPosition)
    {
        assert (newPosition >= 1) && (newPosition <= length + 1);
        int newIndex = newPosition - 1;
        int lastIndex = length - 1;
        // move each entry to next higher index, starting at end of
        // list and continuing until the entry at newIndex is moved
        for (int index = lastIndex ; index >= newIndex ; index--)
            list [index + 1] = list [index];
    } // end makeRoom


    /** Task: Shifts entries that are beyond the entry to be removed
    *tothenextlower position.
    *Precondition:1<=givenPosition < length;
    *lengthislistslength before removal. */
    private void removeGap (int givenPosition)
    {
        assert (givenPosition >= 1) && (givenPosition < length);
        int removedIndex = givenPosition - 1;
        int lastIndex = length - 1;
        for (int index = removedIndex ; index < lastIndex ; index++)
            list [index] = list [index + 1];
    } // end removeGap
    
} // end AList