Computer Science/61b/Homework/hw4/list/DList.java

{{code}]

/* 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 + "]";
	}
}