/**
	*  This class contains the methods to create a linked list and to
	*  insert and delete values from the list stored in ascending order
	*  contains an inner class Node
	*
	*  @author  Elizabeth Adams
	*  @version  Final
	*/
	
    public class LinkedListLab21
   {
      private Node list;  // Node is an inner class 
								
 
   /**
   *  explicit LinkedList constructor
   *
   */
       public LinkedListLab21 ()
      {
         list = null;   // list is empty when created
      } // end constructor
    
   /**
   * This method creates a new node with the desired value in it
   * and inserts it in its proper place in a linked list in ascending order
   * 
   * @param  value to be stored in new node
   */
   public void insert( int aValue) 
   {
       Node newNode;
       Node current, previous;
      
       newNode = new Node (aValue);
      
       previous = null;  // compiler wants these outside if
       current  = null;
  
  			    // need special case for empty list
       if (list == null)  // insert newNode at head of list
       {  
          list = newNode;
       } 
       else   // list not empty, does it go at head?
         if (newNode.value <= list.value)// put it at head of list
         { 
            newNode.next = list;
            list = newNode;
         } 
         else // does it go at the end of 1 element list
         { 
            if (list.next == null)
            {
               list.next = newNode;
            }	 
            else// determine where to insert newNode
            {  
				   previous = list;
					current = list.next;  // exists because list wasn't empty
				
               while (current != null && aValue >= current.value) // move down list
               {
                     current = current.next; 
                     previous = previous.next;
               }
               if (current == null) // goes at end
               {
                  previous.next = newNode;  // or previous.next = newNode;
               }
               else // it goes between previous and current
               {
                  previous.next = newNode;
                  newNode.next = current;
               }	  
            } // end else
         } // end else
      } // end method insert
     

      /**
   	*  This method will determine whether a given value is in the list
   	* 
   	*  @param value being looked for
   	*  @return boolean telling whether value is in the list
   	*/ 
       public boolean isHere (int aValue)
      {
         Node current;
         boolean found;
      	
         current = list; // point current to head of list
         found = false;  // not looked for so not found

			    // while not at end  and value not found
         while (current != null && current.value != aValue) 
         {
            current = current.next; // move down list
         }
         if (current != null && current.value == aValue) // found desired value
         {
            found = true;
         }
         return found;
      } // end isHere
   		
   	/**
   	*  This method determines if the list is empty
   	*
   	*  @return true if it is, false otherwise
   	*
   	*/
       public boolean isEmpty ()
      {
         boolean empty;
      	
         empty = false;  // assume it is not empty
         if (list == null) // if it is
         {
            empty = true;  // reset boolean
         }
         return empty;
      }  
   	
   	/**
   	* 
   	* this method deletes a node containing a given value from a list
   	* 
   	* @param value to be deleted
   	*
   	*/
       public void deleteNode(int aValue)
      {
         Node current, previous;
         boolean temp, found;
      		
         previous = list;
         current = list.next;

      
         if ((!this.isEmpty()) && (this.isHere(aValue)) ) //list has elements
         																 // element in list
         {
            if (list.value == aValue)  // is value at head of list?
            {
               list = list.next; // delete it by moving list header
            }  // end if
            else  // where is it? - move down list looking for it
            {
               found = false;  // know it is there - haven't found it yet
               while (!found) // keep looking
               {
                  if  (current.value == aValue)// found it
                  {
                     previous.next = current.next;   // delete it
                     found = true;
                  } // end if
                  else  // move down list
                  {
                     current = current.next;
                     previous = previous.next;
                  } // end else
               } // end while  
            } // end else
         } // end if	  
      } // end deleteNode
   
   	/**
   	*  This method prints the contents of the linked list
   	*
   	*  @return a String holding the contents of the list
   	*/
       public String toString ()
      {
         Node current;
         String myString;
      	
         myString = "";  // initialize return String
         current = list;   
         while (current != null)
         {
            myString = myString + current.value + " ";
            current = current.next;
         }
         return myString;
      }	  
   
      /**
   	*  Private inner class Node
      */
       private class Node   
      {
         private int value;
         private Node next;  	
      
      /**
      *  explicit Node constructor
      */	
          private Node(int data)
         {
            value = data;
            next = null;
         } // end constructor
      
      } // end class Node
   
   } // end class LinkedListLab21