/*
   An object of type StringList represents a list of strings.  Methods
   are provided to insert a string into the list, to delete a string
   from the list, and to check whether a given string occurs in the list.
   (For testing purposes, a method is also provided that will return an
   array containing all the strings in the list.)
      Note that this class is certainly NOT meant to be a full-featured
   List class.  It is for demonstration only.
*/


public class StringList {

    // Internally, the list of strings is represented as a linked list
    // of nodes belonging to the nested class Node.  The strings in the
    // list are stored in increasing order (using the order given by
    // the compareTo() method from the string class, which is the same
    // as alphabetical order if all the strings are made up of lower
    // case letters.)

   private static class Node {
       String item;
       Node next;
   }
   
   
   private Node head;  // A pointer to the first node in the linked list.
                       // If the list is empty, the value is null.
      
   
   public boolean find(String searchItem) {
         // Returns true if the specified item is in the list, and
         // false if it is not in the list.  (For demonstration 
         // purposes, this method does not use the fact that the
         // list is ordered.)
         
      Node runner;    // A pointer for traversing the list.
      
      runner = head;  // Start by looking at the head of the list.
      while ( runner != null ) {
             // Go through the list looking at the string in each
             // node.  If the string is the one we are looking for,
             // return true, since the string has been found in the list.
         if ( runner.item.equals(searchItem) )
            return true;
         runner = runner.next;  // Move on to the next node.
      }
      
      // At this point, we have looked at all the items in the list
      // without finding searchItem.  Return false to indicate that
      // the item does not exist in the list.
      
      return false;
      
   } // end find()
   
   
   public boolean delete(String deleteItem) {
           // If the specified string occurs in the list, delete it.
           // Return true if the string was found and deleted.  If the
           // string was not found in the list, return false.  (If the
           // item exists multiple times in the list, this method
           // just deletes the first one.)

      if ( head == null ) {
            // The list is empty, so it certainly doesn't contain deleteString.
         return false;
      }
      else if ( head.item.equals(deleteItem) ) {
            // The string is the first item of the list.  Remove it.
         head = head.next;
         return true;
      }
      else {
            // The string, if it occurs at all, is somewhere beyond the 
            // first element of the list.  Search the list.
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND list node.
         previous = head;
         while ( runner != null && runner.item.compareTo(deleteItem) < 0 ) {
                  // Move previous and runner along the list until runner
                  // falls off the end or hits a list element that is
                  // greater than or equal to deleteItem.  When this 
                  // loop ends, runner indicates the position where
                  // deleteItem must be, if it is in the list.
            previous = runner;
            runner = runner.next;
         }
         if ( runner != null && runner.item.equals(deleteItem) ) {
                // Runner points to the node that is to be deleted.
                // Remove it by changing the pointer in the previous node.
            previous.next = runner.next;
            return true;
         }
         else {
               // The item does not exist in the list.
            return false;
         }
      }
      
   } // end delete()
   
   
   public void insert(String insertItem) {
          // Add insertItem to the list.  It is allowed to add
          // multiple copies of the same item.
          
      Node newNode;          // A Node to contain the new item.
      newNode = new Node();
      newNode.item = insertItem;  // (N.B.  newNode.next is null.)
      
      if ( head == null ) {
            // The new item is the first (and only) one in the list.
            // Set head to point to it.
         head = newNode;
      }
      else if ( head.item.compareTo(insertItem) >= 0 ) {
            // The new item is less than the first item in the list,
            // so it has to be inserted at the head of the list.
         newNode.next = head;
         head = newNode;
      }
      else {
            // The new item belongs somewhere after the first item
            // in the list.  Search for its proper position and insert it.
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND position.
         previous = head;
         while ( runner != null && runner.item.compareTo(insertItem) < 0 ) {
                  // Move previous and runner along the list until runner
                  // falls off the end or hits a list element that is
                  // greater than or equal to insertItem.  When this 
                  // loop ends, runner indicates the position where
                  // insertItem must be inserted.
            previous = runner;
            runner = runner.next;
         }
         newNode.next = runner;     // Insert newNode after previous.
         previous.next = newNode;
      }
      
   }  // end insert()
   
   
   public String[] getElements() {
         // Returns an array containing all the elements
         // in the list.  (A superior way to provide the
         // same information would be as an object of
         // type java.util.Enumeration.)
   
      int count;          // For counting elements in the list.
      Node runner;        // For traversing the list.
      String[] elements;  // An array to hold the list elements.
      
      // First, go through the list and count the number
      // of elements that it contains.
      
      count = 0;
      runner = head;
      while (runner != null) {
         count++;
         runner = runner.next;
      }
      
      // Create an array just large enough to hold all the
      // list elements.  Go through the list again and
      // fill the array with elements from the list.
      
      elements = new String[count];
      runner = head;
      count = 0;
      while (runner != null) {
         elements[count] = runner.item;
         count++;
         runner = runner.next;
      }
      
      // Return the array that has been filled with the list elements.

      return elements;

   } // end getElements()
   
   
} // end class StringList