// LinkedList.java

public class LinkedList
{
   protected Node head, tail;
   private int numOfNodes;

   public LinkedList()
   {
      head = tail = null;
      numOfNodes = 0;
   }

   public boolean isEmpty()
   {
      return (head == null);
   }

   public int numOfNodes()
   {
      return numOfNodes;
   }

   public Node removeHead()
   {
      numOfNodes--;
      Node toRemove = head;
      head = head.next;
      if (head == null)
         tail = null;
      return toRemove;
   }

   public void insertAtFront(Node toInsert)
   {
      toInsert.next = head;
      head = toInsert;
      // check for a change in the tail pointer
      if (toInsert.next == null)
         tail = toInsert;
      numOfNodes++;
   }

   public void insertAtEnd(Node toInsert)
   {
      if (head == null)
         head = tail = toInsert;
      else
      {
         tail.next = toInsert;
         tail = toInsert;
      }
      numOfNodes++;
   }

   public void insertInOrder(Node toInsert)
   {
      Node t = null, r = head;
      boolean found = false;
      while ((r != null) && (!found))
         if (r.cost > toInsert.cost)
            found = true;
         else
         {
            t = r;
            r = r.next;
         }
      if (t == null)
      {
         toInsert.next = head;
         head = toInsert;
      }
      else
      {
         t.next = toInsert;
         toInsert.next = r;
      }
      // check for a change in the tail pointer
      if (toInsert.next == null)
         tail = toInsert;
      numOfNodes++;
   }

   public void merge(LinkedList list)
   {
      Node p = list.head;
      while (p != null)
      {
         Node successor = p.next;
         insertInOrder(p);
         p = successor;
      }
   }

   public boolean alreadyIncludes(Node n)
   {
      Node p = head;
      while (p != null)
      {
         if (Utility.isSameState(p.getState(), n.getState()))
            return true;
         else
            p = p.next;
      }
      return false;
   }

}