// make this list generic
public class DoublyLinkedList<ValueType> {
	// member variables
	private Node head;
	private Node tail;
	private int size;

	// constructor
	public DoublyLinkedList() {
		// create sentinel nodes: head, tail
		head = new Node(null, null, null);
		tail = new Node(null, null, null);

		// link together
		head.setNext(tail);
		tail.setPrev(head);

		// set size to zero nodes
		size = 0;
	}

	// insertAtFront method
	public void insertAtFront(ValueType value) {
		insertBetween(value, head, head.getNext());
	}

	// private helper method to insert between two nodes
	private void insertBetween(ValueType value, Node predecessor, Node successor) {
		// which nodes need to be update?
		// predecessor.next must point the new node
		// new node's prev must point to predecessor
		// new node's next must point to successor
		// successor.prev must point to the new node

		// first, create new node
		Node newNode = new Node(value, predecessor, successor);

		// update predecessor
		predecessor.setNext(newNode);

		// update successor
		successor.setPrev(newNode);

		// since we added a new node, increase the size
		size++;
	}

	public void remove(ValueType character) {
		if (size == 0) {
			// do nothing
		}
		// checks for size of 1 and makes sure the character entered is in the list.
		else if (size == 1) {
			if (character.equals(head.getValue())) {
				head.setNext(null);
				size--;
			}
		}
		// Check if the size is greater than 1 but its the first element of the list and
		// will remove it.
		else if (character.equals(head.getNext().getValue())) {
			head.setNext(head.getNext().getNext());
			head.getNext().getNext().setPrev(head);
			size--;

		}
		// verifies and removes the rest of the specified values from the list.
		else {
				Node temp = head.getNext();
				if (character.equals(head.getNext().getValue())) {
				for (; temp.getValue() != character; temp = temp.getNext()) {
					System.out.println(temp);
				}
				temp.getPrev().setNext(temp.getNext());
				temp.getNext().setPrev(temp.getPrev());
				size--;
			}
		}
	}

	// size method
	public int size() {
		return size;
	}

	// toString method
	public String toString() {
		// string to return
		String ret = "";

		// iterate through values, adding each to the string
		for (Node temp = head.getNext(); temp != tail; temp = temp.getNext()) {
			ret += (temp.getValue() + " ");
		}

		// return constructed string
		return ret;
	}

	// internal node class
	private class Node {
		private ValueType value;
		private Node next;
		private Node prev;

		public Node(ValueType value, Node prev, Node next) {
			this.value = value;
			this.next = next;
			this.prev = prev;
		}

		public ValueType getValue() {
			return value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node n) {
			next = n;
		}

		public Node getPrev() {
			return prev;
		}

		public void setPrev(Node p) {
			prev = p;
		}

		public String toString() {
			return "" + value;
		}
	}
}