simplelistextended.java

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

package simple;

public class SimpleListExtended extends LinkedSimpleList implements Cloneable
{
	/**	Returns the largest item in the list. 
		Analysis : Time = O(n), n = number of items in list */
	public Comparable max()
	{
		LinkedNode cur = firstNode;
		Comparable largest = (Comparable)cur.item;
		cur = cur.nextNode;
		while (cur != null)
		{
			if (largest.compareTo(cur.item) < 0) // found a new largest value
				largest = (Comparable) cur.item;
			cur = cur.nextNode;
		}
		return largest;
	}

	
	/**	The index of the first location of the current list that has an item equal to value. 
		Analysis : Time = O(n) worst case, where n = number of items in the list.  */
	public int findPos(Object value)
	{
		LinkedNode cur = firstNode;
		int index = 1;
		while (cur != null)
		{
			if (cur.item.equals(value))
				return index;
			cur = cur.nextNode;
			index++;
		}
		return 0;
	}

	/**	Insert newValue into the current list in the position just prior
		to the position that has an item equal to posValue.
		Analysis : Time = O(n) worst case, where n = the number of items in the list.  */
	public void insertBeforeValue(Object posValue, Object newValue)
	{
		LinkedNode cur, prev;
		cur = firstNode;
		prev = null;
		while ((cur != null) && !posValue.equals(cur.item))
		{
			prev = cur;
			cur = cur.nextNode;
		}
		if (cur != null)
		{
			LinkedNode newNode = new LinkedNode(newValue);
			newNode.setNextNode(cur);
			if (prev == null)
				firstNode = newNode;
			else
				prev.setNextNode(newNode);
		}
	}

	/**	A shallow clone of this list.
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e) 
		{
			/*	Should not occur:  this class implements Cloneable. */ 
			e.printStackTrace();
			return null;
		}
	}

	/**	Constructor for the list.
		Analysis: Time = O(1) */
	public SimpleListExtended()
	{
		super();
	}

	/**	Return a semi-deep clone of this list.
		Analysis: Time = O(count), count = number of items in the list */
	public SimpleListExtended listClone()
	{
		SimpleListExtended result = new SimpleListExtended();
		if (isEmpty())
			return result;
		else
		{
			LinkedNode cur = firstNode;
			result.insertFirst(cur.item());
			LinkedNode cloneLast = result.firstNode;
			cur = cur.nextNode();
			while (cur != null)
			{
				LinkedNode cloneNew = new LinkedNode(cur.item());
				cloneLast.setNextNode(cloneNew);
				cloneLast = cloneNew;
				cur = cur.nextNode();
			}
			return result;
		}
	}
}