bilinkedsimplelist.java

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

package simple;

/**	A version of LinkedSimpleListUos that uses BilinkedNodeUos
	for nodes so that it is possible to go backwards as well as forwards. */
public class BilinkedSimpleList extends LinkedSimpleList
{
	/**	Constructor for the class which creates an empty bilinked list
		Analysis : Time = O(1) */
	public BilinkedSimpleList()
	{
		super();
	}

	/**	Insert x as the first item of the list
		Analysis: Time = O(1) */
	public void insertFirst(Object x)
	{
		BilinkedNode newNode = new BilinkedNode(x);
		newNode.setNextNode(firstNode);
		if (firstNode!=null)
			((BilinkedNode)firstNode).setPreviousNode(newNode);
		firstNode = newNode;
	}
      
	/**	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");
		if (cur==firstNode)
			cur = null;
		firstNode = firstNode.nextNode();
		if (firstNode!=null)
			((BilinkedNode)firstNode).setPreviousNode(null);
	}

	/**	The node containing the current item */
	protected LinkedNode cur;

	/**	Is there a current item? 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return (cur!=null);
	}

	/**	The current item 
		Analysis: Time = O(1) 
		PRECONDITION:
			itemExists() */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist.");

		return cur.item();
	}

	/**	Move to x or else off the end of the list 
		Analysis: Time = O(n), n = size of the list */
	public void search (Object x)
	{ 
		goToLocation(x);
	}
 
	/**	Move to x, or if not found set cur to Void 
		Analysis: Time = O(n), n = size of the list */
	public void goToLocation(Object x)
	{
		cur = firstNode;
		while ((cur!=null) && (!x.equals(cur.item())))
			cur = cur.nextNode();
	}
}