//----------------------------------------------------------------
//	File:		list.java
//	Purpose:	Implement a list class 
//  Author : 
//  Last Modified : 
//  Comments : 
//----------------------------------------------------------------
import Node;

public class List  {

    Node first;
    Node last;
    int numNodes;
    // creates an empty linked list
    public void List(){
      first=last=null;
      numNodes = 0;
    }
    // insert a node at front
    public void insertFront(int n){
       first = new Node(n,first);
       numNodes++;
       if (numNodes==1)
         last=first;
    }
     // insert a node at back
    public void insertBack(int n){
       if (numNodes==0)  insertFront(n);
       else
         { Node newNode = new Node(n,null);
           last.next = newNode;
           last = newNode;
           numNodes++;
         }
    }
    // insert n in the list in order - assumes that the list is sorted
    public void insertInOrder(int n){
       Node ptr = first;
       Node prev = first;
       while (ptr != null && ptr.value < n)
          { prev = ptr; ptr=ptr.next;}
       if (ptr == null) // insert to back (or front)
          insertBack(n);
       else
          { Node newNode = new Node(n,ptr);
            prev.next = newNode; numNodes++;
          }
                  
    }
    // deletes the node with n (if any) else return false
    public boolean delete(int n){
         // find the node first
         Node ptr = first;
         Node prev = first;
         while (ptr != null && ptr.value != n)
          { prev = ptr; ptr=ptr.next;}
        if (ptr == null)   return false;
        else
          { prev.next= ptr.next; numNodes--; return true;} 
    }
    // deletes the last node of the list (if any)
    public void deleteLast()
        if (numNodes == 1)
         { first = last = null; numNodes--;}
        else if (numNodes > 1)
         { // find the node before last
           Node ptr = first;
           while (ptr.next != last) { ptr=ptr.next;}
           ptr.next = null; last=ptr; numNodes--;
         }
    }
    // deletes the first node of the list (if any)
    public void deleteFirst(){
       if (numNodes > 0)
         { first = first.next;numNodes--;}
    }
    // search for n and retunr true if found
    public boolean search(int n){
         Node ptr = first;
         while (ptr != null && ptr.value != n)
          { ptr=ptr.next;}
         if (ptr == null) return false;
         else return true;
    }
    // print the list
    public void print(){
      Node ptr = first;
      while (ptr != null)
        { System.out.println(ptr.value + " ");
          ptr = ptr.next;
        }
    }
    // print in reverse
    public void printReverse(){
       printReverseRecurse(first);
    }
    
    private void printReverseRecurse(Node ptr){
       if (ptr != null)
         { printReverseRecurse(ptr.next);
           System.out.println(ptr.value + " ");
         }
    
    }
    // return the node count
    public int nodeCount(){
        return numNodes;
    }
  }