linkedsimplelist.java

国外的数据结构与算法分析用书

package simple;

/**	An implementation of interface SimpleList using LinkedNodes.  Items can be 
	inserted and deleted at the front of the list only. */
public class LinkedSimpleList implements SimpleList
{
	/**	The first node of the list. */
	protected LinkedNode firstNode; 

	/**	Construct an empty list.
		Analysis: Time = O(1) */
	public LinkedSimpleList()
	{
		firstNode = null;
	}

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

	/**	Is the list full?
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	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 firstNode.item();
	}

	/**	Insert x as the first item of the list.
		Analysis: Time = O(1) */
	public void insertFirst(Object x)
	{
		LinkedNode newNode = new LinkedNode(x);
		newNode.setNextNode(firstNode);
		firstNode = newNode;
	}

	/**	String representation of the list.
		Analysis: Time = O(n), n = number of items in the list */
	public String toString()
	{
		if (!isEmpty())
			return firstNode.toString();
		else
			return new String();
	}

	/**	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");
		firstNode = firstNode.nextNode();
	}
}