public class OrderedLinkedList extends LinkedListClass
{
        //default constructor
    public OrderedLinkedList()
    {
        super();
    }

        //copy constructor
    public OrderedLinkedList(OrderedLinkedList otherList)
    {
        super(otherList);
    }

    public void mergeSort()
    {
        first = recMergeSort(first);
    }//end mergeSort


    private LinkedListNode divideList(LinkedListNode head)
    {
        LinkedListNode middle;
        LinkedListNode current;

        LinkedListNode secondListHead;

        if(head == null)   //list is empty
            secondListHead = null;
        else
            if(head.link == null)   //list has only one node
                secondListHead = null;
            else
            {
                middle = head;
                current = head.link;

                if(current != null)     //list has more than two nodes
                    current = current.link;

                while(current != null)
                {
                    middle = middle.link;
                    current = current.link;

                    if(current != null)
                        current = current.link;
                } //end while

                secondListHead = middle.link;   //secondListHead points
                                        //to the first tnode of the
                                        //second sublist
                middle.link = null;     //set the link of the last node
                                        //of the first sublist to null
            } //end else

            return secondListHead;
    } //end divideList


    private LinkedListNode mergeList(LinkedListNode first1,
                                     LinkedListNode first2)
    {
        LinkedListNode lastSmall;   //reference variable to the
                                    //last node of the merged list
        LinkedListNode newHead;     //reference variable to the
                                    //merged list

        if(first1 == null)      //the first sublist is empty
            return first2;
        else
            if(first2 == null)   //the second sublist is empty
                return first1;
            else
            {
                if(first1.info.compareTo(first2.info) < 0) //compare
                                                           //the first nodes
                {
                    newHead = first1;
                    first1 = first1.link;
                    lastSmall = newHead;
                }
                else
                {
                    newHead = first2;
                    first2 = first2.link;
                    lastSmall = newHead;
                }

                while(first1 != null && first2 != null)
                {
                    if(first1.info.compareTo(first2.info) < 0)
                    {
                        lastSmall.link = first1;
                        lastSmall = lastSmall.link;
                        first1 = first1.link;
                    }
                    else
                    {
                        lastSmall.link = first2;
                        lastSmall = lastSmall.link;
                        first2 = first2.link;
                    }
                } //end while

                if(first1 == null)  //first sublist is exhausted first
                    lastSmall.link = first2;
                else              //second sublist is exhausted first
                    lastSmall.link = first1;

                return newHead;
            }
    }//end mergeList


    private LinkedListNode recMergeSort(LinkedListNode head)
    {
        LinkedListNode otherHead;

        if(head != null)  //if the list is not empty
           if(head.link != null)  //if the list has more
                                  //than one node
           {
              otherHead = divideList(head);
              head = recMergeSort(head);
              otherHead = recMergeSort(otherHead);
              head = mergeList(head, otherHead);
           }

        return head;
    } //end recMergeSort


        //Method to determine whether searchItem is in
        //the list.
        //Postcondition: Returns true if searchItem is found
        //               in the list; otherwise, it returns
        //               false.
    public boolean search(DataElement searchItem)
    {
        LinkedListNode current; //variable to traverse the list
        boolean found;

        current = first;  //set current to point to the first
                          //node in the list

        found = false;    //set found to false

        while(current != null && !found ) //search the list
            if(current.info.compareTo(searchItem) >= 0)
                found = true;
            else
                current = current.link; //make current point to
                                        //the next node

        if(found)
           found = current.info.equals(searchItem);

        return found;
    }

        //Method to insert insertItem in the list
        //Postcondition: first points to the new list,
        //       newItem is inserted at the proper place
        //       in the list, and count is incremented by 1.
    public void insertNode(DataElement insertItem)
    {
        LinkedListNode current;     //variable to traverse the list
        LinkedListNode trailCurrent;    //variable just before current
        LinkedListNode newNode;     //variable to create a node

        boolean  found;

        newNode = new LinkedListNode(); //create the node
        newNode.info = insertItem.getCopy(); //store newItem
                                          //in the node
        newNode.link = null;    //set the link field of the node
                                //to null

        if(first == null)  //Case 1
        {
           first = newNode;
           count++;
        }
        else
        {
           trailCurrent = first;
           current = first;
           found = false;

           while(current != null && !found) //search the list
                if(current.info.compareTo(insertItem) >= 0)
                   found = true;
                else
                {
                   trailCurrent = current;
                   current = current.link;
                }

           if(current == first)   //Case 2
           {
              newNode.link = first;
              first = newNode;
              count++;
           }
           else          //Case 3
           {
              trailCurrent.link = newNode;
              newNode.link = current;
              count++;
           }
        }//end else
    }//end insertNode


        //Method to delete deleteItem from the list.
        //Postcondition: If found, the node containing
        //               deleteItem is deleted from the
        //               list. Also, first points to the first
        //               node, last points to the last
        //               node of the updated list, and count
        //               is decremented by 1.
    public void deleteNode(DataElement deleteItem)
    {
       LinkedListNode current;      //variable to traverse the list
       LinkedListNode trailCurrent; //variable just before current
       boolean found;

       if(first == null)    //Case 1; list is empty.
          System.err.println("Can not delete from an "
                           + "empty list.");
       else
       {
           if(first.info.equals(deleteItem)) //Case 2
           {
              first = first.link;
              count--;
           }
           else  //search the list for the node with the given info
           {
              found = false;
              trailCurrent = first;   //set trailCurrent to point to
                                    //the first node
              current = first.link;   //set current to point to the
                                      //second node

              while(current != null && !found)
              {
                  if(current.info.compareTo(deleteItem) >= 0)
                     found = true;
                  else
                  {
                     trailCurrent = current;
                     current = current. link;
                  }
              } //end while

              if(current == null)   //Case 4
                 System.out.println("Item to be deleted is "
                                  + "not in the list.");
              else
                 if(current.info.equals(deleteItem)) //item to be
                                         //deleted is in the list
                 {
                    if(first == current)    //Case 2
                    {
                       first = first.link;
                       count--;
                    }
                    else                    //Case 3
                    {
                       trailCurrent.link = current.link;
                       count--;
                    }
                 }
                 else                   //Case 4
                    System.out.println("Item to be deleted is "
                                     + " not in the list.");
           }
        } //end else
    } //end deleteNode
}