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

class GenericLinkList<E>
   {
   private GenericLink<E> first;// ref to first link on list
   int numLinks;		// tracks the size of the list

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

   public GenericLinkList()              // constructor
      {
      first = null;               // no links on list yet
      numLinks = 0;
      }
 
// -------------------------------------------------------------
   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
      numLinks++;
      }
// -------------------------------------------------------------
// Added by Sriram Pemmaraju on Feb 22, 2007
//--------------------------------------------------------------
   public E deleteFirst()
      {
      E temp;
      // empty list
      if(first == null)
	return null;
      // non-empty list
      else{
	temp = first.data;
	first  = first.next;
        numLinks--;
      	}
      return temp;
      }
// --------------------------------------------------------------
// Added by Sriram Pemmaraju on Feb 22, 2007.
// The function returns a copy of the list, but with items 
// in reverse order. 
// -----------------------------------------------------------------
   public GenericLinkList<E> copy()
      {
      GenericLinkList<E> temp = new GenericLinkList<E>();
      GenericLink<E> current = first;

      // Scan this list from front to back
      while(current != null){
	temp.insertFirst(current.data);
	current = current.next;
      	}

      return temp;
      }
// --------------------------------------------------------------
// Added by Sriram Pemmaraju on Feb 22, 2007.
// The function returns a copy of the list in an array, but with items
// in reverse order.
// -----------------------------------------------------------------
   public E[] copyIntoArray()
      {
      E[] temp = (E []) new Object[numLinks];
      GenericLink<E> current = first;

      // Scan this list from front to back
      int index = 0;
      while(current != null){
        temp[index++] = current.data;
        current = current.next;
        }

      return temp;
      }

// ---------------------------------------------------------------
// Added by Sriram Pemmaraju on Feb 22, 2007.
// ---------------------------------------------------------------
   public boolean isEmpty()
   {
	return (first == null);
   }
// ---------------------------------------------------------------
// Added by Sriram Pemmaraju on Feb 22, 2007.
// ---------------------------------------------------------------
   public int size()
   {
	return numLinks;
   }
// ---------------------------------------------------------------
   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.equals(current.data))        // 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
      }
// -------------------------------------------------------------
// Modified  on 2/22 to ensure that it works with empty list
// -------------------------------------------------------------
   public GenericLink<E> delete(E key)    // delete link with given key
      {                           
      if(first == null)
	return null;

      GenericLink<E> current = first;              // search for link
      GenericLink<E> previous = first;
      
      while(!key.equals(current.data))
         {
         if(current.next == null)
            return null;                 // didn't find it
         else
            {
            previous = current;          // go to next link
            current = current.next;
            }
         } // end of while 

      // Found key
      numLinks--;
      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 GenericLinkList