import java.util.NoSuchElementException;

// below are several versions of a linked list, incrementally building up

// version 1, only state is a front node


public class MyLinkedList { // implements List or MyList or extends MyAbstract list...
    private LinkedNode front;
	private LinkedNode tail;

	public MyLinkedList() {
		clear();
	}

	public void clear() {
		front = null;
	}

    public int size() {
		int c = 0;
		LinkedNode current = front; // need to modify a temporary variable, i.e. front=front.next will change the list
		while(current != null) {
			c++;
			current = current.next;
		}
		return c;
    }

    public void addFront(Object o) {
		front = new LinkedNode(o,front);
	}
}

// the previous list has a slow size() because it needs to walk through each node.
// instead, let's remember how large the list is with a variable and update the
// variable.

public class MyLinkedList { // implements List or MyList or extends MyAbstract list...
    private LinkedNode front;
	private int size; // this is the new variable for remembering size
	private LinkedNode tail;

	public MyLinkedList() {
		clear();
	}

	public void clear() {
		front = null;
		size = 0;
	}

    public int size() {
		return size;
    }

    public void addFront(Object o) {
		front = new LinkedNode(o,front);
		size++; // we added an element, so the size is one larger
	}

// here we implemented addLast by walking to the end of the list
	public void add(Object o) { // addLast
		if (front == null) { // there's a special case for an empty list to avoid a NullPtrEx
			front = tail = new LinkedNode(o);
		} else {
			LinkedNode current = front;
			while(current.next != null) { // checking for current.next let's us stop one short (draw a picture)
				current = current.next;
			}
			current.next = new LinkedNode(o);
		}
		size++;
}

// the add[Last] method is pretty slow.  we can make it faster by adding data to store the last (tail) node.
// this paradigm is frequent in data structures -- more data to have faster computation.
// aside from the extra space, the primary disadvantage is the extra housekeeping involved for updating all the vars

public class MyLinkedList { // implements List or MyList or extends MyAbstract list...
	// LinkedNode snipped; copy from above

    private LinkedNode front;
	private int size;
	private LinkedNode tail; // the new variable

	public MyLinkedList() {
		front = tail = null;
		size = 0;
	}

	public void clear() {
		front = tail = null;
		size = 0;
	}

    public int size() {
		return size;
	}

    public void addFront(Object o) {
		front = new LinkedNode(o,front)
		if (front.next == null) tail = front; // special case for empty list
		size++;
	}

	public void add(Object o) { // addLast
		if (tail == null) {
			front = tail = new LinkedNode(o);
		} else {
			tail.next = new LinkedNode(o);
			tail = tail.next; // update tail
		}
		size++;
	}

	public Object get(int idx) {
		if (idx<0 || idx>=size()) throw new NoSuchElementException();
		LinkedNode current = front;
		int i = 0;
		while(current != null) {
			if (i == idx) return current.data;
			current = current.next;
			i++;
		}
		return null; // necessary to make java happy
	}
}