// an alternative implementation of LinkedList that does not require
// a separate case for the head node

public class LinkedList2 {

    private Node head;
    private int size;
    
    public LinkedList2(){
	head = new Node(null);
	size = 0;
    }

    public void clear() {
	head = new Node (null);;
    }
		
    public void add(Object item) {
	add(size, item);
    }
		
    public void add(int index, Object item) {
	if (index<0 || index>size)
	    throw new IndexOutOfBoundsException ("List index out of bounds on add");
	
	Node curr = head.getNext();
	for (int i=0; i<index-1; i++){
	    curr = curr.getNext();
	    //System.out.println("it's not: "  +  curr.getItem());
	}
	// append after predecessor
	// System.out.println("appending after: "  +  curr.getItem());
	curr.setNext(new Node (item, curr.getNext()));
	
	size++;
    }
    
    public void remove(int index){
	if(index<0 || index >= size) 
	    throw new IndexOutOfBoundsException ("List index out of bounds on remove");
	Node curr = head.getNext();
	for (int i=0; i<index-1; i++)
	    curr = curr.getNext();
	curr.setNext(curr.getNext().getNext());
	size--;
    }
		
    public boolean remove(Object item){
	
	if(size==0)
	    return false;
	Node curr = head.getNext();
	while(curr.getNext()!=null && 
	      !item.equals(curr.getNext().getItem())){
	    // System.out.println("** It's not " + curr.getNext().getItem());
	    curr = curr.getNext();
	}
	// if node is not in the list
	if (curr.getNext()==null)
	    return false;
	else {
	    curr.setNext(curr.getNext().getNext());
	    size--;
	    return true;
	}
    }
			
    public int size() {
	return size;
    }
    
    public boolean isEmpty() {
	return size == 0;
    }
		
    public String toString(){
	String res = "[" + size + ": ";
	for (Node current = head.getNext(); current != null; current=current.getNext())
	    res += current.getItem().toString() + " ";
	return res+"]";
    }
    
    public static void main(String[] args) {
	
	LinkedList list = new LinkedList();
	list.add("Jane");
	System.out.println(list);
	list.add("John");
	System.out.println(list);
	list.add("Jess");
	System.out.println(list);
	
	list.add(0,"AAAA");
	System.out.println(list);
	list.add(4,"ZZZZ");
	System.out.println(list);
	list.add(2,"BBBB");
	System.out.println(list);
	
	list.remove(0);
	System.out.println("removing at index 0");
	System.out.println(list);
	list.remove(1);
	System.out.println("removing at index 1");
	System.out.println(list);
	list.remove(3);
	System.out.println("removing at index 3");
	System.out.println(list);
	
	list.remove("Jess");
	System.out.println(list);
    }
    
}