public class IntegerLinkedListWithTail implements IntegerList {
    
    private int numElements;
    private Node head;
	private Node tail;
    
    public IntegerLinkedListWithTail() {
        head = null;
		tail = null;
        numElements = 0;
    }
    
    public void addFront (int val) {
        Node n = new Node(val);
		if (tail == null) {
			tail = n;
		} else {
			n.next = head;
		}
		head = n;
		numElements++;
    }
    
    public void addBack (int val) { 
		Node n = new Node(val);
		if (head == null) {
			head = n;
        } else {
			tail.next = n;
		}
		tail = n;
		numElements++;
    }
	
    public int size (){
        return numElements;
    }

    public int get (int position) {
		Node cur = head;
		for (int i = 0; i < position; i++) {
			cur = cur.next;
		}
        return cur.getValue();
    }
	
	/* Parameters: (int) position - place to insert
	 *             (int) val - value to insert
	 * Purpose:  insert an item into the list at the given position
	 * Returns:  nothing
	 * Precondition: 0 <= position <= list.size()
	 * Example: Given a list with items [ 8 1 4 5 2 ]
	 *   		After calling insertAt(2, 9) the
	 *          contents of the list:   [ 8 1 9 4 5 2 ]
	 */
	public void insertAt (int position, int val) {
		if (position == 0) {
			addFront(val);
		} else if (position == numElements) {
			addBack(val);
		} else {
			Node cur = head;
			for (int i = 0; i < position; i++) {
				cur = cur.next;
			}
			// now we want to insert right infront of cur
			Node n = new Node(val);
			n.next = cur.next;
			cur.next.prev = n;
			n.prev = cur;
			cur.next = n;
		}			
	}
    
    /* Parameters: nothing
     * Purpose: create a string representation of list
     * Returns: (String) the string representation
     */
    public String toString() {
        String s = "";
		Node cur = head;
		while (cur != null) {
			s += cur.getValue() + " ";
			cur = cur.next;
		}
        return s;
    }
    
}