12.4

public class List
{
   private Node head;
   
   class Node 
   { 
      int info;
      Node link; 
      
      Node(int i, Node n)
      { 
         info = i;
         link  = n;
      }
      
      void printList ()
      { 
         System.out.println(info);
         if (link != null)
            link.printList();
      }
      
      void insert (int item) 
      {
         if (link == null || item < link.info)
            link = new Node(item, link);
         else
            link.insert(item);
      }
   }

   public void printList()
   {
      if (head != null)
         head.printList();
   }

   public void insert(int item)
   {
      if (head == null || item < head.info)
         head = new Node(item, head);
      else
         head.insert(item);
   }
   
   public static void main(String args[])
   {
      int i;
      List testList = new List();
      do
      {
         do
         {
            System.out.println("Enter a non-negative integer (zero to stop)");
            i = In.getInt();
         } while (i < 0);
         if (i > 0)
            testList.insert(i);
      } while (i > 0);
      testList.printList();
   }
} 

public void deleteLast ()
{ 
   if (head == null) 
      System.out.println("Attempt to delete from empty list");
   else if (head.link == null) 
      head = null; 
   else 
      head.deleteLast(); 
}

void deleteLast ()
{ 
   if (link.link == null) 
      link = null; 
   else
      link.deleteLast();
} 

Node copy ()
{ 
   Node temp = new Node();
   temp.info = info;
   if (link != null) 
      temp.link = link.copy();
   return temp; 
}