linkedsimplelistuos.java

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

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

import dslib.exception.*;

/**	A SimpleListUos class implemented using LinkedNodeUos.  Items can be 
	inserted and deleted at the front of the list only. */
public class LinkedSimpleListUos implements SimpleListUos
{
	/**	The first node of the list. */
	protected LinkedNodeUos firstNode;

	/**	Construct an empty list. <br>
		Analysis: Time = O(1) */
	public LinkedSimpleListUos()
	{
		firstNode = null;
	}
	
	/**	Create a new node that is appropriate to this list.  This routine should be
		overridden for classes that extend this class and need a specialized node,
		i.e., a descendant of LinkedNodeUos. <br>
		Analysis: Time = O(1) */
	protected LinkedNodeUos createNewNode(Object item)
	{
		return new LinkedNodeUos(item);
	}

	/**	Return first node. <br>
		Analysis: Time = O(1) */
	protected LinkedNodeUos firstNode()
	{
		return firstNode;
	}

	/**	Set firstNode to newFirstNode. <br> 
		Analysis: Time = O(1) 
		@param newFirstNode new value for firstNode */
	protected void setFirstNode(LinkedNodeUos newFirstNode)
	{
		firstNode = newFirstNode;
	}

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

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

	/**	Insert x as the first element of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the front of the list */
	public void insertFirst(Object x) 
	{
		LinkedNodeUos cur = createNewNode(x);
		cur.setNextNode(firstNode);
		setFirstNode(cur);
	}
  
	/**	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 on an empty list.");
		
		setFirstNode(firstNode.nextNode());
	}

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

	/**	Return a semi deep clone of this list. <br>
		Analysis: Time = O(count), count = number of items in the list */
	public SimpleListUos listClone()
	{
		LinkedSimpleListUos tempClone = null;
		try
		{  
			tempClone = (LinkedSimpleListUos)super.clone();
			if (isEmpty())
				return tempClone;
			LinkedNodeUos cur = firstNode;
			tempClone.insertFirst(cur.item());
			LinkedNodeUos cloneLast = tempClone.firstNode;
			cur = cur.nextNode();
			while (cur!=null)
			{
				LinkedNodeUos cloneNew = (LinkedNodeUos)cur.clone();
				cloneLast.setNextNode(cloneNew);
				cloneLast = cloneNew;
				cur = cur.nextNode();
			}
		} catch (CloneNotSupportedException e)
		{
			// Should not occur: this is a ContainerUos, which implements Cloneable
			e.printStackTrace();
		}
		return tempClone;
	}

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

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

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			// Should not occur: this is a ContainerUos, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}
}