In my mind, using linked list is somehow abstract. Despite reading posts with similar topic, I still cannot understand how to apply it in to real problem. My teacher gives my this exercise. In spite of not being mandatory, I want do is to understand the problem:
Addition/subtraction /multiplication.. . of two polynomials.
P1(x) = 2x2+3x+7
P2 (x)= 3x3+5x+2
P1(x)+ P2(x)= 3x3+2x2+8x+9
Can anyone give me some cue?

6 Years
Discussion Span
Last Post by Smita_1

What do you know about linked lists? Can you implement a linked list? Do you know what you can do with one?

Surely you understand what polynomials are and how adding them works.

One part of the question is, how would you represent a polynomial using a linked list? The other part is, what's the algorithm that would add two polynomials that are represented thusly?


I hope you already know what an array is.
You can access an array's item by specifying its index, for example a[1] = 1. However, for linked list, you cannot do that. It is because each "linked list node" usually has two parts, data and reference to next item. To access each item, usually, you have to go from the head node to the next one, for example :

node head; // hold the beginning node
//head.next will be your next node

To get to the second node in list, you can do this

node current = head.next;

Now current will have the data and reference to the 3rd item

So for your problem, I think what your teacher wants is to first store the two polynomials coefficient in linked lists, then use them to find the sum.

There are two things needed to store: the coefficient and the power
P(1) = 2x^2 + 3x^1 + 7x^0
So 1st linked list could be : 2|2 -> 3|1 -> 7|0
2nd linked list could be : 3|3 -> 5|1 + 2|0

To find the sum, assume that the power are in descending order.
Start taking the first two nodes, 2|2 and 3|3 . Larger power is 3. So P(3) = 3x^3 + .. Go to next node in P(2)

Two nodes to consider now is : 2|2 and 5|1 . 2 > 1 . P(3) = 3x^3 + 2x^2 + ... Move on like that and you'll get the answer.

If u dont understand, email me tungnk1993@gmail.com

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.