Computer Science/61b/Homework/hw4/list/DList.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

/* DList.java */

package list;

/**
*  A DList is a mutable doubly-linked list ADT.  Its implementation is
 *  circularly-linked and employs a sentinel (dummy) node at the head
 *  of the list.
 *
 *  DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
 */

public class DList {
	
	/**
	 *  head references the sentinel node.
	 *  size is the number of items in the list.  (The sentinel node does not
	 *       store an item.)
	 *
	 *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
	 */
	
	protected DListNode head;
	protected int size;
	
	/* DList invariants:
	 *  1)  head != null.
	 *  2)  For any DListNode x in a DList, x.next != null.
	 *  3)  For any DListNode x in a DList, x.prev != null.
	 *  4)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
	 *  5)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
	 *  6)  size is the number of DListNodes, NOT COUNTING the sentinel,
	 *      that can be accessed from the sentinel (head) by a sequence of
	 *      "next" references.
	 */
	
	/**
	 *  newNode() calls the DListNode constructor.  Use this class to allocate
	 *  new DListNodes rather than calling the DListNode constructor directly.
	 *  That way, only this method needs to be overridden if a subclass of DList
	 *  wants to use a different kind of node.
	 *  @param item the item to store in the node.
	 *  @param prev the node previous to this node.
	 *  @param next the node following this node.
	 */
	protected DListNode newNode(Object item, DListNode prev, DListNode next) {
		return new DListNode(item, prev, next);
	}
	
	/**
	 *  DList() constructor for an empty DList.
	 */
	public DList() {
		size = 0;
		head = newNode(null, null, null);
		head.next = head;
		head.prev = head;
	}
	
	/**
	 *  isEmpty() returns true if this DList is empty, false otherwise.
	 *  @return true if this DList is empty, false otherwise. 
	 *  Performance:  runs in O(1) time.
	 */
	public boolean isEmpty() {
		return size == 0;
	}
	
	/** 
	 *  length() returns the length of this DList. 
	 *  @return the length of this DList.
	 *  Performance:  runs in O(1) time.
	 */
	public int length() {
		return size;
	}
	
	/**
	 *  insertFront() inserts an item at the front of this DList.
	 *  @param item is the item to be inserted.
	 *  Performance:  runs in O(1) time.
	 */
	public void insertFront(Object item) {
		DListNode node = newNode(item, head, head.next);
		head.next.prev = node;
		head.next = node;
		size++;
	}
	
	/**
	 *  insertBack() inserts an item at the back of this DList.
	 *  @param item is the item to be inserted.
	 *  Performance:  runs in O(1) time.
	 */
	public void insertBack(Object item) {
		DListNode node = newNode(item, head.prev, head);
		head.prev.next = node;
		head.prev = node;
		size++;
	}
	
	/**
	 *  front() returns the node at the front of this DList.  If the DList is
	 *  empty, return null.
	 *
	 *  Do NOT return the sentinel under any circumstances!
	 *
	 *  @return the node at the front of this DList.
	 *  Performance:  runs in O(1) time.
	 */
	public DListNode front() {
		if (size == 0) { return null;
		} else { return head.next; }
	}
	
	/**
	 *  back() returns the node at the back of this DList.  If the DList is
	 *  empty, return null.
	 *
	 *  Do NOT return the sentinel under any circumstances!
	 *
	 *  @return the node at the back of this DList.
	 *  Performance:  runs in O(1) time.
	 */
	public DListNode back() {
		if (size == 0) { return null;
		} else { return head.prev; }
	}

	/**
	 *  next() returns the node following "node" in this DList.  If "node" is
	 *  null, or "node" is the last node in this DList, return null.
	 *
	 *  Do NOT return the sentinel under any circumstances!
	 *
	 *  @param node the node whose successor is sought.
	 *  @return the node following "node".
	 *  Performance:  runs in O(1) time.
	 */
	public DListNode next(DListNode node) {
		if (node==null || node.next == head) { return null; }
		else { return node.next; }
	}
	
	/**
	 *  prev() returns the node prior to "node" in this DList.  If "node" is
	 *  null, or "node" is the first node in this DList, return null.
	 *
	 *  Do NOT return the sentinel under any circumstances!
	 *
	 *  @param node the node whose predecessor is sought.
	 *  @return the node prior to "node".
	 *  Performance:  runs in O(1) time.
	 */
	public DListNode prev(DListNode node) {
		if (node==null || node.prev == head) { return null; }
		else { return node.prev; }
	}
	
	/**
	 *  insertAfter() inserts an item in this DList immediately following "node".
	 *  If "node" is null, do nothing.
	 *  @param item the item to be inserted.
	 *  @param node the node to insert the item after.
	 *  Performance:  runs in O(1) time.
	 */
	public void insertAfter(Object item, DListNode node) {
		if (node != null) {
			DListNode insertion = newNode(item, node, node.next);
			node.next.prev = insertion;
			node.next = insertion;
			size++;
		}
	}
	
	/**
	 *  insertBefore() inserts an item in this DList immediately before "node".
	 *  If "node" is null, do nothing.
	 *  @param item the item to be inserted.
	 *  @param node the node to insert the item before.
	 *  Performance:  runs in O(1) time.
	 */
	public void insertBefore(Object item, DListNode node) {
		if (node != null) {
			DListNode insertion = newNode(item, node.prev, node);
			node.prev.next = insertion;
			node.prev = insertion;
			size++;
		}
	}
	
	/**
	 *  remove() removes "node" from this DList.  If "node" is null, do nothing.
	 *  Performance:  runs in O(1) time.
	 */
	public void remove(DListNode node) {
		if (node != null) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
			// not really necessary, but just to be safe fully disconnect all pointers
			node.next = null;
			node.prev = null;
			size--;
		}
	}
	
	/**
	 *  toString() returns a String representation of this DList.
	 *
	 *  DO NOT CHANGE THIS METHOD.
	 *
	 *  @return a String representation of this DList.
	 *  Performance:  runs in O(n) time, where n is the length of the list.
	 */
	public String toString() {
		String result = "[  ";
		DListNode current = head.next;
		while (current != head) {
			result = result + current.item + "  ";
			current = current.next;
		}
		return result + "]";
	}
}