public class DoubleNode {
    private int data;
    private DoubleNode next;
    private DoubleNode prev;

    public DoubleNode(int d) {
	data = d;
    }

    public int getData() {
	return data;
    }

    // return the next node
    public DoubleNode getNext() {
	return next;
    }

    // set the next node 
    public void setNext(DoubleNode n) {
	next = n;
    }

    // return the previous node
    public DoubleNode getPrev() {
	return prev;
    }
    
    // set the previous node
    public void setPrev(DoubleNode n) {
	prev = n;
    }
}

// Doubly linked list
// Written by Elena Machkasova, Oct. 6 2004 
// Modified Feb. 23 2005

public class DoubleLinkedList {
    private DoubleNode first;
    private DoubleNode last;

    public DoubleLinkedList() {
	// sets 'first' and 'last' to null
    }

    public boolean isEmpty() {
	return (first == null);
    }

    public DoubleNode getFirst() {
	return first;
    }

    public DoubleNode getLast() {
	return last;
    }

    // works for non-null parameters only
    // if a null parameter is passed, it will print error message and exit
    public void addFront(DoubleNode n) {
	if (n == null) {
	    System.out.println("addFront: received a null parameter");
	    System.exit(0);
	}
	
	n.setNext(first);
	
	// check if this is the only element on the list
	// if not, set the 'prev' of the first
	// if it is, set 'last'
	if (first != null) {
	    first.setPrev(n);
	} else {
	    last = n;
	}
	first = n;
    }

    // works for non-null parameters only
    // if a null parameter is passed, it will print error message and exit    
    public void addBack(DoubleNode n) {
	if (n == null) {
	    System.out.println("addBack: received a null parameter");
	    System.exit(0);
	}
	
	n.setPrev(last);

	// if this is not the only node, reset the reference
	// from the previous node
	// Otherwise reset first
	if (last != null) {
	    last.setNext(n);
	} else {
	    first = n;
	}
	last = n;
    }

    // removes the element. If there is no element to remove,
    // prints an error message and exits
    public void removeFront() {
	if (first == null) {
	    System.out.println("removeFront: can't remove from an empty list");
	    System.exit(0);
	}

	// if there is only one element
	if (first == last) {
	    first = null;
	    last = null;
	} else {
	    // the second-to-first is now first:
	    first.getNext().setPrev(null);
	    first = first.getNext();
	}
    }
    
    public void removeBack() {
	if (last == null) {
	    System.out.println("removeBack: can't remove from an empty list");
	    System.exit(0);
	}

	// if there is only one element
	if (first == last) {
	    first = null;
	    last = null;
	} else {
	    // the second-to-first is now first:
	    last.getPrev().setNext(null);
	    last = last.getPrev();
	}
    }
}

public class TestDoubleLinked {
    public static void main(String [] args) {
	DoubleLinkedList dl = new DoubleLinkedList();
	DoubleNode dn1 = new DoubleNode(1);
	DoubleNode dn2 = new DoubleNode(2);
	DoubleNode dn3 = new DoubleNode(3);
	DoubleNode dn4 = new DoubleNode(4);
	DoubleNode dn5 = new DoubleNode(5);
	DoubleNode dn6 = new DoubleNode(6);

	dl.addFront(dn1);
	dl.addBack(dn2);
	dl.addFront(dn3);
	dl.addBack(dn4);
	dl.removeFront();
	dl.addFront(dn5);
	dl.removeBack();
	dl.addBack(dn6);

	System.out.println("Printing forward:");
	DoubleNode dn = dl.getFirst();
	while(dn != null) {
	    System.out.println(dn.getData());
	    dn = dn.getNext();
	}

	System.out.println("Printing backward:");
	dn = dl.getLast();
	while(dn != null) {
	    System.out.println(dn.getData());
	    dn = dn.getPrev();
	}
    }
}