list.java

这个程序是为了更好的理解

// Fig. 20.3: List.java
// ListNode and List class definitions.
package com.deitel.jhtp5.ch20;

// class to represent one node in a list
class ListNode {

	// package access members; List can access these directly
	Object data;

	ListNode nextNode;

	// create a ListNode that refers to object
	ListNode(Object object) {
		this(object, null);
	}

	// create ListNode that refers to Object and to next ListNode
	ListNode(Object object, ListNode node) {
		data = object;
		nextNode = node;
	}

	// return reference to data in node
	Object getObject() {
		return data; // return Object in this node
	}

	// return reference to next node in list
	ListNode getNext() {
		return nextNode; // get next node
	}

} // end class ListNode

// class List definition
public class List {
	private ListNode firstNode;

	private ListNode lastNode;

	private String name; // string like "list" used in printing

	// construct empty List with "list" as the name
	public List() {
		this("list");
	}

	// construct an empty List with a name
	public List(String listName) {
		name = listName;
		firstNode = lastNode = null;
	}

	// insert Object at front of List
	public synchronized void insertAtFront(Object insertItem) {
		if (isEmpty()) // firstNode and lastNode refer to same object
			firstNode = lastNode = new ListNode(insertItem);

		else
			// firstNode refers to new node
			firstNode = new ListNode(insertItem, firstNode);
	}

	// insert Object at end of List
	public synchronized void insertAtBack(Object insertItem) {
		if (isEmpty()) // firstNode and lastNode refer to same Object
			firstNode = lastNode = new ListNode(insertItem);

		else
			// lastNode's nextNode refers to new node
			lastNode = lastNode.nextNode = new ListNode(insertItem);
	}

	
	//HomeWorks Beginning
	// insert Object at middle of list
	public synchronized void insertAtMiddle(int index, Object data) {
		int count = 1;
		int length;
		if (isEmpty())
			firstNode = lastNode = new ListNode(data);

		else {
			ListNode current = firstNode;
			while (current != lastNode) {
				current = current.nextNode;
				count += 1;
			}
			length = count + 1;
			if (index <= length - 1 && index >= 2) {
				ListNode current1 = firstNode;
				for (int i = 0; i < index - 2; i++) {
					current1 = current1.nextNode;
				}
				current1.nextNode = new ListNode(data, current1.nextNode);
			} else {
				throw new EmptyListException(name);
			}
		}
	}

	// remove by data
	public synchronized Object removeBydata(Object data)
			throws EmptyListException {
		if (isEmpty())
			throw new EmptyListException(name);
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else {
			ListNode current2 = firstNode;
			Object removedItem = data;
			while (current2 != lastNode) {
				Object checkDate = current2.nextNode.data;

				if (checkDate == data) {
					current2.nextNode = current2.nextNode.nextNode;
				}
				current2 = current2.nextNode;
			}

		}
		return data;

	}

	// remove by index
	public synchronized void removeByindex(int index) throws EmptyListException {
		int count = 1;
		int length;
		if (isEmpty())
			throw new EmptyListException(name);
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else {
			ListNode current3 = firstNode;
			while (current3 != lastNode) {
				current3 = current3.nextNode;
				count += 1;
			}
			length = count + 1;
			if (index <= length - 1 && index >= 2) {
				ListNode current4 = firstNode;
				for (int i = 0; i < index - 2; i++) {
					current4 = current4.nextNode;
				}
				Object removedItem = current4.nextNode.data;
				current4.nextNode = current4.nextNode.nextNode;
			} else {
				throw new EmptyListException(name);
			}
		}

	}//HomeWorks Over

	// remove first node from List
	public synchronized Object removeFromFront() throws EmptyListException {
		if (isEmpty()) // throw exception if List is empty
			throw new EmptyListException(name);

		Object removedItem = firstNode.data; // retrieve data being removed

		// update references firstNode and lastNode
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.nextNode;

		return removedItem; // return removed node data

	} // end method removeFromFront

	// remove last node from List
	public synchronized Object removeFromBack() throws EmptyListException {
		if (isEmpty()) // throw exception if List is empty
			throw new EmptyListException(name);

		Object removedItem = lastNode.data; // retrieve data being removed

		// update references firstNode and lastNode
		if (firstNode == lastNode)
			firstNode = lastNode = null;

		else { // locate new last node
			ListNode current = firstNode;

			// loop while current node does not refer to lastNode
			while (current.nextNode != lastNode)
				current = current.nextNode;

			lastNode = current; // current is new lastNode
			current.nextNode = null;
		}

		return removedItem; // return removed node data

	} // end method removeFromBack

	// determine whether list is empty
	public synchronized boolean isEmpty() {
		return firstNode == null; // return true if List is empty
	}

	// output List contents
	public synchronized void print() {
		if (isEmpty()) {
			System.out.println("Empty " + name);
			return;
		}

		System.out.print("The " + name + " is: ");
		ListNode current = firstNode;

		// while not at end of list, output current node's data
		while (current != null) {
			System.out.print(current.data.toString() + " ");
			current = current.nextNode;
		}

		System.out.println("\n");
	}

} // end class List

/*******************************************************************************
 * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and * Prentice Hall. All
 * Rights Reserved. * * DISCLAIMER: The authors and publisher of this book have
 * used their * best efforts in preparing the book. These efforts include the *
 * development, research, and testing of the theories and programs * to
 * determine their effectiveness. The authors and publisher make * no warranty
 * of any kind, expressed or implied, with regard to these * programs or to the
 * documentation contained in these books. The authors * and publisher shall not
 * be liable in any event for incidental or * consequential damages in
 * connection with, or arising out of, the * furnishing, performance, or use of
 * these programs. *
 ******************************************************************************/