/** 
 * More advanced LinkedList class with references 
 * to both the head and tail Node's in the list
 * Throws EmptyListException if attempt is made  
 * to remove and return value at front or rear 
 * of an empty list
 * @author Suzanne Balik, 16 Oct 2001
 */
public class LinkedList {

  private Node head;
  private Node tail;
  
  public LinkedList(){
    head = null;
    tail = null;
  }
  
  public void clear() {
    head = null;
    tail = null;
  }
  
  public boolean isEmpty() {
    if (head == null) 
      return true;
    else
      return false;
  }
  
  public void addToFront(int info) {
    if (head == null)
      head = tail = new Node(info);
    else
      head = new Node(info, head);
  }
  
  public void addToRear(int info) {
    if (head == null)
      head = tail = new Node(info);
    else {
      tail.link = new Node(info);
      tail = tail.link;
    }
  }
      
  
  public void remove(int info) {

    //Case 1 - The list is empty - just return
    if (isEmpty())
      return;
    
    //Case 2 - The head node contains info - 
    //         move head to the next node  
    if (head.info == info) {
      head = head.link;
      if (head == null)
        tail = null;
      return;
    }
    
    //Case 3 - One of the other nodes contains info - 
    //         link around the node
    Node prev = head;
    Node curr = head.link;
    while(curr != null) {
      if (curr.info == info) {
        if (curr == tail)
	  tail = prev;
        prev.link = curr.link;
	return;
      }
      else {
        prev = curr;
	curr = curr.link;
      }
    }
    
    //Case 4 - The list does not contain info - 
    //         just return
    return;
  }
  
  public int removeFromFront() throws EmptyListException {
    int retval = 0;
    if (isEmpty()) 
      throw new EmptyListException("List is empty!");
    else {
      retval = head.info;
      head = head.link;
      if (head == null)
        tail = null;
    }
    return retval;
  }
  
  public int removeFromRear() throws EmptyListException {
    int retval = 0;
    if (isEmpty())
      throw new EmptyListException("List is empty!");;
    if (head == tail) {
      retval = head.info;
      head = tail = null;
    }
    else {
      Node prev = head;
      while (prev.link.link != null)
        prev = prev.link;
      retval = prev.link.info;
      prev.link = null;
      tail = prev;
    }
    return retval;
  } 
  
  
  public String toString() {
    String s = "[";
    Node tmp = head;
    while (tmp != null) {
      s += tmp.info;
      if (tmp.link != null)
        s += ", ";
      tmp = tmp.link;
    }
    s += "]";
    return s;
  }
  
  public static void main (String[] args) {
  
  //Create a linked list
  LinkedList list = new LinkedList();
  
  //Check if the list is empty
  System.out.println("List empty? " + list.isEmpty());
  
  //Add some integers to front of list
  list.addToFront(5);
  list.addToFront(9);
  list.addToFront(4);
  list.addToFront(8);
  
  //Check if the list is empty
  System.out.println("List empty? " + list.isEmpty());
  
  //Output the list
  System.out.println(list);
  
  //Remove the head node and output the list
  list.remove(8);
  System.out.println(list);
  
  //Remove a node in the middle and output the list
  list.remove(9);
  System.out.println(list);
  
  //Try to remove something that's not in the list and 
  //output the list
  list.remove(2);
  System.out.println(list);
  
  //Clear the list - list should be empty
  list.clear();
  System.out.println("List empty? " + list.isEmpty());
  
  //Add to rear of empty list
  list.addToRear(6);
  System.out.println(list);
  
  //Remove from rear of list with one Node
  System.out.println(list.removeFromRear());
  System.out.println(list);
  
  //Add some integers to rear of list
  list.addToRear(1);
  list.addToRear(2);
  list.addToRear(3);
  list.addToRear(4);
  list.addToRear(5);
  System.out.println(list);
  
  //Remove from rear of list
  System.out.println("Removed from rear: " + 
                      list.removeFromRear());
  System.out.println(list);
  
  //Remove last integer in list
  list.remove(4);
  System.out.println(list);
  
  //Remove from front of list
  System.out.println("Removed from front: " + 
                      list.removeFromFront());
  System.out.println(list);
  
  //Clear list and try to remove from front - 
  //should catch an EmptyListException
  try {
    
    list.clear();
    list.removeFromFront();
  }
  catch (EmptyListException e) {
    System.err.println(e);
  }
  
  //See what happens is we remove from rear of empty list and 
  //don't catch the EmptyListException
  list.removeFromRear();
  }
}