public class List {
    int length;
    Node head;

    public List () {
	length = 0;
	head = null;
    }

    public boolean empty () {
	return head == null;
    }

    public void addNewFirstNode (Object obj) {
	head = new Node (obj, head);
    }

    public void addNewLastNode (Object obj) {
	if (head == null) {
	    head = new Node (obj, null);
	    return;
	}
	Node last;
	for (last = head; last.next != null; last = last.next) {
	    // traverse the list to find the last node
	}
	last.next = new Node (obj, null);
    }

    public Object removeFirstNode () {
	Object result = head.cargo;
	if (head != null) {
	    head = head.next;
	}
	return result;
    }

    // insertAfter: inserts the newNode into the list
    // immediately after pred.  precondition: pred must
    // be in the list
    public void insertAfter (Node newNode, Node pred) {
        newNode.next = pred.next;
        pred.next = newNode;
        length++;
    }

    // insertBefore: inserts the newNode into the list
    // immediately before successor.  precondition: successor must
    // be in the list.  warning: this method modifies the cargo
    // of both nodes!
    public void insertBefore (Node newNode, Node successor) {
        insertAfter (newNode, successor);
        Object cargo = newNode.cargo;
        newNode.cargo = successor.cargo;
        successor.cargo = cargo;
    }

    // print: print the list
    public void print () {
	Node node;

	System.out.print ("(");

	// start at the beginning of the list
	node = head;

	// traverse the list, printing each element
	while (node != null) {
	    System.out.print (node.cargo);
	    node = node.next;
	    if (node != null) {
		System.out.print (", ");
	    }
	}
	
	System.out.println (")");
    }

    public void printBackward () {
	System.out.print ("(");

	if (head != null) {
	    Node tail = head.next;
	    Node.printBackward (tail);
	    System.out.print (head);
	}
	System.out.println (")");
    }	
}