import java.io.*;

class LinkList
   {
   private Link first;            // ref to first link on list
   private int numLinks;	  // to keep track of the number of links

// -------------------------------------------------------------
   public LinkList()              // default constructor
      {
      first = null;               // no links in the list yet
      numLinks = 0;
      }
// -------------------------------------------------------------
// Constructs a Link object with the given Record and inserts
// it at the beginning of this linked list
   public void insertFirst(Record newData)
      {                           // make new link
      Link newLink = new Link(newData);
      newLink.next = first;       // it points to old first link
      first = newLink;            // now first points to this
      numLinks++;
      }
// -------------------------------------------------------------
// Uses the keyWord in the given Record (key) to look for a matching
// Link object. Returns a reference to the first Link that is found.
// If no matching Link is found, then null is returned.
   public Link find(Record key)      
      {                           
      if(first == null)			// return null if list is empty
	return null;

      Link current = first;              // start at 'first'
      while(!current.data.keyWord.equals(key.keyWord))        // 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
      }
// -------------------------------------------------------------
// Deletes a Link from this LinkList that contains a Record with
// the same keyWord as the given Record (key). There may be more than
// one such matching Records; the function deletes just the first
// such Link.
   public Link delete(Record key)    // delete link with given key
      {                          
 
      if(first == null)		     // returns null if list if empty
	return null;

      Link current = first;          // search for link
      Link previous = first;
      while(!current.data.keyWord.equals(key.keyWord))
         {
         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
      numLinks--;
      return current;
      }
// -------------------------------------------------------------
   public void displayList()      // print the contents of the list
      {
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      }
// -------------------------------------------------------------
   public void displayList(PrintStream p)    	// print the contents of the
						// list to the given PrintStream
      {
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink(p);   // print data
         current = current.next;  // move to next link
         }
      }
// -------------------------------------------------------------
   public int length() 	// returns the length of the linked list
      {
	return numLinks;
      }
   }  // end class LinkList