// Arup Guha
// 6/24/02, edited 7/7/04 for 2004 BHCSI, 
// Portion of a linked list class, using only one instance variable.
// Removed the reverse from the previous version.

import java.util.Random;

public class LL2 {
  
  private Node head;

  // Initializes the LL object to be empty.
  public LL2() {
    head = null;
  }

  public LL2(Node front) {
    head = front;
  }

  public boolean isEmpty() { 
    return (head == null);
  }

  public void makeEmpty() { 
    head = null;
  }

  // Creates a node with the value x and inserts it into the LL object.
  public void insert(int x) {

    Node temp = new Node(x); // Create a node with the value x.

    // Take care of the case where the LL object is empty.
    if (head == null)
      head = temp;

    // Deal with the standard case.
    else {
  
      // Insertion into the front of the LL object.
      if (head.data > x) {
        temp.next = head;
        head = temp;
      } 

      else {

        // Set up helper reference to refer to the node that the inserted
        // node should be inserted after.
        Node helper = head;   
        while ((helper.next != null) && (helper.next.data < x)) 
          helper = helper.next;

        // Adjust necessary references.
        temp.next = helper.next;
        helper.next = temp;
      }
    }
  }

  // Removes a node storing the value x. If no such node exists, nothing
  // is done and the method returns false. Otherwise, the node is removed
  // and true is returned.
  public boolean remove(int x) {

    // Can't remove anything from an empty list.
    if (head == null)
      return false;
   
    // Remove the first element, if necessary.
    if (head.data == x) {
      head = head.next;
      return true;
    }

    // Set up helper reference to refer to the node right before the node
    // to be deleted would be stored.
    Node helper = head;   
    while ((helper.next != null) && (helper.next.data < x)) 
      helper = helper.next;

    // If x was too big to be on the list, simply return false.
    if (helper.next == null)
      return false;

    // Only if the appropriate node stores x should it be deleted.
    if (helper.next.data == x) {
      helper.next = helper.next.next;
      return true;
    }   

    return true; // Never gets here, compiler complains w/o this.
  }

  // Returns a copy of the current object.
  public LL2 copy() {

    // Create a new empty list.
    LL2 cp = new LL2();
    Node temp = head;

    // Adds each subsequent item to the list, one by one.
    while (temp != null) {
      cp.addToEnd(new Node(temp.data));
      temp = temp.next;
    }

    // Return the list.
    return cp;
  }

  // Inserts a node after every node in the current list that stores twice
  // the value of the previous node.
  public void doublelist() {
   
    Node temp = head;

    // Iterate through the entire list.
    while (temp != null) {

      // Create the new node to add.
      Node addnode = new Node(2*temp.data);

      // Patch in the new node into the current list.
      Node temp2 = temp.next; // Save temp.next

      // Adjust the previous node to point to the new one.
      temp.next = addnode; 
      addnode.next = temp2; // Patch the new node to the next node.

      temp = addnode.next; // Advance temp.

    }
  }

  // Add x to the end of the current list.
  public void addToEnd(Node x) {
    x.next = null;

    // Find the last node.
    Node temp = findLast();

    // Case where current list is empty.
    if (temp == null)
      head = x;

    // Typical case.
    else
      temp.next = x;
  }

  // Prints out all the values in the current list, separated by spaces.
  public void printlist() {

    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data+" ");
      temp = temp.next;
    }
  }

  // Returns a reference to the last node in the current list.
  public Node findLast() {

    // No list.
    if (head == null)
      return null;

    // Find the last node.
    Node temp = head;
    while (temp.next != null)
      temp = temp.next;
    return temp;
  }

  // Run some tests here.
  public static void main(String[] args) {

    LL2 list = new LL2();
    Random ran = new Random();

    for (int i=0; i<20;i++) {
      int temp = ran.nextInt()%8;
      if (temp >= 0)
        list.insert(temp);
      else
        list.remove(-temp);
    }

    list.printlist();
    System.out.println();

    list.doublelist();
    list.printlist();

    System.out.println();

  }  
}