polynomial addition using linked list in java

Question

Here's my implementation of a addition of two polynomials using a linked List.
For example if I want to add
3x^2+5^x+3 and 4x^3+5x+2

first I check if there are similar exponents in the two polynomials and if so I add their coefficients and I append the exponents to a string.
After adding similar exponents then using the string I add the remaining parts in both polynomials to the final result.

 public class Node2{
        int coef;
        int exp;
        Node2 next;
        Node2(int c,int e,Node2 n){
            coef=c;
            exp=e;
            next=n;
        }
        Node2(int c,int e){
            coef=c;
            exp=e;

        }


}

public class LinkedPoly{
    static String exponent="";
    Node2 head;
    Node2 current;

LinkedPoly(){
    head=null;

}
public void createList(int c,int e){
    head=new Node2(c,e,head);
}

public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
    LinkedPoly addList=new LinkedPoly();

    Node2 temp1=list1.head;
            Node2 temp3=temp1;
    Node2 temp2=list2.head;
            Node2 temp4=temp2;
    while(temp1.next!=null){
        while(temp2.next!=null){
            if(temp1.exp==temp2.exp){

            addList.createList((temp1.coef+temp2.coef),temp1.exp);
            exponent+=temp1.exp;

            }
            temp2=temp2.next;
        }
        temp1=temp1.next;
        temp2=temp4;
    }
    String[] array=exponent.split("");
    for(int i=1;i<array.length;i++){

        while(temp3.next!=null){
            if(temp3.exp!=Integer.parseInt(array[i])){
                addList.createList(temp3.coef,temp3.exp);
            }
            temp3=temp3.next;
        }
        while(temp4.next!=null){
            if(temp4.exp!=Integer.parseInt(array[i])){
                addList.createList(temp4.coef,temp4.exp);
            }
            temp4=temp4.next;
        }
    }

    return addList;
}


public static void main (String args[]){
    LinkedPoly l1=new LinkedPoly();
    l1.createList(3,2);
    l1.createList(5,1);
    l1.createList(3,0);
    LinkedPoly l2=new LinkedPoly();
    l2.createList(4,3);
    l2.createList(5,1);
    l2.createList(2,0);

    LinkedPoly l3=add(l1,l2);
    System.out.println(l3.head.next.next.coef);
}

}

According to my example the exponent string include 1 and 0 ,but it only sums the coefficient of 1.Also the rest of the addition is also wrong.

I can't see where I am mistaking.Also how can I print out the final addList so that I can check if this implementation works fine

Answer 1

Here's an add method that works:

public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
    LinkedPoly addList=new LinkedPoly();

    Node2 temp1=list1.head;
    Node2 temp3=temp1;
    Node2 temp2=list2.head;
    Node2 temp4=temp2;
    while(temp1.next!=null){
        while(temp2.next!=null){
            if(temp1.exp==temp2.exp){

                addList.createList((temp1.coef+temp2.coef),temp1.exp);
                exponent+=temp1.exp;

            }
            temp2=temp2.next;
        }
        temp1=temp1.next;
        temp2=temp4;
        addList.print();
    }
    String[] array=exponent.split("");


    while(temp3!=null){
        boolean exponentPresent = false;
        for(int i=1;i<array.length;i++){
            if(temp3.exp==Integer.parseInt(array[i])){
                exponentPresent = true;
            }
        }
        if (!exponentPresent) {
            addList.createList(temp3.coef,temp3.exp);
        }
        temp3=temp3.next;
    }
    while(temp4!=null){
        boolean exponentPresent = false;
        for(int i=1;i<array.length;i++){
            if(temp4.exp==Integer.parseInt(array[i])){
                exponentPresent = true;
            }
        }
        if (!exponentPresent) {
            addList.createList(temp4.coef,temp4.exp);
        }
        temp4=temp4.next;
    }


    return addList;
}

And here's a print method you can add to the LinkedPoly class:

public void print() {
    current = head;
    System.out.print(current.coef + "x^" + current.exp);
    while (current.next != null) {
        current = current.next;
        System.out.print(" + " + current.coef + "x^" + current.exp);
    }
    System.out.println();
}

There were two main issues with your add method.

Issue #1. The first was that your loop through the array of already included exponents was outside of your loops through the nodes of the polynomial linked lists - it should be on the inside. The way you were doing it before, your process went like this:

a. Take one of the already included exponents from the array b. Go through all the terms of each polynomial c. If any of those terms has an exponent that doesn't match the exponent from part a., add it to the result. d. Repeat from part a., but using the next of the already included exponents.

The problem with this approach is that you only want to add a new term to the result if its exponent doesn't match ANY of the already included terms - not just if it doesn't match one of them. This is why your result had all those extra x^1 terms - when your program was at the "0" element of the array, it was adding the x^1 terms of the polynomials.

Issue #2. You should replace while (temp3.next!= null) or (temp4.next!=null) with just (temp3!=null) or (temp4!=null). Otherwise, your code never gets to the last node of the polynomial (it stops before the last one because it's checking to see if there's a "next" one after the last one). This is why your result didn't have the x^3 and x^4 terms - your loops were ending before getting to those terms.

A few things to consider

1. You use a lot of temp variables. Try giving them more descriptive names, or better yet, find a way that doesn't use so many.
2. I'm not sure why you add the already used exponents to an "exponent" string, which you then break up into an array with the split() method. Consider just adding to an array from the start.
3. Your add method could probably be restructured to be a lot cleaner. Instead of seeing which exponents your two polynomials have in common, dealing with those, and then dealing with the ones they don't have in common separately, you could try this: find the highest exponent in any of your polynomials. Then, cycle through all the exponent degrees from 0 to that number. Within each of those cycles, cycle through each polynomial, and add together the coefficients of all the polynomials that have that exponent. That way, your code would all be in one big loop.
4. Right now, your code doesn't ensure that the polynomials keep their terms in order - there's no way to stop the x^2 term from coming before a x^3 term, which comes before a x^1 term. Consider either adding a sort() method to your LinkedPoly class, adding some code during node addition that ensures the polynomials stay in order, or going with suggestion #3 above, which would allow you to sort your sum polynomial as you create it. Or, if having them in order isn't important, don't bother :)