/**
 * Simple Linked List class
 * @author Suzanne Balik, 9 Oct 2001
 */

public class SimpleLinkedList {

  private Node head;
  
  public SimpleLinkedList(){
    head = null;
  }
  
  public void clear() {
    head = null;
  }
  
  public boolean isEmpty() {
    if (head == null) 
      return true;
    else
      return false;
  }
  
  public void addToHead(int info) {
    head = new Node(info, head);
  }
  
  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;
      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) {
        prev.link = curr.link;
	return;
      }
      else {
        prev = curr;
	curr = curr.link;
      }
    }
    
    //Case 4 - The list does not contain info 
    //         just return
    return;
  }
  
  public void mergeSort() {
    
    //FILL IN THIS METHOD AND ADD ANY NECESSARY HELPER METHODS
  }
    
  //FIX THE toString() method to add a "\n" every 10 values or so.  
  
  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
  SimpleLinkedList list = new SimpleLinkedList();
  
  //Check if the list is empty
  System.out.println("List empty? " + list.isEmpty());
  
  //Add some integers to the list
  list.addToHead(5);
  list.addToHead(9);
  list.addToHead(4);
  list.addToHead(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());
  }
}