public class LinkedList {
    Node head;
    int length;

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

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

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

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

    // set: set the cargo of the element indicated by index.
    // if the index is out of bounds, do nothing.
    public void set (int index, int cargo) {
	if (index<0 || index>=length) return;
	Node node = head;
	for (int i=0; i<index; i++) {
	    node = node.next;
	}
	node.cargo = cargo;
    }

    // add: put a new node at the position indicated by index.
    // if the index is out of bounds, do nothing.
    public void add (int index, int cargo) {
	if (index<0 || index>length) return;
	if (index == 0) {
	    addFirst (cargo);
	    return;
	}
	Node node = head;
	for (int i=0; i<index-1; i++) {
	    node = node.next;
	}
	node.next = new Node (cargo, node.next);
	length++;
    }

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


    // reverse: modifes the current list so that it contains
    // all the same elements in the opposite order
    public void reverse () {
	LinkedList result = new LinkedList ();
	for (Node node = head; node != null; node = node.next) {
	    result.addFirst (node.cargo);
	}
	head = result.head;
    }

    // addLast: make a new node with the given cargo and append
    // it to the list
    public void addLast (int cargo) {
	Node last = new Node (cargo, null);
	appendNode (last);
	length++;
    }

    // append: copy the nodes from the given list and add
    // them at the end of the list
    public void append (LinkedList list) {
	Node copy = Node.copy (list.head);
	appendNode (copy);
	length += list.length;
    }

    // appendNode: tack the given node onto the end of the list
    // warning: does not maintain the length invariant!!!
    // warning: does not maintain the null terminator!!!
    private void appendNode (Node newNode) {
	Node end = Node.findEnd (head);
	if (end == null) {
	    head = newNode;
	} else {
	    end.next = newNode;
	}
    }

    // 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 (")");
    }
}