We're a community of 1077K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,076,437 Members — Technology Publication meets Social Media

# Help me represent polynomial by using linked-list

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?

3
Contributors
2
Replies
11 Hours
Discussion Span
1 Year Ago
Last Updated
5
Views
Question
vuquanghoang
Newbie Poster
17 posts since Feb 2012
Reputation Points: 10
Skill Endorsements: 0

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?

Rashakil Fol
Super Senior Demiposter
Team Colleague
2,732 posts since Jun 2005
Reputation Points: 1,153
Skill Endorsements: 25

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

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

tungnk1993
Junior Poster in Training
95 posts since May 2010
Reputation Points: 6