Computer Science/61b/Homework/hw5/list/DListNode.java

This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.

Copyright 2006, 2007 Paul Borokhov. All rights reserved.

This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

The code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

/* DListNode.java */

package list;

/**
 *  A DListNode is a mutable node in a DList (doubly-linked list).
 **/

public class DListNode extends ListNode {
	
	/**
	 *  (inherited)  item references the item stored in the current node.
	 *  (inherited)  myList references the List that contains this node.
	 *  prev references the previous node in the DList.
	 *  next references the next node in the DList.
	 *
	 *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
	 **/
	
	protected DListNode prev;
	protected DListNode next;
	
	/**
	 *  DListNode() constructor.
	 *  @param i the item to store in the node.
	 *  @param l the list this node is in.
	 *  @param p the node previous to this node.
	 *  @param n the node following this node.
	 */
	DListNode(Object i, DList l, DListNode p, DListNode n) {
		item = i;
		myList = l;
		prev = p;
		next = n;
	}
	
	/**
	 *  isValidNode returns true if this node is valid; false otherwise.
	 *  An invalid node is represented by a `myList' field with the value null.
	 *  Sentinel nodes are invalid, and nodes that don't belong to a list are
	 *  also invalid.
	 *
	 *  @return true if this node is valid; false otherwise.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public boolean isValidNode() {
		return myList != null;
	}
	
	/**
	 *  next() returns the node following this node.  If this node is invalid,
	 *  throws an exception.
	 *
	 *  @return the node following this node.
	 *  @exception InvalidNodeException if this node is not valid.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public ListNode next() throws InvalidNodeException {
		if (!isValidNode()) {
			throw new InvalidNodeException("next() called on invalid node");
		}
		return next;
	}
	
	/**
	 *  prev() returns the node preceding this node.  If this node is invalid,
	 *  throws an exception.
	 *
	 *  @param node the node whose predecessor is sought.
	 *  @return the node preceding this node.
	 *  @exception InvalidNodeException if this node is not valid.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public ListNode prev() throws InvalidNodeException {
		if (!isValidNode()) {
			throw new InvalidNodeException("prev() called on invalid node");
		}
		return prev;
	}
	
	/**
	 *  insertAfter() inserts an item immediately following this node.  If this
	 *  node is invalid, throws an exception.
	 *
	 *  @param item the item to be inserted.
	 *  @exception InvalidNodeException if this node is not valid.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public void insertAfter(Object item) throws InvalidNodeException {
		if (!isValidNode()) {
			throw new InvalidNodeException("insertAfter() called on invalid node");
		}
		DListNode insertion = ((DList) myList).newNode(item, (DList) myList, this, this.next);
		this.next.prev = insertion;
		this.next = insertion;
		myList.size++;
	}
	
	/**
	 *  insertBefore() inserts an item immediately preceding this node.  If this
	 *  node is invalid, throws an exception.
	 *
	 *  @param item the item to be inserted.
	 *  @exception InvalidNodeException if this node is not valid.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public void insertBefore(Object item) throws InvalidNodeException {
		if (!isValidNode()) {
			throw new InvalidNodeException("insertBefore() called on invalid node");
		}
		DListNode insertion = ((DList) myList).newNode(item, (DList) myList, this.prev, this);
		this.prev.next = insertion;
		this.prev = insertion;
		myList.size++;
	}
	
	/**
	 *  remove() removes this node from its DList.  If this node is invalid,
	 *  throws an exception.
	 *
	 *  @exception InvalidNodeException if this node is not valid.
	 *
	 *  Performance:  runs in O(1) time.
	 */
	public void remove() throws InvalidNodeException {
		if (!isValidNode()) {
			throw new InvalidNodeException("remove() called on invalid node");
		}
		// Your solution here.  Will look something like your Homework 4 solution,
		//   but changes are necessary.  For instance, there is no need to check if
		//   "this" is null.  Remember that this node's "myList" field tells you
		//   what DList it's in.
		this.prev.next = this.next;
		this.next.prev = this.prev;
		myList.size--;
		// Make this node an invalid node, so it cannot be used to corrupt myList.
		myList = null;
		// Set other references to null to improve garbage collection.
		next = null;
		prev = null;
	}
}