// Programmer Sriram Pemmaraju. 2/18/07
//
// This class was created by starting with Lafore's LinkList class,
// enhancing it a bit and then making it generic.

class GenericLinkList<E extends Comparable<E>>
   {
   private GenericLink<E> first;            // ref to first link on list

// -------------------------------------------------------------

   public GenericLinkList()              // constructor
      {
      first = null;               // no links on list yet
      }
// -------------------------------------------------------------
   public void insertFirst(E data)
      {                           // make new link
      GenericLink<E> newLink = new GenericLink<E>(data);
      newLink.next = first;       // it points to old first link
      first = newLink;            // now first points to this
      }
// -------------------------------------------------------------
   public GenericLink<E> find(E key)      // find link with given key
      {            
      if(first == null)
	return null;

      GenericLink<E> current = first;              // start at 'first'

      // The compareTo function, expected of class E is used
      // in code below.
      while(key.compareTo(current.data) != 0)        // while no match,
         {
         if(current.next == null)        // if end of list,
            return null;                 // didn't find it
         else                            // not end of list,
            current = current.next;      // go to next link
         }
      return current;                    // found it
      }
// -------------------------------------------------------------
   public GenericLink<E> delete(E key)    // delete link with given key
      {                           // (assumes non-empty list)
      GenericLink<E> current = first;              // search for link
      GenericLink<E> previous = first;
      while(key.compareTo(current.data) != 0)
         {
         if(current.next == null)
            return null;                 // didn't find it
         else
            {
            previous = current;          // go to next link
            current = current.next;
            }
         }                               // found it
      if(current == first)               // if first link,
         first = first.next;             //    change first
      else                               // otherwise,
         previous.next = current.next;   //    bypass it
      return current;
      }
// -------------------------------------------------------------
   public String toString()
   {
      String temp = "";
      GenericLink current = first;   // start at beginning of list
      while(current != null)         // until end of list,
         {
         temp = temp + (current.data).toString() + "\n";   
         current = current.next;  // move to next link
         }
    
      return temp;
   }

	

// -------------------------------------------------------------
   public void displayList()      // display the list
      {
      System.out.println("List (first-->last): ");
      System.out.print(toString());
      }
// -------------------------------------------------------------
   }  // end class LinkList