arrayedsimplelist.java

来自「国外的数据结构与算法分析用书」· Java 代码 · 共 100 行

package simple;

/**	An arrayed implementation of interface SimpleList.  It has methods to manipulate the 
	item at the front of the list and to test for the list being empty or full.  It 
	also includes an instance variable to store the number of items in the list.  */	
public class ArrayedSimpleList implements SimpleList
{
	/**	Internal representation for this list, where the first 
		item is stored in location count - 1, and last in location 0. */
	protected Object[ ] rep;

	/**	The number of items in the list. */
	protected int count; 

	/**	Construct a new list with the specified length.
		Analysis: Time = O(length)
		PRECONDITION:
			length >= 0 */
	public ArrayedSimpleList(int length)
	{
		if (length < 0)
			throw new InvalidArgumentUosException("Cannot create a "
				+ " list with a negative capacity.");
		rep = new Object[length];
		count = 0;
	}

	/**	The number of items in the list.
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	The maximum number of items that can be in the list.
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}

	/**	Is the list empty?
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return (count == 0);
	}

	/**	Is the list full?
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return (count == capacity());
	}
	
	/**	Insert x as the first item of the list.
		Analysis: Time = O(1)
		PRECONDITION:
			 !isFull() */
	public void insertFirst(Object x) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full list");
		rep[count] = x;
		count++;
	}

	/**	The first item in the list.
		Analysis: Time = O(1)
		PRECONDITION:
			 !isEmpty() */
	public Object firstItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot obtain an item from an empty list");
		return rep[count - 1];
	}

	/**	Delete the first item from the list.
		Analysis: Time = O(1)
		PRECONDITION:
			 !isEmpty() */
	public void deleteFirst() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty list");
		count--;
	}

	/**	String representation of the list.
		Analysis: Time = O(count) */
	public String toString()
	{
		String result = new String();
		for (int i = count - 1; i >= 0; i--)
			result = result + rep[i] + "  ";      
		return result;
	}
}