public class List {
    Node head;
    int length;

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

    public List (Node head, int length) {
	this.head = head;
	this.length = length;
    }

    // addNewFirstNode: create a new node with the given cargo
    // and add it at the beginning of the list
    public void addNewFirstNode (int cargo) {
	head = new Node (cargo, head);
	length++;
    }

    // removeFirstNode: remove and return the first node
    // in the list, or null if the list is empty
    public Node removeFirstNode () {
	Node node = head;
	if (node != null) {
	    head = head.next;
	    length--;
	}
	return node;
    }

    // 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);
	int cargo = newNode.cargo;
	newNode.cargo = successor.cargo;
	successor.cargo = cargo;
    }

    // copy: returns a copy of the List object and all the nodes
    // that follow
    public List copy () {
	Node nodes = Node.copy (head);
	return new List (nodes, length);
    }

    // reverse: returns a new list that contains new nodes with the
    // cargo from the original list in reverse order.
    public List reverse () {
	List result = new List ();
	for (Node node = head; node != null; node = node.next) {
	    result.addNewFirstNode (node.cargo);
	}
	return result;
    }

    // appendNode: tack the given node onto the end of the list
    // warning: it is the caller's responsibility to insure that
    // newNode.next == null
    public void appendNode (Node newNode) {
	Node end = Node.findEnd (head);
	if (end == null) {
	    head = newNode;
	} else {
	    end.next = newNode;
	}
	length++;
    }

    // appendList: copy the nodes from the given list and add
    // them at the end of the list
    public void appendList (List list) {
	appendNode (Node.copy (list.head));
	length += list.length - 1;           // KLUDGE !!!!
    }

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

	System.out.print (length + " (");

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

	// traverse the list, printing each element
	while (node != null) {
	    System.out.print (node);
	    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 (")");
    }	
}