/**
 * A partial linked list implementation with a number of methods
 * (adapted from Duane Bailey's LinkedList from the structure5 package)
 * 
 * @author dave
 * @date 2/16/10
 *
 * @param <E>
 */
public class LinkedList<E>{ 
	private Node<E> head; 

	public LinkedList() { 
		head = null; 
	} 
	
	public void addFirst(E value) { 
		// note order that things happen: 
		// head is parameter, then assigned 
		head = new Node<E>(value, head); 
	} 
	
	public E removeFirst() { 
		E returnMe = head.value(); 
		head = head.next(); // move head down list 
		return returnMe;
	} 

	public E getFirst() { 
		return head.value(); 
	}
	
	public boolean contains(E value){ 
		Node<E> finger = head; 

		while (finger != null && !finger.value().equals(value)) { 
			finger = finger.next(); 
		}
		
		return finger != null; 
	}
	
	public boolean recursiveContains(E value){
		return containsHelper(head, value);
	}
	
	private boolean containsHelper(Node<E> current, E value){
		if( current == null ){
			return false;
		}else if( current.value().equals(value) ){
			return true;
		}else{
			return containsHelper(current.next(), value);
		}
	}

	public void clear() { 
		head = null; 
	}
	
	
	public void remove(E value){
		if( head.value().equals(value) ){
			head = head.next();
		}else{
			Node<E> finger = head.next(); 
			Node<E> prev = 	head;
		
			while (finger != null && !finger.value().equals(value)){
				prev = finger;
				finger = finger.next();
			}
			
			prev.setNext(finger.next());
		}
	}
	
	public int indexOf(E value){
		int index = 0;
		
		Node<E> finger = head;
		
		while( finger != null && !finger.value().equals(value) ){
			finger = finger.next();
			index++;
		}
		
		return index;
	}
	
	public void addLast(E value){
		if( head == null ){
			head = new Node<E>(value);
		}else{
			Node<E> finger = head;
			
			while( finger.next() != null ){
				finger = finger.next();
			}
			
			finger.setNext(new Node<E>(value));
		}
	}
	
	public E get(int index){
		Node<E> finger = head;
		
		for( int i = 0; i < index && finger != null; i++ ){
			finger = finger.next();
		}
		
		return finger == null ? null : finger.value();
	}

}