linkedlastlistuos.java

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

/* LinkedLastListUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.list;

import dslib.exception.*;

/**	A LinkedBasicListUos which allows insertion at the end and 
	setting the last item.  It includes a linked iterator to move through 
	the list of nodes. */
public class LinkedLastListUos extends LinkedBasicListUos implements LastListUos
{
	/**	Last node of the list. */
	protected LinkedNodeUos lastNode;
	
	/**	Construct an empty list. <br>
		Analysis: Time = O(1) */
	public LinkedLastListUos()
	{
		super();
		lastNode = null;
	}

	/**	Set lastNode to newLastNode. <br>
		Analysis: Time = O(1) 
		@param newLastNode node to be set as the last node*/
	protected void setLastNode(LinkedNodeUos newLastNode)
	{
		lastNode = newLastNode;
	}

	/**	Return the last node. <br>
		Analysis: Time = O(1) */
	public LinkedNodeUos lastNode()
	{
		return lastNode;
	}

	/**	The last item of the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()	 
		</ul> */
	public Object lastItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return last item since list is empty.");
	
		return lastNode.item();
	}

	/**	Set the last item of the list to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul>
		@param x new item replace the last item */
	public void setLastItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set last item since a last node does not exist, that is, the list is empty.");
		
		lastNode.setItem(x);
	}

	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at front of the list */
	public void insertFirst(Object x) 
	{
		super.insertFirst(x);
		if (lastNode == null) 
			lastNode = firstNode;
	}

	/**	Delete the first item from the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteFirst() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot perform deletion since list is empty.");
		
		super.deleteFirst();
		if (firstNode == null) 
			lastNode = null;
	}

	/**	Insert x as the last item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the end of the list */
	public void insertLast(Object x)
	{
		if (isEmpty()) 
			insertFirst(x);
		else
		{
			LinkedNodeUos temp = createNewNode(x);
			lastNode.setNextNode(temp);
			lastNode = temp;
		}
	}

	/**	Return a clone of this list. 
		Analysis: Time = O(count), count = number of items in the list */
	public SimpleListUos listClone()
	{
		LinkedLastListUos result = (LinkedLastListUos)this.clone();
		result.wipeOut();
		if (isEmpty())  
			return result;
		else
		{
			LinkedNodeUos cur = firstNode;
			while (cur != null)
			{ 
				result.insertLast(cur.item());
				cur = cur.nextNode();
			}
			return result;
		}
	}

	/**	Remove all items from the list. 
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		super.wipeOut();
		lastNode = null;
	}
}