Adding two polynomials stored as linked lists

Question

I have the following code..

    import java.io.*;
    class Link

    {

      public int coeff;

      public int exp;

      Link next;

      public Link(int a,int b)
    {
       coeff=a;exp=b;
    }

       public int retcof(){
        return coeff;
    }

       public int retexp() {
        return exp;
    }

       public void displayLink(){
       System.out.print(coeff+"x^"+exp);
    }


    }


     class LinkList{


     Link first,last;


    public LinkList(){
               ;
    }

      public void insertfirst(int x,int y)
    {
      Link newLink=new Link(x,y);

      newLink.next=first;

      first=newLink;
    }

      public void displayList()
    {

      Link x=first;


      while(x!=null)
    {


      x.displayLink();

         x=x.next;

          if(x!=null)

          System.out.print("+");

    }



    }


      /*public void add(LinkList a,LinkList b)

      {
      int p;

      Link current1=a.first;

      Link current2=b.first;

      LinkList qwe=new LinkList();

      while(current2!=null)

      { 

      while(current1!=null)

      { 
       if(current1.retexp()>current2.retexp()) 

        qwe.insertfirst(current1.retcof(),current1.retexp());
       else if(current2.retexp()>current1.retexp())

        qwe.insertfirst(current2.retcof(),current2.retexp());
       else if(current1.retexp()==current2.retexp())

       { 

       p=current1.retcof()+current2.retcof();


     qwe.insertfirst(p,current2.retexp());

       }

         current1=current1.next;



      }

        current2=current2.next;


      }

      qwe.displayList();

      }*/


 public void add(LinkList a,LinkList b)
{
Link current1=a.first;

  Link current2=b.first;

  LinkList qwe=new LinkList();
while (current1 != null || current2 != null) {    
    //now check if one of them has ended    
   if (current1 == null&&current2!=null) //first ended; insert remaining nodes from second; return result    
     {qwe.insertfirst(current2.retcof(),current2.retexp());current2 = current2.next;}
  if (current2 == null&&current1!=null) //second ended, insert remaining nodes from first; return result  
    {qwe.insertfirst(current1.retcof(),current1.retexp());  current1 = current1.next;}
   //otherwise, compare exponents    
   if ((current1 != null && current2 != null)&&(current1.retexp() > current2.retexp())) 
      {qwe.insertfirst(current1.retcof(),current1.retexp()); current1 = current1.next;}    
       //advance the first pointer, but not he second        
   else if ((current1 != null && current2 != null)&&(current1.retexp() < current2.retexp()))   
       {qwe.insertfirst(current2.retcof(),current2.retexp()); current2 = current2.next;}
      //in this case advancing the second pointer, but not the first    
   else if((current1 != null && current2 != null)&&(current1.retexp() == current2.retexp()))//exponents are equal    
       {qwe.insertfirst(current2.retcof()+current1.retcof(),current2.retexp());; current1 = current1.next; current2 = current2.next;}    
      //add the members and advance both pointers    
}
qwe.displayList();
}





    }

      class zz
    {


      public static void main(String [] args)throws IOException
    {

       int degree1,degree2,num1,itr;


        LinkList wow=new LinkList();


        LinkList wow1=new LinkList();

    //wow.insertfirst(1,2);


      System.out.println("Enter the degree of the first polynomial "+" ");


      DataInputStream X=new DataInputStream(System.in);


      String s=X.readLine();

      degree1=Integer.parseInt(s);


      itr=degree1;


      while(itr>=0){ 

      System.out.print("enter the coeff of x^"+itr+" : ");

       s=X.readLine();
       num1=Integer.parseInt(s);

       wow.insertfirst(num1,itr);

       itr--;

      } 


      wow.displayList();


      System.out.println("\n"+"Enter the degree of the second polynomial "+" ");


      s=X.readLine();

      degree2=Integer.parseInt(s);

      itr=degree2;


      while(itr>=0)
    {

      System.out.print("enter the coeff of x^"+itr+" : ");

      s=X.readLine();
      num1=Integer.parseInt(s);

      wow1.insertfirst(num1,itr);
     itr--;

    }


      wow1.displayList();


      System.out.println("\n");


      wow.add(wow,wow1);

    }

    }

EDIT:FIXED. There was problem with the add() function which has been rectified now!

Is there any other efficient way to do this? How to make this code simpler particularly the add() function which seems a bit complex.

Answer 1

The following is the complete resolved code.

    import java.io.*;
class Link

{

  public int coeff;

  public int exp;

  Link next;

  public Link(int a,int b)
{
   coeff=a;exp=b;
}

   public int retcof(){
    return coeff;
}

   public int retexp() {
    return exp;
}

   public void displayLink(){
   System.out.print(coeff+"x^"+exp);
}


}


 class LinkList{


 Link first,last;


public LinkList(){
           ;
}

  public void insertfirst(int x,int y)
{
  Link newLink=new Link(x,y);

  newLink.next=first;

  first=newLink;
}

  public void displayList()
{

  Link x=first;


  while(x!=null)
{


  x.displayLink();

     x=x.next;

      if(x!=null)

      System.out.print("+");

}



}



public void add(LinkList a,LinkList b)
{

Link current1=a.first;


   Link current2=b.first;


  LinkList qwe=new LinkList();

  while (current1 != null || current2 != null) {    

   if (current1 == null&&current2!=null)

     {qwe.insertfirst(current2.retcof(),current2.retexp());current2 = current2.next;}
  if (current2 == null&&current1!=null)

    {qwe.insertfirst(current1.retcof(),current1.retexp());  current1 = current1.next;}

   if ((current1 != null && current2 != null)&&(current1.retexp() > current2.retexp())) 

      {qwe.insertfirst(current1.retcof(),current1.retexp()); current1 = current1.next;}    

   else if ((current1 != null && current2 != null)&&(current1.retexp() < current2.retexp()))   

       {qwe.insertfirst(current2.retcof(),current2.retexp()); current2 = current2.next;}

   else if((current1 != null && current2 != null)&&(current1.retexp() == current2.retexp()))//exponents are equal    

       {qwe.insertfirst(current2.retcof()+current1.retcof(),current2.retexp());; current1 = current1.next; current2 = current2.next;}    
}
qwe.displayList();
}





}

  class k
{


  public static void main(String [] args)throws IOException
{

   int degree1,degree2,num1,itr;


    LinkList wow=new LinkList();


    LinkList wow1=new LinkList();


  System.out.println("Enter the degree of the first polynomial "+" ");


  DataInputStream X=new DataInputStream(System.in);


  String s=X.readLine();

  degree1=Integer.parseInt(s);


  itr=degree1;


  while(itr>=0){ 

  System.out.print("enter the coeff of x^"+itr+" : ");

   s=X.readLine();
   num1=Integer.parseInt(s);

   wow.insertfirst(num1,itr);

   itr--;

  } 


  wow.displayList();


  System.out.println("\n"+"Enter the degree of the second polynomial "+" ");


  s=X.readLine();

  degree2=Integer.parseInt(s);

  itr=degree2;


  while(itr>=0)
{

  System.out.print("enter the coeff of x^"+itr+" : ");

  s=X.readLine();
  num1=Integer.parseInt(s);

  wow1.insertfirst(num1,itr);
 itr--;

}


  wow1.displayList();


  System.out.println("\n");


  wow.add(wow,wow1);

}

}

Answer 2

The biggest thing I see here is your lack of handling properly the case where either of your current variables are null, in a manner that will prevent a NPE (as you've seen)...

Your code, better formatted below has a couple issues regarding the handling of null

while (current1 != null || current2 != null) {    
   //now check if one of them has ended    
   if (current1 == null) //first ended; insert remaining nodes from second; return result    
   {
        qwe.insertfirst(current2.retcof(),current2.retexp());
        current2 = current2.next;
   }
   if (current2 == null) //second ended, insert remaining nodes from first; return result  
   {
        qwe.insertfirst(current1.retcof(),current1.retexp());  
        current1 = current1.next;
   }
   //otherwise, compare exponents    
   if (current1.retexp() > current2.retexp()) 
   {
        qwe.insertfirst(current1.retcof(),current1.retexp()); 
        current1 = current1.next;
   }    
   //advance the first pointer, but not he second        
   else if (current1.retexp() < current2.retexp())   
   {
        qwe.insertfirst(current2.retcof(),current2.retexp()); 
        current2 = current2.next;
   }
   //in this case advancing the second pointer, but not the first    
   else //exponents are equal                     
   {        
        qwe.insertfirst(current2.retcof()+current1.retcof(),current2.retexp());
        current1 = current1.next; 
        current2 = current2.next;
   }    
   //add the members and advance both pointers    
}

Consider the case where current2 is null

Your code will correctly determine that it's null and enter your second if block, and advance current1.

However, you don't protect against the access of fields on current2 in the subsequent if blocks, so you're going to eventually get a NPE, on:

 //otherwise, compare exponents    
if (current1.retexp() > current2.retexp())  // right here! you access current2, but it's null :(

You need to bypass all this logic if either of your links are null so you don't get into this mess.